Let $n$ be a positive integer having at least two different prime factors. Show that there exists a permutation $a_1, a_2, \dots , a_n$ of the integers $1, 2, \dots , n$ such that \[\sum_{k=1}^{n} k \cdot \cos \frac{2 \pi a_k}{n}=0.\]
Problem
Source:
Tags: trigonometry, number theory, equation, Trigonometric Equations, Trigonometric Identities, IMO Shortlist
28.02.2012 16:29
Let $n=r.s$, where $\gcd(r,s) = 1$. Denote: $\theta=\frac{2\pi}{n}$, $M=\left\{z|\, z \in \mathbb{C},\, z=e^{ik\theta}, k=1,2,\cdots,n \right\} $, $M_0 = \left\{e^{i(ks\theta)}|\, k=1,2,\cdots,r \right\} $ $M_l = e^{i(lr\theta)}.M_0,\, l=0,1,\cdots,s-1 $. Let $\psi:\, M \to \{1,2,\cdots,n\},\, \psi(e^{ik\theta})= k,\, k=1,2,\cdots,n$. First to make certain that $M_{l_1} \cap M_{l_2} = \emptyset,\, l_1 \neq l_2$. Assume that: $ l_1r\theta + k_1s \theta = l_2 r \theta + k_2 s \theta,\, 1\leq k_1, k_2 \leq r, 0 \leq l_1,l_2 \leq s-1 \, \Rightarrow$ $ (l_1-l_2)r=(k_2-k_1) s \, \Rightarrow \, l_1=l_2, k_1=k_2 $. If $ z \in M_l$, and $z= e^{i(lr\theta)}.z_0$, where $ z_0 \in M_0$, define $\sigma(z) = \psi(z_0)+l$ (when $\psi(z_0)=n$, we consider $n+l$ to be just $l$). Hence $\sigma$ is defined on $M$ and $\{\sigma(z)\}_{z \in M }$ is a permutation of $1,2,\cdots,n$. Our next aim is to calculate $\sum_{z \in M} z.\sigma(z)$. Denote $\omega_0 = \sum_{z \in M_0} z.\psi(z)$. (1) $\sum_{z \in M} z.\sigma(z) = \sum_{l=0}^{s-1} \, \sum_{z \in M_l} z.\sigma(z) = \sum_{l=0}^{s-1} e^{i lr\theta} \sum_{z \in M_0} z.\left(\psi(z) + l \right) = \sum_{l=0}^{s-1} e^{i lr\theta}.\omega_0 = 0.$ If we take the real parts of (1), will get that there exists a permutation $\sigma$ of integers $1,2,\cdots,n$, such that: (2) $\sum_{k=1}^n \sigma(k). cos \frac{2\pi k}{n} = 0 $ Finally, (2) is equivalent to the problem's statement.