41
$\begingroup$

In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says:

On National Public Radio, the Weekend Edition program posed the following probability problem: Given a certain number of balls, of which some are blue, pick 5 at random. The probability that all 5 are blue is 1/2. Determine the original number of balls and decide how many were blue.

If there are $n$ balls, of which $m$ are blue, then the probability that 5 randomly chosen balls are all blue is $\binom{m}{5} / \binom{n}{5}$. We want this to be $1/2$, so $\binom{n}{5} = 2\binom{m}{5}$; equivalently, $n(n-1)(n-2)(n-3)(n-4) = 2 m(m-1)(m-2)(m-3)(m-4)$. I'll denote these quantities as $[n]_5$ and $2 [m]_5$ (this is a notation for the so-called "falling factorial.")

A little fooling around will show that $[m+1]_5 = \frac{m+1}{m-4}[m]_5$. Solving $\frac{m+1}{m-4} = 2$ shows that the only solution with $n = m + 1$ has $m = 9$, $n = 10$.

Is this the only solution?

You can check that $n = m + 2$ doesn't yield any integer solutions, by using the quadratic formula to solve $(m + 2)(m +1) = 2(m - 3)(m - 4)$. I have ruled out $n = m + 3$ or $n = m + 4$ with similar checks. For $n \geq m + 5$, solutions would satisfy a quintic equation, which of course has no general formula to find solutions.

Note that, as $n$ gets bigger, the ratio of successive values of $\binom{n}{5}$ gets smaller; $\binom{n+1}{5} = \frac{n+1}{n-4}\binom{n}{5}$ and $\frac{n+1}{n-4}$ is less than 2—in fact, it approaches 1. So it seems possible that, for some $k$, $\binom{n+k}{5}$ could be $2 \binom{n}{5}$.

This is now a question at MathOverflow.

$\endgroup$
  • 1
    $\begingroup$ We know that the exact power of two that divides the binomial coefficient ${n\choose 5}$ is the number of carries you need to do when you calculate $5+(n-5)$ in binary (with the grade school method). We can thus immediately rule out cases like $n\equiv 5\pmod8$ and $n\equiv 7\pmod 8$ simply because ${n\choose 5}$ is then an odd integer. Not sure how much this helps (other than cuts down search space), I'm afraid :-( $\endgroup$ – Jyrki Lahtonen Mar 28 '13 at 5:35
  • 3
    $\begingroup$ Note that you need approximately $n = 2^{1/5} m.$ So, with a computer package that allows for large integers, you can test this very rapidly. It is actually quicker to fix $k = n - m$ which is what you began in the final paragraph. Then solve for real number $\mu$ such that $$ k = (2^{1/5} - 1) \mu, $$ then let $m = 2 + \lfloor \mu \rfloor$ and $n = m + k.$ If the ratio is above 2 (it should be) increase both $m,n$ by 1 until the ratio is below 2. Then go on to the next difference $k.$ $\endgroup$ – Will Jagy Mar 28 '13 at 21:10
  • 1
    $\begingroup$ Considering possible values of $m$ modulo primes from 7 to 31, it's possible to quick-reject all but 8223271875 values $\pmod {247357937827}$ (i.e. to quick-reject about 29 in 30 values). It might be possible to prove that for prime $p$ at least $f(p)$ values of $m \pmod p$ have no possible value of $n \pmod p$ with a function $f$ which grows fast enough to make a heuristic argument for the number of solutions being vanishingly small. $\endgroup$ – Peter Taylor Mar 31 '13 at 22:19
  • 1
    $\begingroup$ A computer search says there are no other solutions for $n$ up to (as of now) 8040000000. $\endgroup$ – ShreevatsaR Apr 1 '13 at 9:36
  • 1
    $\begingroup$ It is necessary that we have $m>\frac {5n}{6}$ in order for the solution to exist. $\endgroup$ – user67878 Apr 3 '13 at 17:25
13
+100
$\begingroup$

Many Diophantine equations are solved using modern algebraic geometry. For an informal survey how this works, see

M. Stoll, How to solve a Diophantine equation, arXiv.

The most prominent example is Fermat's equation. But there are also interesting binomial equations. It has been shown very recently that $\binom{x}{5}=\binom{y}{2}$ has exactly $20$ integer solutions:

Y. Bugeaud, M. Mignotte, S. Siksek, M. Stoll, Sz. Tengely, Integral Points on Hyperelliptic Curves, arXiv

I don't know if this can be proven by elementary means. And I don't know the situation for $\binom{x}{5}=2 \binom{y}{5}$. I just want to warn you that it might be a waste of time to look for elementary solutions, and that instead more sophisticated methods are necessary. On the other hand, this equation arises as a problem from a book, so I am not sure ...

$\endgroup$
  • 1
    $\begingroup$ I suggest to ask this at mathoverflow ... $\endgroup$ – Martin Brandenburg Apr 9 '13 at 19:27
5
$\begingroup$

