Wikipedia:Reference desk/Archives/Mathematics/2008 December 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 17

Number of subsets of size k

Hello. I am trying to solve the given problem:

In a given set of the form $\{1,2\cdots n\}$ how many subsets of size k (where $0\leq k\leq n$) are possible where each k-subset has the property that if its elements are placed in increasing order the absolute difference between two consecutive elements belongs to a given set $\{d_{1},d_{2}\}$ where $d_{1},d_{2}$ are positive integers.

I'll be grateful for any help. Thanks.--Shahab (talk) 07:45, 17 December 2008 (UTC)

How certain are you that there's an answer of a simple form? 67.150.247.57 (talk) 08:29, 17 December 2008 (UTC)

Hi Shahab. Do the same as in your previous problem. For each of the $2^{k-1}$ binary sequences $\delta$ of increments, with $\scriptstyle \delta _{i}\in \{d_{1},d_{2}\}$, you should count how many $a\in \mathbb {N}$ generate a sequence with $x_{k}\leq n$. It depends only on the number r of indices i such that $\delta _{i}=d_{1}$. You will obtain a sum over $0\leq r\leq k-1$, weighted with a binomial $\scriptstyle {k-1} \choose {r}$, to work out.--PMajer (talk) 09:31, 17 December 2008 (UTC)

Something like $\scriptstyle \sum _{r}{k-1 \choose r}(n-rd_{1}-(k-1-r)d_{2})_{+}$, where $x_{+}$ denotes the positive part of $x$. Assuming $d_{1}>d_{2}$, the sum is over all integer r with $\scriptstyle 0\leq r\leq {n-(k-1)d_{2} \over d_{1}-d_{2}}$ (in the last inequality $<$ or $\scriptstyle \leq$ does not make a difference because the corresponding term with =, if any, is 0). Also note that if $\scriptstyle n\geq (k-1)d_{1}$ all terms are authomatically positive and the sum reduces to a simpler closed form (in this case maybe ther is a more direct computation).--PMajer (talk) 14:05, 17 December 2008 (UTC)

Thanks PMajer for the reply. I really haven't worked everything what you said yet but I am getting there. It's not clear to me why $\scriptstyle 0\leq r\leq {n-(k-1)d_{2} \over d_{1}-d_{2}}$. My real _target however is to find out the number of such k-subsets where d1 and d2 can be any possible values and are not given on advance. So really I want to count the number of weak k-APs (or something like that) in {1,2...n}. I don't know whether a solution exists. Any comments on that? Cheers----Shahab (talk) 16:16, 17 December 2008 (UTC)

Ok, so you want the whole sum over r and $0<d_{2}<d_{1}$. It could be worked and reduced to a simpler form, maybe. But you have possibly more chances with asymptotics. In this direction, I would try splitting the sum into a sum over $\scriptstyle d_{2}\leq n^{\alpha }$ and one over $n^{\alpha }<d_{2}$, choosing $\alpha$ such that the second sum is little oh of the first. The first sum, rescaled, should luckily produce an integral. Shouldn't this work, plan B: try to write a generating function and then work on the coefficients. Again, some more chances with asymptotics.--PMajer (talk) 15:21, 18 December 2008 (UTC)

It seems that an asymptotics is not that complicated to obtain; however, the sum I wrote has to be corrected a little bit, because those special sequences displaying only "$\textstyle d_{1}$-jumps" or only "$\textstyle d_{2}$-jumps" (i.e. the arithmetic ones) have to be counted separately, if you know what I mean. Just to make all formulas a bit simpler, let $h:=k-1\$, $a:=d_{1}-d_{2}>0\$ , $b:=d_{2}>0\$; then the number of your $\ (h+1)$ -terms sequences in $\textstyle \{1,2,\cdots ,n\}$ is :

$\sum _{a>0}(n-ha)_{+}\ +\sum _{s=1}^{h-1}\ \sum _{a>0,b>0}{h \choose s}(n-sa-hb)_{+}$.

Precisely, the first sum counts the number of k-terms arithmetic sequences, and we already know everything about it; the second sum counts the number of non-arithmetic sequences, that is, making $s\$ jumps of $\textstyle d_{1}$ and $h-s\$ jumps of $\ \textstyle d_{2}$, where now $s\$ varies from 1 to $h-1\$. There are ${h \choose s}$ such sequences $\textstyle x_{0}<x_{1}..<x_{h}$, and they all have the same final value $\textstyle x_{h}=x_{0}+sd_{1}+(h-s)d_{2}=x_{0}+sa+hb$. Therfore, in order to have $x_{h}\leq n$, the corresponding initial value must verify $\textstyle 1\leq x_{0}\leq n-sa-hb$, and there are thus exactly $\textstyle (n-sa-hb)_{+}$ choices for it. Since any sequence is uniquely determined by $\textstyle x_{0}$ and by the ordered sequence of the jumps $\textstyle x_{i}-x_{i-1}$ for $\textstyle 1\leq i\leq h$, we are led to the above sum. Now let us find an asymptotics for it as $n\to +\infty$. Extract a factor $\textstyle n^{3}\$ : the idea is that what is left is a Riemann sum for a double integral:

