IMO 1983 SL 22

Origin: SWE

Problem

Let n be a positive integer having at least two different prime factors. Show that there exists a permutation a1, a2, . . . , an of the integers 1, 2, . . . , n such that n  k=1 k \cdot cos 2\piak n = 0.

Solution

Decompose n into n = st, where the greatest common divisor of s and t is 1 and where s > 1 and t > 1. For 1 \leqk \leqn put k = vs + u, where 0 \leqv \leqt −1 and 1 \lequ \leqs, and let ak = avs+u be the unique integer in the set {1, 2, 3, . . ., n} such that vs + ut −avs+u is a multiple of n. To prove that this construction gives a permutation, assume that ak1 = ak2, where ki = vis + ui, i = 1, 2. Then (v1 −v2)s + (u1 −u2)t is a multiple of n = st. It follows that t divides (v1 −v2), while |v1 −v2| \leqt −1, and that s divides (u1 −u2), while |u1 −u2| \leqs −1. Hence, v1 = v2, u1 = u2, and k1 = k2. We have proved that a1, . . . , an is a permutation of {1, 2, . . ., n} and hence

n  k=1 k cos 2\piak n

t−1  v=0

s  u=1 (vs + u) cos 2\piv t

• 2\piu s  . Using s u=1 cos(2\piu/s) = s u=1 sin(2\piu/s) = 0 and the additive formu- las for cosine, one finds that n  k=1 k cos 2\piak n = t−1  v=0

cos 2\piv t s  u=1 u cos 2\piu s −sin 2\piv t s  u=1 u sin 2\piu s

=

s  u=1 u cos 2\piu s

t−1  v=0 cos 2\piv t

−

s  u=1 u sin 2\piu s

t−1  v=0 sin 2\piv t

= 0.