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
: 33. There are 68 delegates. Each shakes hands with at most 66 others, so we can label the 67 members of S as a 0 , a 1 , ... , a 66 , where a n shakes hands with n delegates. Let L be the leader of country X. We claim that: (1) a 66 shakes hands with a 1 , a 2 , ... , a 65 and L, and is from the same country as a 0 ; (2) for n = 1, 2, ... , 32, delegate a n shakes hands with a 67-n , a 68-n , ... , a 66 and is the partner of a 66-n who shakes hands with , a n+1 , a n+2 , ... , a 66 (except himself) and L, (3) the deputy leader is a 33 , (4) L shakes hands with a 34 , a 35 , ... , a 66 . Note that a 66 shakes hands with everyone except himself and the other delegate from his country. a 0 does not shake hands with anyone, and hence in particular does not shake hands with a 66 , 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 33 . That establishes (3). We establish (4) by inspection of (1) and (2). Finally, we note that a 0 , a 1 , ... , a 32 do not shake hands with L or a 33 , whereas a 34 , a 35 , ... , a 66 shake hands with both a 33 and L. 26th IMO shortlist 1985 © John Scholes jscholes@kalva.demon.co.uk 11 Sep 2002