I am putting some results that may or may not be part of an answer here, as a community wiki post, rather that cluttering the question with them. Perhaps they will help lead someone to a complete answer. If you have similar potentially useful information or partial answers, please feel free to add it here.


Let's see what can be gleaned by looking at $\binom{n}{r} = 2 \binom{n-k}{r}$ for other values of $r$. There is an interesting duality: $\binom{n}{r} = 2 \binom{n-k}{r} \iff \binom{n}{k} = 2 \binom{n-r}{k}$. So we can find solutions to the original problem by finding solutions to $\binom{n}{k} = 2\binom{n-5}{k}$. For any $r$, there is a "standard" solution, $\binom{2r}{r} = 2\binom{2r-1}{r}$, and several "trivial" solutions, $\binom{i}{r} = 2\binom{j}{r}$ whenever $0 \leq i,j \leq r - 1$.

For $r = 1$, there are infinitely many solutions; for any $k$, we have $\binom{2k}{1} = 2 \binom{k}{1}$. Under the duality, these correspond to the "standard" solutions $\binom{2k}{k} = 2 \binom{2k - 1}{k}$.

For $r = 2$, there are also infinitely many solutions. It's fun to see why. A solution satisfies the equation $n(n-1) = 2 (n-k)(n-k-1)$ or $$\begin{equation}\tag{1}\label{eq:qud}n^2 - (4k+1)n + (2k^2 + 2k) = 0.\end{equation}$$ Thus $n = \frac{4k + 1 \pm \sqrt{8k^2 + 1}}{2}$. Since $8k^2 + 1$ is odd, this either has two integer solutions if $8k^2 + 1$ is a perfect square, or none at all. Thus, whenever there is one solution $n$ for a given difference $k$, there must be a second. The second key ingredient is that since we are multiplying evenly many terms, we can change the signs of all the terms without changing the result.

So, start with the standard solution: $$ 4 \cdot 3 = 2 (3 \cdot 2). $$ Then it's also true that $$ 4 \cdot 3 = 2 (-2 \cdot -3), $$ in other words, $[4]_2 = 2[-2]_2 = 2[4-6]_2$, a solution with $k = 6$. So there must be another. When $k = 6$, equation $\eqref{eq:qud}$ is $n^2 - 25n + 84 = 0$, and we know we can factor out $(n - 4)$, which leaves $(n - 21)$. And indeed, $\binom{21}{2} = 2 \binom{15}{2}$. The duality gives $\binom{21}{6} = 2 \binom{19}{6}$. Repeating the process, we get $[21]_2 = 2 [-14]_2$ with a difference $k = 35$; factoring $(n - 21)$ from equation $\eqref{eq:qud}$ leaves $(n - 120)$, and indeed $\binom{120}{2} = 2 \binom{85}{2}$. Dually, $\binom{120}{35} = 2 \binom{118}{35}$. We can keep going up this "staircase" forever; if $k$ gives a solution, then so does $3k + \sqrt{8k^2 + 1}$. This is OEIS A001109.

Of course, this doesn't help for our case because $5$ doesn't appear. But it does show that solutions exist, besides the standard and trivial ones, for $r > 2$.

Now consider $r = 3$. We need to solve $[n]_3 = 2[n-k]_3$ or $$\begin{equation}\tag{2}\label{eq:cub}n^3 - (6k + 3)n^2 + (6k^2 + 12k + 2)n - (2k^3 + 6k^2 + 4k) = 0.\end{equation}$$ With $k = 0$ this factors as expected as $n(n-1)(n-2)$. With $k = 1$ it again gives us the known trivial and standard solutions, $(n-1)(n-2)(n-6)$. With $k = 2$, $\eqref{eq:cub}$ is $n^3 - 15n^2 + 50n - 48 = 0$, from which we can factor the known trivial solution: $(n-2)(n^2 - 13n + 24) = 0$. But the other factor has no integer solutions. For general $k$, we can apply the Cubic formula. We find that the discriminant $\Delta$ is $4(-27k^6 + 108k^4 + 18k^2 + 1)$, which is positive for $k = 0,1,2$ and negative for $k \geq 3$, so that it has three real roots for $k \leq 2$ but only one real root for $k \geq 3$. This root turns out to be $$ 2k + 1 - \sqrt[3]{-3k^3 + \sqrt{k^6 - 4k^4 - \frac{2}{3}k^2 - \frac{1}{27}}} - \sqrt[3]{-3k^3 - \sqrt{k^6 - 4k^4 - \frac{2}{3}k^2 - \frac{1}{27}}}. $$ I don't think that this can ever be an integer, but I don't know how to prove this. Unfortunately it's not sufficient to show that the contents of the cube roots cannot be perfect cubes, since even if neither is an integer, their sum still could be. However, no solutions exist for $n$ up to 10,000 (checked in the table provided at OEIS A000292.)

