Library / Hellenic Mathematical Olympiad /5 of 57

Hellenic Mathematical Olympiad

Combinatorics Difficulty 5.1 AIME, harder Prove it Greece

Each of the $50$ students of a class sent on Christmas period cards to exactly $25$ co-students. Prove that at least $2$ of the $50$ students each received the card of the other.

Solution

$50$ students determine $\frac{50 \cdot 49}{2} = 1225$ different pairs. The cards sent are totally $50 \cdot 25 = 1250 > 1225$ , a number greater than the number of different pairs. Hence at least the members of one pair received each the card of the other.

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

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