IMO 1995 SL N5

Origin: IRE | Category: Number Theory

Problem

At a meeting of 12k people, each person exchanges greetings with exactly 3k + 6 others. For any two people, the number who exchange greetings with both is the same. How many people are at the meeting?

Solution

For each two people let n be the number of people exchanging greetings with both of them. To determine n in terms of k, we shall count in two ways the number of triples (A, B, C) of people such that A exchanged greetings with both B and C, but B and C mutually did not. There are 12k possibilities for A, and for each A there are (3k + 6) possi- bilities for B. Since there are n people who exchanged greetings with both

A and B, there are 3k + 5 −n who did so with A but not with B. Thus the number of triples (A, B, C) is 12k(3k + 6)(3k + 5 −n). On the other hand, there are 12k possible choices of B, and 12k −1 −(3k + 6) = 9k −7 possible choices of C; for every B, C, A can be chosen in n ways, so the number of considered triples equals 12kn(9k −7). Hence (3k + 6)(3k + 5 −n) = n(9k −7), i.e., n = 3(k+2)(3k+5) 12k−1 . This gives us that 4n 3 = 12k2+44k+40 12k−1 = k + 4 −3k−44 12k−1 is an integer too. It is directly verified that only k = 3 gives an integer value for n, namely n = 6. Remark. The solution is complete under the assumption that such a k exists. We give an example of such a party with 36 persons, k = 3. Let the people sit in a 6 \times 6 array [Pij]6 i,j=1, and suppose that two persons Pij, Pkl exchanged greetings if and only if i = k or j = l or i −j \equivk −l (mod 6). Thus each person exchanged greetings with exactly 15 others, and it is easily verified that this party satisfies the conditions.