We can at least check if any answers to our original question have the difference $n - m = 3$ by looking at the above root, with $k = 5$. It's about 25.268, not an integer, so any extra solutions have the difference at least 4.

For $r = 4$, a similar "negation" trick should work as for $r = 2$. Unfortunately, it doesn't seem to yield extra positive solutions. The equation $[n]_4 = 2[n-k]_4$ expands to $$\begin{equation}\tag{3}\label{eq:qrt}n^4 - (8k + 6)n^3 + (12k^2 + 36k + 11)n^2 - (8k^3 + 36k^2 + 44k + 6)n + (2k^4 + 12k^3 + 22k^2 + 12k) = 0.\end{equation}$$ Starting from the standard solution, $[8]_4 = 2[7]_4$, we have another solution, $[8]_4 = 2[-4]_4$, with difference $k = 12$. And indeed, we can factor $(n - 8)$ out of equation $\eqref{eq:qrt}$ with $k = 12$, $$ n^4 - 102n^3 + 2171n^2 - 19542n + 65520 = (n-8)(n^3 - 94n^2 + 1419n - 8190). $$ But the other factor is a cubic with one real root, which isn't an integer. There are no solutions (besides the trivial and standard) up to $n=1002$ (checked in the table provided at OEIS A000332.)

When $k=5$, $\eqref{eq:qrt}$ becomes $n^4 - 46n^3 + 491n^2 - 2126n + 3360$, which (according to Wolfram Alpha) has no integer solutions. So for the original problem, $n - m > 4$.


Related OEIS sequences:

  • A000389: $\binom{n}{5}$ and table up to $n=1000$
  • A001109 are values of $k$ such that $\binom{n}{2} = 2\binom{n-k}{2}$, or equivalently $\binom{n}{k} = 2\binom{n-2}{k}$, has a solution $n = \bigl(4k + 1 + \sqrt{8k^2 + 1}\bigr)/2$.
  • A082291 are the values of $n-2$ in the above, offset by one. That is, A001109 begins 0,1,6 and A082291 begins 2, 19, 118. $\binom{2+2}{1} = 2\binom{2}{1}$, and $\binom{19+2}{6} = 2\binom{19}{6}$.
$\endgroup$
  • $\begingroup$ I was also trying to solve it along similar lines of thought, and also proved that the case $r=2$ has infinitely many solutions, by reducing that case to a Pell equation which had infinitely many solutions, and those solutions can be determined recursively so probably (I didn`t try) the recursion can be find for infinitely many or all such $n$ which are solutons to the case $r=2$. Nice work. $\endgroup$ – user67878 Apr 8 '13 at 11:20
0
$\begingroup$

WRONG The problem generalizes to the drawing of $N>1$ balls. The solution for any $N$ is characterized by a telescoping product of probabilities (one for each ball drawn) whose first factor is $\frac{2N-1}{2N}$ with subsequent factors progressively smaller. The solutions are unique UNPROVEN: consider perturbations. Increasing (or decreasing) the first factor increases (or decreases WRONG) all the factors and so the product. Thus the first factor of any solution is fixed. With the first factor fixed, some measure of the overall shrinkage of subsequent factors must be constant if the product is not to change; but if we multiply the numerator and denominator of the first factor by some natural number greater than 1, we reduce the relative shrinkage from factor to factor, which increases the product. Thus the telescoping product is immutable; so every solution has $2N$ balls with all but one being blue. [Apparently rude edits added by author.]

$\endgroup$
  • $\begingroup$ Some of the telescoping products mentioned: $$\begin{align}N=2\quad&&\frac34\cdot\frac23&=\frac12,\\N=3\quad&&\frac56\cdot\frac45\cdot\frac34&=\frac12,\\N=4\quad&&\frac78\cdot\frac67\cdot\frac56\cdot\frac45&=\frac12;\end{align}$$ and my claim is that the factors can't be fiddled (because of their mutual relation) without altering the product; so all solutions for $N>1$ are unique. $\endgroup$ – mindless oaf Apr 6 '13 at 0:23
  • $\begingroup$ I don't know why mathjax doesn't like me. $\endgroup$ – mindless oaf Apr 6 '13 at 0:32
  • $\begingroup$ This is why. $\endgroup$ – Cameron Buie Apr 6 '13 at 17:58
  • $\begingroup$ (I didn't downvote this, but.) A lot of people have tried for more than a week to figure out whether the solution is unique for just drawing $5$ balls, and you go ahead and claim there's a unique solution for drawing any $N$ balls in general. :-) Try writing down your proof clearly for the $N = 5$ case in question here... $\endgroup$ – ShreevatsaR Apr 6 '13 at 19:50
  • $\begingroup$ The solution comes from $$\frac12=\frac9{10}\cdot\frac89\cdot\frac78\cdot\frac67\cdot\frac56.$$ Each factor is the probability of drawing a blue ball, so each but the first relates to the previous by having numerator and denominator each less by one. $\endgroup$ – mindless oaf Apr 6 '13 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.