11
$\begingroup$

I was given this puzzle:

At the end of the seminar, the lecturer waited outside to greet the attendees. The first three seen leaving were all women. The lecturer noted " assuming the attendees are leaving in random order, the probability of that is precisely 1/3." Show the lecturer is lying (or badly mistaken).

I've puzzled it out to proving that there is no ratio of $\binom{a}{3}/\binom{a+b}{3}$ that is 1/3, where $ a,b \in\mathbb{N}$ and $a\ge3$ and $b\ge0$, $a$ being the number of women and $b$ the number of men.

I'm stuck at this point (but empirically pretty convinced).

Any help/pointers appreciated.

Rasher

PS- as an amusing aside, the first 12 values in the sequence of values for $\binom{3+b}{3}$ are the total number of gifts received for each day of the "12 days of Christmas" song.

I've narrowed it down to proving that in the sequence generated by $n^3+3 n^2+2 n$ with $n \in\mathbb{N}$ and $n\ge1$ it is impossible for $3(n^3+3 n^2+2 n)$ to exist in the form of $n^3+3 n^2+2 n$ . Still stymied at this point.

I found today a (somewhat) similar question at MathOverflow. Since my question seems to boil down to showing the Diophantine $6 a - 9 a^2 + 3 a^3 - 2 b + 3 b^2 - b^3=0$ has no solutions for $(a,b) \in\mathbb{N}$ and $(a,b)>= 3$ would it be appropriate to close this here and ask for help at MathOverflow to determine if this can be proved?

An update: I asked a post-doc here at Stanford if he'd have a look (he's done some heavy lifting in the area of bounds on ways $t$ can be represented as a binomial coefficient). To paraphrase his response "That's hard...probably beyond proof in the general case". Since I've tested for explicit solutions to beyond 100M, I'm settling with the lecturer is lying/mistaken at least in spirit unless one admits lecture halls the size of a state.

$\endgroup$
  • $\begingroup$ Rewrite it to one binomial coefficient and look at Pascal's triangle. $\endgroup$ – Anonymous - a group Dec 10 '13 at 12:02
  • $\begingroup$ @Anonomous: I am not aware of any identity that would allow me to re-write it as "one binomial coefficient". In any case, having a "look at Pascal's Triangle" is not a proof, which is what I'm seeking. Perhaps you could clarify what you meant, I could be missing something. $\endgroup$ – rasher Dec 10 '13 at 13:20
  • $\begingroup$ @Ross- done. Left bottom Diophantine as is, since not relevant there. Thx. $\endgroup$ – rasher Dec 16 '13 at 5:08
  • 2
    $\begingroup$ Thanks, Dan. I've verified there are no explicit solutions under a=10,000,000, and have approximated solutions to a~10^1000000 which gives 1/3 until past 1 million of the decimal digits. I'm able to get arbitrarily close, it seems, but I conjecture the ratio of b/a for a given a to get 1/2 is irrational so an exact 1/3 is not possible for integer a and b. This thing is keeping me amused... $\endgroup$ – rasher Dec 16 '13 at 8:02
  • 2
    $\begingroup$ @StevenStadnicki yes, it can be transformed to problem on an elliptic curve $y^2 = x^3 - 27x + 90$. Look at answers of this question which I believe is inspired by this question. $\endgroup$ – achille hui Apr 29 '14 at 5:31
5
$\begingroup$

Let $a$ = the number of women, $b$ = the number of men, and $n = a + b$ be the total number of attendees.

The probability that the first 3 students to leave are all female is $\frac{a}{n} \cdot \frac{a-1}{n-1} \cdot \frac{a-2}{n-2}$. Setting this expression equal to $\frac{1}{3}$ and cross-multiplying gives $3a(a-1)(a-2)=n(n-1)(n-2)$.

The product of any three consecutive integers is divisible by 6, so the left-hand side is divisible by 18. For the equation to work out, we must have $n \in \{0, 1, 2\}$ modulo 9.

This doesn't solve your puzzle, but it does rule out (informally) 2/3 of the domain.

$\endgroup$
2
$\begingroup$

Simplistic answer:

Let $w=$ number of women, $m=$ number of men, and $n=w+m$.

Assuming the professor has no prior knowledge of the male:female ratio on the course, the solution is quite simple.

The probability that $w:m=1:1$ is $50:50$, so $n=2w$.

Dan's statement can therefore be rewritten:

$$(3w-3)(w-2)=(4w-2)(2w-2)\\ 3w^2-9w+6=8w^2-12w+4\\ 5w^2-3w-2=0\\ w=\frac{3\pm \sqrt {9+40}}{10}\\ w=1, -\frac {2}{5} $$ which, of course is absurd.

More complete answer:

Without assuming that probabilistically, $n=2w$.

This is basically a rephrasing of your conjecture that there are no rational solutions for $a$ (in the comments section above). $$3w(w-1)(w-2)=(w+m)(w+m-1)(w+m-2)\\ 2m-3m^2+m^3-4w-6mw+3m^2w+6w^2+3mw^2-2w^3=0\\$$ which basically boils down to the (ugly beast of a) statement that $$w=\frac{2+m}{2}+ \frac{-12-27m^2}{6\sqrt[3]{3}\sqrt[3]{54m^3\sqrt{3}\sqrt{-64-432m^2-972m^4+243m^6}}}+\\ \frac{\sqrt[3]{-54m^3+\sqrt{3}\sqrt{-64-432m^2-972m^4+243m^6}}}{4\sqrt[3]{9}}\\ $$ has no integer solutions for $m\in \mathbb{Z}$. Unfortunately, this is where I become a little unstuck!

$\endgroup$
  • $\begingroup$ Just saw this, nice work! Seems to fit into the post-doc's statement of "probably beyond proof..." +1 $\endgroup$ – rasher Apr 27 '14 at 7:34
  • $\begingroup$ Thanks! Looked like a fun problem but there is more to it than meets the eye! :) $\endgroup$ – martin Apr 27 '14 at 21:35
-1
$\begingroup$

Your ratio is $\frac{a! (a+b-3)! 3!}{(a-3)!3!(a+b)!} = \frac{(a+b-3)!}{(a-3)!(a+b)!} = 1/\binom{a+b-3}{a+b},$ so you are trying to prove that $\binom{a+b}{a+b-3}$ is never equal to $3.$ If you look at Pascal's triangle, you will see that the third column is increasing, so you need only check it for a couple of initial values.

$\endgroup$
  • 3
    $\begingroup$ Algebra error: you lost a factor of $a!$ in the numerator. $\endgroup$ – Brian M. Scott Dec 10 '13 at 1:38

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.