IMO 1999 SL A3

Origin: FIN | Category: Algebra

Problem

A game is played by n girls (n \geq2), everybody having a ball. Each of the
n  pairs of players, in an arbitrary order, exchange the balls they have at that moment. The game is called nice if at the end nobody has her own ball, and it is called tiresome if at the end everybody has her initial ball. Determine the values of n for which there exists a nice game and those for which there exists a tiresome game.

Solution

A game is determined by the ordering t1, . . . , tN of the N =
n  transpo- sitions (i, j) of the set {1, 2, . . ., n}. The game is nice if the permutation P = tNtN−1 . . . t1 has no fixed point, and tiresome if P is the identity (denoted by I). Recall that every permutation can be written as a com- position of disjoint cycles. We claim that there exists a nice game if and only if n ̸= 3. For n = 2, P2 = t1 = (1, 2) is obviously nice. For n = 3 each game has the form P = (b, c)(a, c)(a, b) = (a, c) for an appropriate nota- tion of the players, which cannot be nice. Now for n \geq4 we define

Pn = (1, 2)(1, 3)(2, 3) \cdot \cdot \cdot(1, n)(2, n) \cdot \cdot \cdot (n −1, n). We obtain inductively that Pn = Pn−1(1, n, n −1, . . . , 2) = (1, n)(2, n −1) \cdot \cdot \cdot (i, n + 1 −i) \cdot \cdot \cdot is nice for all even n. Also, if n = 2k+1 is odd, then Qn = Pn−1(1, n)(2, n) \cdot \cdot \cdot (k, n)(n−1, n)(n− 2, n) \cdot \cdot \cdot (k + 1, n) maps i to n + 1 −i for i \leqk, to n −1 −i for k + 1 \leq i \leq2k −1, and to 3k + 1 −i if i \in{2k, 2k + 1}. Hence Qn is nice. This justifies our claim. Now we prove that a tiresome game exists if and only if n \equiv0, 1 (mod 4). Evidently every transposition changes the sign of the permutation. Thus the sign of P is (−1)( n 2) and for P to be the identity we must have 2 |
n  ⇒n \equiv0, 1(mod 4). Let us now construct tiresome games for the allowed n. For n = 4k we divide the girls into groups of 4. In each group we perform the following game: (3, 4)(1, 3)(2, 4)(2, 3)(1, 4)(1, 2) = I. On the other hand, among two different groups (call them {1, 2, 3, 4} and {5, 6, 7, 8}) we perform (4, 7)(3, 7)(4, 6)(1, 6)(2, 8)(3, 8)(2, 7)(2, 6) (4, 5)(4, 8)(1, 7)(1, 8)(3, 5)(3, 6)(2, 5)(1, 5) = I. For n = 4k + 1 we divide into groups of four as before, with one girl remaining. Every time a group (denoted {1, 2, 3, 4}) is to play a game the remaining girl (denoted 5) joins in, and they play (3, 5)(3, 4)(4, 5)(1, 3)(2, 4)(2, 3)(1, 4)(1, 5)(1, 2)(2, 5) = I. This completes the proof.