Problem A. 904. (March 2025)
A. 904. Let \(\displaystyle n\) be a given positive integer. Luca, the lazy flea sits on one of the vertices of a regular \(\displaystyle 2n\)-gon. For each jump, Luca picks an axis of symmetry of the polygon, and reflects herself on the chosen axis of symmetry. Let \(\displaystyle P(n)\) denote the number of different ways Luca can make \(\displaystyle 2n\) jumps such that she returns to her original position in the end, and does not pick the same axis twice. (It is possible that Luca's jump does not change her position, however, it still counts as a jump.) a) Find the value of \(\displaystyle P(n)\) if \(\displaystyle n\) is odd. b) Prove that if \(\displaystyle n\) is even, then \(\displaystyle P(n)=(n-1)!\cdot n!\cdot \sum_{d\mid n,d\in \mathbb{N}}\left(\varphi\left (\dfrac{n}{d}\right) \cdot \binom{2d}{d} \right)\), where \(\displaystyle \varphi(k)\) denotes the number of positive integers not greater than \(\displaystyle k\) that are coprime to \(\displaystyle k\).
Proposed by: Péter Csikvári and Kartal Nagy, Budapest
(7 pont)
Deadline expired on April 10, 2025.
Let's mark the vertices of the polygon with numbers \(\displaystyle 1,2,...,2n\). A reflection symmetry can be describe using an integer number \(\displaystyle a\), where \(\displaystyle a\) takes values \(\displaystyle 1,2,...,2n\), and the image of vertex \(\displaystyle x\) is \(\displaystyle a-x\) modulo \(\displaystyle 2n\). Therefore the question can be rephrased as find those permutations \(\displaystyle a_1,a_2,...,a_{2n}\) of numbers \(\displaystyle 1,2,...,2n\), for which \(\displaystyle L=a_{2n}-(a_{2n-1}-(...-(a_2-(a_1-L))))\) modulo \(\displaystyle 2n\) (where \(\displaystyle L\) denotes Luca's original position). Breaking up the brackets results in \(\displaystyle L=L+(a_{2n}-a_{2n-1}+...+a_2-a_1)\) modulo \(\displaystyle 2n\), i.e. \(\displaystyle a_{2n}-a_{2n-1}+....+a_2-a_1=0\) modulo \(\displaystyle 2n\).
a. We prove that if \(\displaystyle n\) is odd, we cannot get \(\displaystyle 0\) modulo \(\displaystyle 2n\). \(\displaystyle 1+2+...+2n=n(2n+1)=n\) modulo \(\displaystyle 2n\), however, if \(\displaystyle a_1+a_3+..+a_{2n-}=a_2+a_4+...+a_{2n}=x\) modulo \(\displaystyle 2n\), thus \(\displaystyle 2x=n\) modulo \(\displaystyle 2n\), which is clearly impossible, if \(\displaystyle n\) is odd. Therefore \(\displaystyle P(n)=0\).
b. Using the previous part we get that \(\displaystyle x=n/2\) modulo \(\displaystyle n\), therefore we have to count the number of ways we can pick \(\displaystyle n\) numbers from \(\displaystyle 1,2,...,2n\) such that their sum equals \(\displaystyle m=n/2\) modulo \(\displaystyle n\). Our strategy will be counting the number of ways we can get a sum that is divisible by \(\displaystyle m=n/2\), and subtract the number of those sums which are divisible by \(\displaystyle n\).
Let's consider the two-variable polynomial
\(\displaystyle p(x,y)=\prod_{i=1}^{2n}(1+x^iy). \)
In this polynomial the coefficient of \(\displaystyle x^ay^b\) equals the number of ways we can pick \(\displaystyle b\) numbers from \(\displaystyle 1,2,...,2n\) such that their sum equals \(\displaystyle a\). Therefore we want to find the sum of the coefficients of \(\displaystyle x^iy^n\) where \(\displaystyle i\) takes the values of the multiples of \(\displaystyle m=n/2\). Let \(\displaystyle \omega\) be a primitive root of unity of order \(\displaystyle m=n/2\). We claim that in polynomial
\(\displaystyle \frac{1}{m}\sum_{k=1}^mp(\omega^k,y) \)
the coefficient of \(\displaystyle y^n\) equals the number we are looking for. The reason for this is the well known fact that \(\displaystyle \sum_{k=1}^m\omega^{ak}\) is \(\displaystyle 0\), if \(\displaystyle a\) is not divisible by \(\displaystyle m\), otherwise it's \(\displaystyle m\). Our next aim is to find \(\displaystyle p(\omega^k,y)\). Let \(\displaystyle \xi\) be a primitive root of unity of order \(\displaystyle d\), where \(\displaystyle d|2n\). From the well known identity \(\displaystyle z^d-1=(z-1)(z-\xi)(z-\xi^2)...(z-\xi^{d-1})\) we get that \(\displaystyle \prod_{i=1}^d=(1+\xi^iy)=1-(-1)^dy^d\). Since the powers of \(\displaystyle \xi\) follow a cyclic pattern, we get that \(\displaystyle p(\xi,y)=(1+(-1)^{d+1}y^d)^\frac{2n}{d}\). We are done, since \(\displaystyle \omega^k\) is a primitive root of order \(\displaystyle \frac{m}{\text{gcd}(k,m)}\).
Now let's try to find the coefficient of \(\displaystyle y^n\) in polynomial \(\displaystyle \frac{1}{m}\sum_{k=1}^m p(\omega^k,y)\). In polynomial \(\displaystyle (1+(-1)^{d+1}y^d)^\frac{2n}{d}\) the coefficient of \(\displaystyle y^n\) is \(\displaystyle (-1)^\frac{n(d+1)}{d}\binom{2n/d}{n/d}\) based on the binomial theorem (if \(\displaystyle d|n\), otherwise we get 0). Now we have to count how many times will \(\displaystyle \omega^k\) be a primitive root of order \(\displaystyle d\) (we note that since \(\displaystyle d\) has to divide \(\displaystyle m=n/2\), this means that the exponent of \(\displaystyle (-1)\) is even, since \(\displaystyle n/d\) is already even): the condition for this is that \(\displaystyle \text{gcd}(k,m)=m/d\), therefore \(\displaystyle k\) is a product of \(\displaystyle m/d\) and a number between \(\displaystyle 1\) and \(\displaystyle d\) that is relatively prime to \(\displaystyle d\), thus \(\displaystyle \varphi(d)\) times. Finally the coefficient we are looking for is
\(\displaystyle \frac{1}{m}\sum_{d|m}\varphi(d)\binom{2n/d}{n/d}=\frac{1}{m}\sum_{d'|m}\varphi(m/d')\binom{4d'}{2d'}=\frac{1}{m}\sum_{d''|n,\,d''\text{ is even}}\varphi(n/d'')\binom{2d''}{d''}. \)
Now if we want to find the number of ways to get a sum that is divisible by \(\displaystyle n\), we can follow a similar method. Now \(\displaystyle \omega\) is a primitive root of unity of order \(\displaystyle n\). The minor difference compared to the earlier calculation is that \(\displaystyle (-1)^\frac{n(d+1)}{d}\) can also be -1: if \(\displaystyle d''=n/d\) is odd, then \(\displaystyle d\) is even, thus the exponent is odd (in other words, we get \(\displaystyle -1\) if \(\displaystyle d\) divides \(\displaystyle n\), but does not divide \(\displaystyle n/2\), notably there are the divisors that were missing in our earlier sum). Thus we get that the number of sums divisible by \(\displaystyle n\) is
\(\displaystyle \frac{1}{n}\sum_{d|n}(-1)^{\frac{n(d+1)}{d}}\varphi(d)\binom{2n/d}{n/d}=\frac{1}{n}\sum_{d''|n}(-1)^{d''}\varphi(n/d'')\binom{2d''}{d''}. \)
Now we are ready to finish our argument: the difference of the two above sums is
\(\displaystyle \left(\frac{1}{m}-\frac{1}{n}\right)\sum_{d|n,d \text{ is even}}\varphi(n/d)\binom{2d}{d}+\frac{1}{n}\sum_{d|n,d \text{ is odd}}\varphi(n/d)\binom{2d}{d}, \)
and this is exactly the statement we wanted to prove since \(\displaystyle 1/m-1/n=2/n-1/n=1/n\), and the numbers of ways to permute the \(\displaystyle n\) chosen numbers and their complement is \(\displaystyle n!\cdot n!\) (note that a non-trivial consequence of this solution is that if we compose line reflections over concurrent axes, the order of the reflections at the odd and at the even positions, respectively, can be arbitrarily permuted, and we will still get the same result).
Statistics:
11 students sent a solution. 7 points: Bodor Mátyás, Varga Boldizsár. 6 points: Xiaoyi Mo. 5 points: 1 student. 3 points: 1 student. 2 points: 2 students. 1 point: 4 students.
Problems in Mathematics of KöMaL, March 2025