38th BMO 2002 Problem 2 n people wish to sit at a round table which has n chairs. The first person takes an seat. The second person sits one place to the right of the first person, the third person sits two places to the right of the second person, the fourth person sits three places to the right of the third person and so on. For which n is this possible? Solution
: n = 2 m for m a non-negative integer. Label the seats 0, 1, 2, ... , n-1. The kth person sits in seat k(k - 1)/2 for k = 1, 2, ... , n. So the seating plan is possible iff the n numbers k(k - 1)/2 are incongruent mod n for k = 1, 2, ... , n. Suppose first that n = 2 m . We have h(h - 1)/2 - k(k - 1)/2 = (h - k)(h + k - 1)/2. If h and k are unequal, then h - k and (h + k - 1) are non-zero. But they have opposite parity, and both are less than 2n, so one is odd and the other is not divisible by a higher power of 2 than 2 m . Thus (h - k)(h + k - 1)/2 cannot be divisible by 2 m . So the seating plan works for n a power of 2. Conversely, suppose n = 2 m (2a + 1). If a  2 m , then take h = 2 m + a + 1, k = a - 2 m + 1. Then h - k = 2 m+1 , h + k - 1 = 2a + 1. So again h(h - 1)/2 and k(k - 1)/2 are equal mod n. So no seating plan is possible if n is not a power of 2. 38th BMO 2002 © John Scholes jscholes@kalva.demon.co.uk 9 Jul 2002