Library / /660 of 740

, 2023

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

An HMMT party has $m$ MIT students and $h$ Harvard students for some positive integers $m$ and $h$ . For every pair of people at the party, they are either friends or enemies. If every MIT student has 16 MIT friends and 8 Harvard friends, and every Harvard student has 7 MIT enemies and 10 Harvard enemies, compute how many pairs of friends there are at the party.

Solution

Solution:

We count the number of MIT-Harvard friendships. Each of the $m$ MIT students has 8 Harvard friends, for a total of $8m$ friendships. Each of the $h$ Harvard students has $m-7$ MIT friends, for a total of $h(m-7)$ friendships. So, $8m = h(m-7) \Longrightarrow mh - 8m - 7h = 0 \Longrightarrow (m-7)(h-8) = 56$ .

Each MIT student has 16 MIT friends, so $m \geq 17$ . Each Harvard student has 10 Harvard enemies, so $h \geq 11$ . This means $m-7 \geq 10$ and $h-8 \geq 3$ . The only such pair $(m-7, h-8)$ that multiplies to 56 is $(14, 4)$ , so there are 21 MIT students and 12 Harvard students.

We can calculate the number of friendships as $\frac{16m}{2} + 8m + \frac{(h-1-10)h}{2} = 168 + 168 + 6 = 342$ .

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.