IMO shortlist 1983/21 solution

24th IMO 1983 shortlist

Problem 21

Let n be a positive integer which is not a prime power. Show that there is a permutation a₁, a₂, ... , a_n of 1, 2, ... , n such that cos(2πa₁/n) + 2 cos(2πa₂/n) + 3 cos(2πa₃/n) + ... + n cos(2πa_n/n) = 0.

Solution

We show that a slightly stronger result is true: we can find such a permutation for n not a power of 2.

Put c_k = cos(2πk/n). We show first that for odd n = 2m+1 we have c₁ + 2c₂ + 3c₃ + ... + mc_m + (m+1)c_2m+1 + (m+2)c_m+1 + (m+3)c_m+2 + ... + (2m+1)c_2m = 0 (*). This follows almost immediately from c₁ + c₂ + ... + c_n = 0 (1), c_k = c_n-k (2) and c_n = 1 (3). (1) just says that the sum of the complex roots of 1 has zero real part (obvious from the polynomial zⁿ = 1), (2) follows from cos(-x) = cos x, and (3) is immediate. So we have c₁ + c₂ + ... + c_m = -1/2. Hence (2m+2)(c₁ + c₂ + ... + c_m) = -(m+1) = -(m+1) c_2m+1, which is (*).

Next we show that if the result is true for n, then it is also true for 2n. We show first by a similar argument to the above that c₁ + 3c₃ + 5c₅ + 7c₇ + ... + (2n-1)c_2n-1 = 0 (**). Note first that c₂ + c₄ + c₆ + ... + c_2n is just ∑ cos(2πk/n) and so is zero by (1). Subtracting from c₁ + c₂ + c₃ + ... + c_2n = 0 gives that c₁ + c₃ + c₅ + c₇ + ... + c_2n-1 = 0. But c_i = c_2n-i, so c₁ + 3c₃ + 5c₅ + 7c₇ + ... + (2n-1)c_2n-1 = (2n-1)c₁ + (2n-3)c₃ + ... + c_2n-1. Adding the two sides gives 2n x (c₁ + c₃ + ... + c_2n-1) = 0, so each side is zero, giving (**).

Now by assumption we have ∑ a_kc_k = 0 where c_k = cos(2πk/n) for some permutation a_k of 1,2,3, ... , n. So ∑ (2a_k)c_2k = 0, where c_2k = cos(2π2k/2n). Putting this together with (**) gives the result for 2n.

Thanks to Lauri Ahlroth for this

24th IMO shortlist 1983