Given a finite set $X$, two positive integers $n,k$, and a map $f:X\to X$. Define $f^{(1)}(x)=f(x),f^{(i+1)}(x)=f^{(i)}(x)$,$i=1,2,3,\ldots$. It is known that for any $x\in X$,$f^{(n)}(x)=x$. Define $m_j$ the number of $x\in X$ satisfying $f^{(j)}(x)=x$. Prove that: (1)$\frac{1}n \sum_{j=1}^n m_j\sin {\frac{2kj\pi}{n}}=0$ (2)$\frac{1}n \sum_{j=1}^n m_j\cos {\frac{2kj\pi}{n}}$ is a non-negative integer.
Problem
Source: 2017 CGMO P6
Tags: number theory, algebra, roots of unity
smy2012
14.08.2017 17:28
This structure also appears in IMO Shortlist 2009 N5
smy2012
14.08.2017 17:34
Call the smallest integer $i$ satisfying $f^{(i)}(x)=x$ the length of $x$. The length of any $x$ must divide $n$. The number of $x$ with length $d$ is also divided by $d$. Define $dt_d$ the number of $x$ with length $d$ ($t_d\in\mathbb{N}$,$d=1,2,\ldots$).Then we have $m_k=\sum_{d|k} dt_d$. Pick any $\zeta$ satisfying $\zeta^n=1$,we only need to prove $\displaystyle\frac{1}n\sum_{k=1}^n m_k\zeta^k\in\mathbb{N}$. \begin{align} \frac{1}n\sum_{k=1}^n m_k\zeta^k&=\frac{1}n\sum_{k=1}^n (\sum_{d|k} dt_d)\zeta^k\\ &=\frac1n \sum_{d|k,1\le k\le n} dt_d\zeta^k\\ &=\frac1n \sum_{d|n}(\sum_{d|k,1\le k\le n} dt_d\zeta^k)\\ &=\sum_{d|n} t_d(\frac{d}n\sum_{j=1}^{n/d} \zeta^{dj})\in\mathbb{N} \end{align}(3) is true, because for $d\nmid n$,$t_d=0$. (4) is true, because for $d\mid n$,we have $\dfrac{d}n\sum_{j=1}^{n/d} \zeta^{dj}=0$ or $1$. This completes the solution.
rafayaashary1
14.08.2017 22:19
As always, drawing a picture is critical. In this case consider the digraph on $X$ induced by the action of $f$. It is not hard to show that each connected component is a set of trees funneling into a single cycle. The rest is just simple NT (only the cycles matter) and computation.
khbghvb
19.12.2017 14:19
It was very easy
khbghvb
19.12.2017 14:19
khbghvb wrote: It was very easy Took me thirty minutes to solve