Competition problem — Combinatorics

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.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.