Competition problem — Combinatorics

Library / /111 of 136

Combinatorics Difficulty 8.3 Shortlist Prove it Hong Kong

In a school there are $2013$ boys and $2013$ girls. For each pair of a boy and a girl, together they have to choose one (and only one) of $25$ different clubs to join. Determine the maximum possible value of the integer $k$ , such that no matter what the choices of the students are, there is a club with $k$ or more members. (A boy and a girl in a club together are counted as two members.)

Solution

The answer is $806$ .

By the pigeonhole principle, there is a club with $n \ge \frac{2013^2}{25}$ pairs. Suppose there are $a$ boys and $b$ girls in this club. Then the number of pairs is at most $ab$ . By the AM-GM inequality, we have
$\frac{a+b}{2} \ge \sqrt{ab} \ge \sqrt{n} \ge \frac{2013}{5}.$

This implies the number of members of this club is $a + b \ge 806$ .

We now give a construction for which $k \le 806$ . We partition the boys into $5$ groups $B_1, B_2, \dots, B_5$ such that each of $B_1, B_2, B_3$ has $403$ boys, while each of $B_4, B_5$ has $402$ boys. Similarly, we partition the girls into $5$ groups $G_1, G_2, \dots, G_5$ in a similar way. Suppose each boy in group $B_i$ and each girl in group $G_j$ choose the club $C_{ij}$ . Then each club consists of at most $403+403=806$ members. This proves $k \le 806$ .

It follows that the maximum $k$ is $806$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.