IMO shortlist 1985/25 solution

26th IMO 1985 shortlist

Problem 25

34 countries each sent a leader and a deputy leader to a meeting. Some of the participants shook hands before the meeting, but no leader shook hands with his deputy. Let S be the set of all 68 participants except the leader of country X. Every member of S shook hands with a different number of people (possibly zero). How many people shook hands with the leader or deputy leader of X?

Solution

Solution by Demetres Christofides

Answer: 33.

There are 68 delegates. Each shakes hands with at most 66 others, so we can label the 67 members of S as a₀, a₁, ... , a₆₆, where a_n shakes hands with n delegates. Let L be the leader of country X. We claim that: (1) a₆₆ shakes hands with a₁, a₂, ... , a₆₅ and L, and is from the same country as a₀; (2) for n = 1, 2, ... , 32, delegate a_n shakes hands with a_67-n, a_68-n, ... , a₆₆ and is the partner of a_66-n who shakes hands with , a_n+1, a_n+2, ... , a₆₆ (except himself) and L, (3) the deputy leader is a₃₃, (4) L shakes hands with a₃₄, a₃₅, ... , a₆₆.

Note that a₆₆ shakes hands with everyone except himself and the other delegate from his country. a₀ does not shake hands with anyone, and hence in particular does not shake hands with a₆₆, so they must be from the same country. That establishes (1).

We prove (2) by induction. (1) is effectively the case n = 0. Suppose it is true for all m < n < 32. Then a_66-m shakes hands with a_n (by induction) for m = 0, 1, ... , n-1. That accounts for all n people who shake hands with a_n. Similarly, a_m does not shake hands with a_66-n, which gives n people who do not shake hands with a_66-n. We have just established that a_n does not and a_66-n himself does not, so we have n+2 people who do not, and hence at most 68-(n+2) = 66-n who do. So the n+2 people are the only people who do not. The only candidate for the partner of a_66-n is a_n. That establishes the case n. So by induction it is true for n = 1, 2, ... , 32.

The only person unaccounted for, who could be L's partner is a₃₃. That establishes (3). We establish (4) by inspection of (1) and (2). Finally, we note that a₀, a₁, ... , a₃₂ do not shake hands with L or a₃₃, whereas a₃₄, a₃₅, ... , a₆₆ shake hands with both a₃₃ and L.

26th IMO shortlist 1985