Competition problem — Combinatorics

Library / /6 of 94

Combinatorics Difficulty 4.6 AIME Prove it Hong Kong

In a school there are $b$ teachers and $c$ students. Suppose that
(i) each teacher teaches exactly $k$ students; and
(ii) for each pair of distinct students, exactly $h$ teachers teach both of them.
Show that
$\frac{b}{h} = \frac{c(c-1)}{k(k-1)}$

Solution

We count the number of triples $(T, S_1, S_2)$ such that $T$ is a teacher teaching two distinct students $S_1$ and $S_2$ . Note that $(T, S_1, S_2)$ is different from $(T, S_2, S_1)$ .

For each of the $b$ teachers, there are $k$ choices for $S_1$ and $k-1$ choices for $S_2$ . Therefore, there are $b k (k-1)$ such triples.

For each of the $c$ students $S_1$ and each of the $c-1$ students $S_2$ , there are $h$ choices for $T$ . Therefore, there are $c (c-1) h$ such triples.

Thus, we have obtained $b k (k-1) = c (c-1) h$ . This clearly implies $\frac{b}{h} = \frac{c(c-1)}{k(k-1)}$ .

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.