Let $P(x)$ be a polynomial with integer coefficients that has at least one rational root. Let $n$ be a positive integer. Alan and Allan are playing a game. First, Alan writes down $n$ integers at $n$ different locations on a board. Then Allan may make moves of the following kind: choose a position that has integer $a$ written, then choose a different position that has integer $b$ written, then at the first position erase $a$ and in its place write $a+P(b)$. After any nonnegative number of moves, Allan may choose to end the game. Once Allan ends the game, his score is the number of times the mode (most common element) of the integers on the board appears. Find, in terms of $P(x)$ and $n$, the maximum score Allan can guarantee. Henrick Rabinovitz
Problem
Source: ELMO Shortlist 2024/N9
Tags: Elmo, number theory
22.06.2024 19:01
Here is a write-up done with pieater314159 and numbersandnumbers
08.07.2024 05:19
5 observation before going for solution Case 1- $ P(x) = 0$ In this case, the game is trivial, and Allan can guarantee a score of $1$ by simply not making any moves. This is because the polynomial $P(x) = 0$ has no roots $,$ so there are no moves that can be made to change the integers on the board. Case 2- $P(x) = ax + b, \gcd(a, b) = 1$ In this case, Allan can guarantee a score of $n-1$ by using the following strategy Alan writes down n distinct integers at $n$ different locations on the board Allan chooses a position with integer a and a different position with integer $b,$ and applies the move $a + P(b)$ to the first position Allan repeats the previous step until all integers on the board are equal Cuse the move $a + P(b)$ preserves the gcd of the integers on the board. Since $\gcd(a, b) = 1,$ the $\gcd$ of the integers on the board remains $1$ after each move. Therefore, Allan can keep applying this move until all integers are equal. The key insight here is that the move $a + P(b)$ is essentially adding a multiple of the $\gcd$ of $a, b$ to the first integer. Since the $\gcd = 1, \implies$ the move is essentially adding $1$ to the first integer, which preserves the gcd of the integers on the board. Case 3- $P(x) = ax + b, \gcd(a, b) > 1$ In this case, Allan can guarantee a score of $\lceil\frac{n}{\gcd(a, b)}\rceil$ by using a similar strategy to Case 2, but with some additional tricks. The key insight here is that the move $a + P(b)$ preserves the gcd of the integers on the board, but also increases the number of distinct residue classes modulo $\gcd(a, b).$ By carefully choosing the moves, Allan can ensure that the number of distinct residue classes modulo $\gcd(a, b)$ is at most $c,$ where $c $ is the number of distinct residue classes modulo $\gcd(a, b)$ that are represented among the integers on the board. Since $\gcd(a, b) > 1,$ the move $a + P(b)$ increases the number of distinct residue classes modulo $\gcd(a, b)$ by at least $1.$ Therefore, Allan can keep applying this move until the number of distinct residue classes modulo $\gcd(a, b)$ is at most $c.$ At this point, Allan can guarantee that at least $\lceil \frac{n}{\gcd(a, b)}\rceil$ integers on the board are equal. Case 4- $\mathrm{deg P}\geq 2$ In this case, Allan can guarantee a score of $1$ by using a different strategy. The key insight here is that there exists a positive integer $M$ such that P has at least n roots modulo $M$. By choosing integers that are congruent to these roots $\text{modulo M},$ Allan can ensure that the integers on the board are always distinct. Cause the polynomial $P(x)$ has at least $n$ roots $\text{modulo M},\implies$ there are at least n distinct residue classes modulo M that are roots of P(x). By choosing integers that are congruent to these roots $\text{modulo M},$ Allan can ensure that the integers on the board are always distinct. Solution- $$\textbf{Claim 1-}P(x) = 0$$$\textbf{Allan can guarantee a score of 1 by not making any moves.} $ $$\textbf{Claim 2-} $$$$P(x) = ax + b, \gcd(a, b) = 1 \,\text{Allan can guarantee a score of } n-1 \text{ by using the following strategy-} $$ 1. Alan writes down distinct integers at $n$ different locations on the board. 2. Allan chooses a position with integer $a$ and a different position with integer $ b, $ $\text{ and applies the move } a + P(b) \text{ to the first position.} $ 3.$ \text{ Allan repeats the previous step until all integers on the board are equal.}$ \[P(x) = ax + b\] \[P(b) = ab + b = b(a + 1)\] Therefore$, $ the move \(a + P(b)\) is equivalent to adding \(b(a + 1)\) to the first integer. Since \(\gcd(a, b) = 1\) $,$ we know that \(a\) and \(b\) are coprime. Therefore, the move \(a + P(b)\) preserves the gcd of the integers on the board. Specifically, if the gcd of the integers on the board is \(d\) before the move, then the gcd after the move is also \(d\). Moreover, since \(a\) and \(b\) are coprime, we know that the move \(a + P(b)\) increases the value of the first integer by at least 1. Therefore, by repeatedly applying this move, Allan can ensure that all integers on the board are equal. $$\textbf{Claim 3-} P(x) = ax + b, \gcd(a, b) > 1 \,$$$\text{Allan can guarantee a score of } \lceil n/\gcd(a, b) \rceil \textbf{ by using a similar strategy to Case 2 ,but with some additional tricks.}$ The move \(a + P(b)\) still preserves the gcd of the integers on the board, but it also increases the number of distinct residue classes modulo \(\gcd(a, b)\). Specifically, if the gcd of the integers on the board is \(d\) before the move, then the gcd after the move is still \(d\), but the number of distinct residue classes modulo \(d\) increases by at least $1.$ Therefore, by carefully choosing the moves, Allan can ensure that the number of distinct residue classes modulo \(\gcd(a, b)\) is at most \(c\), where \(c\) is the number of distinct residue classes modulo \(\gcd(a, b)\) that are represented among the integers on the board. Moreover, since \(\gcd(a, b) > 1\), we know that the move \(a + P(b)\) increases the value of the first integer by at least \(\gcd(a, b)\). Therefore, by repeatedly applying this move, Allan can ensure that at least $\left(\lceil\frac{ n}{\gcd(a, b) }\rceil\right)$ integers on the board are equal. $$\textbf{Claim 4:} \deg P \geq 2 \,\text{Allan can guarantee a score of 1 by using a different strategy.}$$ There exists a positive integer \(M\) such that \(P\) has at least \(n\) roots modulo \(M\). This is because the polynomial \(P(x)\) has degree at least 2, so it has at least one root modulo \(p\) for every prime \(p\). By choosing integers that are congruent to these roots modulo \(M\), Allan can ensure that the integers on the board are always distinct. Specifically, if the integers on the board are \(x_1, \ldots, x_n\), then Allan can choose integers \(y_1, \ldots, y_n\) such that \(y_i \equiv x_i \pmod{M}\) for all \(i\). Since \(P\) has at least \(n\) roots modulo \(M\), we know that there are at least \(n\) distinct residue classes modulo \(M\) that are roots of \(P(x)\). Therefore, by choosing integers that are congruent to these roots modulo \(M\), Allan can ensure that the integers on the board are always distinct.
08.07.2024 06:16
buh $ $
08.07.2024 06:17
Not fun to read