Problem A. 886. (September 2024)

A. 886. Let \(\displaystyle k\) and \(\displaystyle n\) be two given distinct positive integers greater than 1. There are finitely many (not necessarily distinct) integers written on the blackboard. Kázmér is allowed to erase \(\displaystyle k\) consecutive elements of an arithmetic sequence with a difference not divisible by \(\displaystyle k\). Similarly, Nándor is allowed to erase \(\displaystyle n\) consecutive elements of an arithmetic sequence with a difference that is not divisible by \(\displaystyle n\). The initial numbers on the blackboard have the property that both Kázmér and Nándor can erase all of them (independently from each other) in a finite number of steps. Prove that the difference of biggest and the smallest number on the blackboard is at least \(\displaystyle \varphi(n)+\varphi(k)\), where \(\displaystyle \varphi\) denotes Euler's totient function, i.e., \(\displaystyle \varphi(n)\) is the number of positive integers not exceeding \(\displaystyle n\) that are coprime to \(\displaystyle n\).

Proposed by Boldizsár Varga, Budapest

(7 pont)

Deadline expired on October 10, 2024.

If we increase or decrease each number by the same amount, it does not change the erasability or the difference between the largest and smallest numbers, so we can assume that the smallest number is 0. In this case, we need to prove that the largest number is at least \(\displaystyle \varphi(n) + \varphi(k)\).

Let the written numbers (with multiplicity) be in some order \(\displaystyle a_1, a_2, \ldots, a_m\). Consider the polynomial \(\displaystyle \sum_{i=1}^m x^{a_i}\). Notice that every primitive \(\displaystyle k\)-th complex root of unity is a root of this polynomial, because if we partition the elements into arithmetic sequences that Kázmér has erased, then for every arithmetic sequence \(\displaystyle a_i, a_i+d, a_i+2d, \ldots, a_i+(k-1)d\) (where we know that \(\displaystyle k \nmid d\)), the corresponding polynomial is \(\displaystyle x^{a_i} + x^{a_i+d} + \cdots + x^{a_i+(k-1)d}\) (this sum of these is the original polynomial). Substituting a primitive \(\displaystyle k\)-th root of unity \(\displaystyle \varepsilon\), we get \(\displaystyle \varepsilon^{a_i} \cdot \left( 1 + \varepsilon^d + \varepsilon^{2d} + \cdots + \varepsilon^{(k-1)d} \right) = \varepsilon^{a_i} \cdot \frac{\varepsilon^{kd} - 1}{\varepsilon^d - 1} = 0\). Since \(\displaystyle \varepsilon\) is a primitive root of unity, \(\displaystyle \varepsilon^d - 1 \neq 0\). Based on this reasoning, the polynomial has all \(\displaystyle \varphi(k)\) primitive \(\displaystyle k\)-th roots of unity as roots, and similarly, it also has all \(\displaystyle \varphi(n)\) primitive \(\displaystyle n\)-th roots of unity as roots. However, due to primitiveness, none of these roots coincide, so the polynomial has at least \(\displaystyle \varphi(k) + \varphi(n)\) distinct roots. By definition, the polynomial is not identically zero, which implies that its degree must be at least \(\displaystyle \varphi(k) + \varphi(n)\). Thus, the largest number written on the board must be at least this large, which is exactly what we wanted to prove.

Statistics:

9 students sent a solution.
7 points:	Bodor Mátyás, Forrai Boldizsár, Szakács Ábel, Tianyue DAI, Varga Boldizsár.
2 points:	2 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, September 2024