HMMT February, 2019

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

There are 100 people in a room with ages $1, 2, \ldots, 100$ . A pair of people is called cute if each of them is at least seven years older than half the age of the other person in the pair. At most how many pairwise disjoint cute pairs can be formed in this room?

Solution

Solution:

For a cute pair $(a, b)$ we would have
$a \geq \frac{b}{2} + 7, \quad b \geq \frac{a}{2} + 7$
Solving the system, we get that $a$ and $b$ must both be at least $14$ . However, $14$ could only be paired with itself or a smaller number; therefore, only people with age $15$ or above can be paired with someone of different age. Pairing consecutive numbers $(15,16), (17,18), \ldots, (99,100)$ works, giving $\frac{100-14}{2} = 43$ pairs.

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.