Twenty boys and twenty girls were invited to a prom. During the dance competition $99$ pairs (consisting of a boy and a girl) made a dance performance. All pairs were unique. Prove that there exist such two boys and such two girls that each boy danced with both girls.

What I managed to do myself:

I found the number of pairs consisting of $2$ girls: it's $\frac{20!}{18!\cdot 2!}=190$

  • $\begingroup$ Maybe try starting with $n$ boys and $n$ girls and try to determine $f(n)=$the maximum number of unique pairs that can dance together if there are no such two boys and girls, then show that $f(20)\lt 99$. You can look for a pattern with small values of $n$. $\endgroup$ – Gabriel Burns Oct 28 '16 at 20:07
  • $\begingroup$ This would usually be phrased as a question about how many edges a bipartite graph on 20+20 nodes with girth at least 6 can have. Attempts to search for that turns up references to a Reiman's inequality -- which however is not tight enough for this purpose (It doesn't exploit the graph being bipartite either). $\endgroup$ – Henning Makholm Oct 28 '16 at 20:12
  • $\begingroup$ So far you've done one basic calculation. You might see if you can come up with any of these other quantities, which might be relevant: number of pairs consisting of a boy and a girl, number of ways to pick 2 boys and 2 girls, and anything else that occurs to you. This won't get you the solution by itself, but it can help you think about the problem, and it's good practice if you're just learning combinatorics. $\endgroup$ – Gabriel Burns Oct 28 '16 at 20:13
  • $\begingroup$ @HenningMakholm do you mean Riemann? or is there a Reiman too? $\endgroup$ – Gabriel Burns Oct 28 '16 at 20:19
  • $\begingroup$ @GabrielBurns: There's a Reiman too; the inequality in question is cited as "Reiman (1958)", long after Bernhard Riemann's time. $\endgroup$ – Henning Makholm Oct 28 '16 at 20:20

Assume that there is no two boys and two girls that each boy danced with both girls.

Let the girls are G1, G2, ...G20, and they danced with n1, n2, ...n20 boys. We have that

n1 + n2 + ... + n20 = 99*2 = 198

For a girl, say G1, we can select 2 boys from the n1 boys who danced with G1. There are C(n1,2) = n1*(n1-1)/2 such pair of boys. Similar, for girl G2, we have C(n2,2) pairs of boy who danced with G2. We say, the boy-pairs of G1 and G2 has no overlap, otherwise we will have boy B1 and B2, they both danced with G1 and G2, contradiction.

Boy-pairs of each girl should have no overlap. So, the sum should be not greater than C(20,2)=190

It's to say: C(n1,2)+C(n2,2)+...+C(n20,2)<=190

but the left side is

(n1^2 + n2^2 + ... + n20^2 - n1 - n2 - ... -n20)/2

it's greater or equal than ( ((n1+...+n20)/20)^2 * 20 - (n1+...+n20) )/2

= ( (198/20)^2 * 20 - 198 ) / 2

= 881.1



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.