$S(h,n):=\sum _{a,b,s}{h \choose s}\left(n-sa-hb\right)_{+}=n^{3}\sum _{a,b,s}{h \choose s}\left(1-s{\frac {a}{n}}-h{\frac {b}{n}}\right)_{+}{\frac {1}{n^{2}}}$,

where hereafter all sums are over positive integers and $s<h\$ . Notice that one has, just by the bounds of the integrands on the domains of integration:

$\int _{[{\frac {a}{n}},{\frac {a+1}{n}}]\times [{\frac {b}{n}},{\frac {b+1}{n}}]}(1-sx-hy)_{+}dx\ dy\leq \left(1-s{\frac {a}{n}}-h{\frac {b}{n}}\right)_{+}{\frac {1}{n^{2}}}\leq \int _{[{\frac {a-1}{n}},{\frac {a}{n}}]\times [{\frac {b-1}{n}},{\frac {b}{n}}]}(1-sx-hy)_{+}dx\ dy$.

Summing over all $a>0\$ and $b>0\$ we get:

$\int _{[{\frac {1}{n}},\infty [\times [{\frac {1}{n}},\infty [}(1-sx-hy)_{+}dx\ dy\leq \sum _{a,b}\left(1-s{\frac {a}{n}}-h{\frac {b}{n}}\right)_{+}{\frac {1}{n^{2}}}\leq \int _{]0,\infty [\times ]0,\infty [}(1-sx-hy)_{+}dx\ dy$.

The value of each of the two integrals is just the volume of an orthogonal tetrahedron; precisely, on the right it is the tetrahedron with vertices $\textstyle (0,0,0)\$, $\textstyle ({\frac {1}{s}},0,0)\$, $\textstyle (0,{\frac {1}{h}},0)\$, $\textstyle (0,0,1)\$, with volume ${\frac {1}{6sh}}$; the other is similar but reduced of a factor $\left(1-{\frac {s+h}{n}}\right)^{3}\geq \left(1-{\frac {2h}{n}}\right)^{3}\geq 1-{\frac {6h}{n}}$, for all $1\leq s\leq h$.

Summing over all $0<s<h\$ we get:

$\left(1-{\frac {6h}{n}}\right){\frac {n^{3}}{6h}}\ \sum _{s=1}^{h-1}{h \choose s}{\frac {1}{s}}\ \leq \ S(h,n)\ \leq \ {\frac {n^{3}}{6h}}\ \sum _{s=1}^{h-1}{h \choose s}{\frac {1}{s}}$.

In particular

$S(h,n)=C_{h}n^{3}\left(1+O\left({\frac {1}{n}}\right)\right)\quad$ , as $\ n\to \infty$

with the constant

$C_{h}:={\frac {1}{6h}}\ \sum _{s=1}^{h-1}{h \choose s}{\frac {1}{s}}$.

Notice that for the number of the arithmetic progression (the first sum) we had found an asymptotics ${\frac {n^{2}}{2h}}\left(1+O\left({\frac {1}{n}}\right)\right)$ (you can check it computing it again by means of the corresponding integral in one variable), so adding it to $S(h,n)\$ does not affect the above asymptotic. With more precise evaluation one should be able to get more precise asymptotics; however this is the first order one, and it is possible that one can get it more dirctly by probabilistic arguments. A small check: for $k:=2\$ the second sum is of course empty; if $k:=3\$ all 3-terms sequences are to be counted, and in fact $S(3,n)={\frac {n^{3}}{6}}\left(1+O\left({\frac {1}{n}}\right)\right)={n \choose 3}\left(1+O\left({\frac {1}{n}}\right)\right)$. --PMajer (talk) 11:32, 29 December 2008 (UTC)

REVISITED: How many subtractions do you need to obtain number 32, using the numbers 1, 5, 6, 7 and 9?

OK, so the answer is 3 subtractions as per the following: 57 - 19 - 6 = 32. I guess the question requires that you use all integers. What is the name of the logic I used to solve this? What I did was keep combining the digits until it finally equaled 32. However, is there an easier way to solve this? --Emyn ned (talk) 16:00, 17 December 2008 (UTC)

I would say that is two subtractions, not three; it uses the digits 1, 5, 6, 7 and 9, not the numbers; and it is not unique because 57 - 16 - 9 also works. It's just a dreadfully mal-formed and ambiguous question. Gandalf61 (talk) 16:09, 17 December 2008 (UTC)

You are correct! Two, not three...--Emyn ned (talk) 16:12, 17 December 2008 (UTC)

Also note that this question was taken from one of the online IQ tests which is one of the External Links in the genius Wiki article. Tests & Questionnaires by Members of the Cerebrals Society. --Emyn ned (talk) 16:16, 17 December 2008 (UTC)

If you know the answers to my questions above, do you know the answer to the following?: How many additions do you need to obtain number 10, using the numbers 1, 3, 3 and 5? The closest I have come to is 13 + (-5) + 3 but it equals 11, not 10. --Emyn ned (talk) 16:03, 17 December 2008 (UTC)

3 + 3 + 5 + (-1) = 10. --LarryMac | Talk 16:06, 17 December 2008 (UTC)

5+1=10 in base 6 —Preceding unsigned comment added by PMajer (talk • contribs) 16:25, 17 December 2008 (UTC)

Look, there is no point asking the questions again and again. They are really bad questions and are impossible to answer because there is no way to know what they actually want. Find another way to challenge yourself, that IQ test is rubbish. --Tango (talk) 18:04, 17 December 2008 (UTC)

9 + 9 + 9 + 5 = 32. That makes zero subtractions. —Preceding unsigned comment added by 84.187.93.95 (talk) 01:43, 19 December 2008 (UTC)

Rational inequalities

1. ${\frac {x+1}{2x-6}}>0$

2. ${\frac {x+1}{2x-6}}+1>1$

3. ${\frac {3x-5}{2x-6}}>1$

4. $3x-5>2x-6\,$

5. $x-5>-6\,$

6. $x>-1\,$

Two questions:

a) I arrived at x > -1, when actually, the answer is x < -1. I can arrive at the correct answer by taking the reciprocal of both sides at point 3. Continuing to solve for x will give me x < -1. How the HELL do I tell if I have the right answer, because I don't know wether to take the reciprocal or not?

b) The other solution is x > 3. How can I derive both solutions algebraically? Right now I can only solve linear inequalities, not rational or higher polynomial. Is there a way of solving inequalities for a variable x if I know the solutions to the equation?

86.144.56.2 (talk) 17:51, 17 December 2008 (UTC)

I'd solve this by writing down a table of for which x the numerator and denominator are positive and negative separately. Fredrik Johansson 18:03, 17 December 2008 (UTC)

From step 3 to 4 you need to know whether 2x-6 is positive or negative. It appears mysterious because of the enigma wrapped in the mystery of the "x", but for specific numbers the problem is very clear: 2 is less than 7 but 2*(-1) is not less than 7*(-1). When you multiply the inequality 2 < 7 by the negative number -1, it flips the inequality: -2 > -7. When you are working with something like 2x-6 you have to break into two cases, 2x-6 positive and 2x-6 negative. When 2x-6 is positive, x > 3, and so you answer becomes "in case 2x-6 is positive, it is sufficient that x > -1", but that is a little redundant "in case x is greater than 3, then any x greater than -1 (that is still greater than 3) works". This just simplifies to "x greater than 3". You still have to look at the other case when 2x-6 is negative, but this should work out like you said with the "reciprocal".

You asked another very important question unrelated to the rules of flipping inequalities: "how do I tell if I have the right answer?" For rational inequalities it turns out that you only need to find the "important" points, and then you can just check points in between. For this inequality, the important points are x=-1 (when the numerator is zero) and x=3 (when the denominator is zero). Just check x=-2, x=0, and x=4 to see whether (x+1)/*(2x-6) is positive or negative for "all x less than -1", "all x strictly between -1 and 3", and "all x greater than 3". This method is the same as the one suggested by Fredrik Johansson above.

Even if you don't know this method, it should be clear that it at least helps you check your work: try some very negative number, like -100, try some very positive number like 100, and then carefully try some middle numbers; make sure that your general answer agrees with your tests for specific values of x. For instance, you work out that x > -1 are the only x, but when you check x=0 you get 1/-6 is negative, oops. Also, when you try x=-100, you get -99/-206 is positive, oops. JackSchmidt (talk) 18:08, 17 December 2008 (UTC)

(edit conflict, saying about the same thing but I'll post it anyway) The problem is in step 4 - you have multiplied by something that might be negative, you can't do that. When you multiply (or divide) an inequality by a negative number it reverses it. I think the best approach is to split it into cases, do it assuming 2x-6>0 and then do it assuming 2x-6<0 (remember to include those assumptions in the final answer). The answer clearly isn't just x<-1, if you plug in a very large x you'll get about 1/2, which is greater than zero. --Tango (talk) 18:12, 17 December 2008 (UTC)