# Prove the lecturer is a liar…

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.

• Rewrite it to one binomial coefficient and look at Pascal's triangle. – Anonymous - a group Dec 10 '13 at 12:02
• @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. – rasher Dec 10 '13 at 13:20
• @Ross- done. Left bottom Diophantine as is, since not relevant there. Thx. – rasher Dec 16 '13 at 5:08
• 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... – rasher Dec 16 '13 at 8:02
• @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. – achille hui Apr 29 '14 at 5:31

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.

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.

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!
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.
• Algebra error: you lost a factor of $a!$ in the numerator. – Brian M. Scott Dec 10 '13 at 1:38