Competition problem — Combinatorics

Combinatorics Difficulty 8.0 National Olympiad, round 2 Prove it United States

In a group of people, some are friends (friendship is mutual) and each person $p$ has a list $f_1(p), f_2(p), \dots, f_{d(p)}(p)$ of their friends, where $d(p)$ is the number of friends $p$ has. Additionally, any two people are connected by a series of friendships. Each person also has a water balloon. The following game is played until someone ends up with more than one water balloon: on round $r$ , each person $p$ throws the current water balloon they have to their friend $f_s(p)$ such that $d(p) \mid r - s$ . Show that if the game never ends, then everyone has the same number of friends.

Solution

Given a person $p$ , let $F(p)$ be the set of friends of $p$ . Choose a person $p$ with the most friends. Note that for each friend $q$ of $p$ , $p$ receives a water balloon from $q$ once out of every $d(q)$ turns. Since $p$ always receives 1 water balloon, we must have
$\sum_{q \in F(p)} \frac{1}{d(q)} = 1.$
Since this sum has $d(p)$ terms, and since $d(q) \le d(p)$ for all $q$ , we have
$1 \ge d(p) \cdot \frac{1}{d(p)} = 1.$
Thus we must have equality for all friends $q$ of $p$ . In particular, $d(q) = d(p)$ . Thus all friends of any person with the most number of friends also have the most number of friends.

Again, let $p$ be a person with the most friends. Now for any other person $q$ , there exists a sequence of people $p = p_0, p_1, \dots, p_n = q$ . Repeatedly applying the previous result gives us $d(p) = d(p_0) = d(p_1) = \dots = d(p_n) = d(q)$ . Thus any person has the maximum number of friends out of the group, which means that each person has the same number of friends. ■

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.