AoPS - Problem

Problem

Source: ELMO Shortlist 2024/N9

Tags: Elmo, number theory

IAmTheHazard

22.06.2024 18:53

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

MarkBcc168

22.06.2024 19:01

Here is a write-up done with pieater314159 and numbersandnumbers

The answer is \[\begin{cases} 1 & P(x)=0 \\ n-1 & P(x)=ax+b,\ \gcd(a,b)=1 \\ \left\lceil \frac{n}{\gcd(a, b)} \right\rceil & P(x)=ax+b,\ \gcd(a,b)>1 \\ 1 & \deg P\geq 2. \end{cases}\]The problem is evident when $P$ is constant. Proof for $\boldsymbol{\deg P\geq 2}$ We will show that we can find some positive integer $M$ for which $P$ has at least $n$ roots $r_1,\ldots,r_n$ modulo $M$. Once we have shown this, Alan can pick one integer from each residue class $r_i$, and as the integers will then be invariant modulo $M$, they will always be distinct. To find such an $M$, take a linear factor $ax+b$ of $P$, and let $P(x) = (ax+b)^kQ(x)$ where $k$ is maximal. If $Q$ is not constant, then we claim there exist infinitely many primes $p$ such that $P$ has at least two roots modulo $p$. Indeed, by Schur's theorem there are infinitely many primes $p$ such that $Q$ has a root mod $p$, and since $Q(-b/a) \neq 0$, for all but finitely many such $p$ the value $-b/a$ is a root of $P$ that is not a root of $Q$. We can then choose $M$ to be a product of many of these primes. If $Q$ is constant, then $P(x) = c(ax+b)^k$ where $k\geq 2$, in which case $P(x)$ will have at least $p$ roots modulo $p^2$ for all primes $p>\max(|a|,|b|)$. So, taking $M=p^2$ for some large prime $p$ suffices. Upper Bound for $\boldsymbol{\deg P = 1}$ Write $P(x) = c(ax + b)$ where $\gcd(a,b) = 1$, $c > 0$. If $c>1$, then Allen's movement is invariant modulo $c$, so Alan just needs to make the numbers as spread modulo $c$ as possible. If $c=1$ and $a>0$, then Alan can choose all the numbers not all equal and all greater than $k = \max(0, -bc)$. Since $P(k) \geq 0$, the numbers will always be greater than $k$. Moreover, if Allen operates on $x$ and $y$, then we have $x + P(y) \geq x + (y + cb) > y$, so the two resulting integers are not equal. Thus, it is impossible to ever make the integers all equal. If $c=1$ and $a<0$, then Alan can pick some numbers strictly greater than the root of $P$ and some numbers strictly less than the root of $P$. There is never a move that removes the last number strictly greater than the root of $P$, and there is never a move that removes the last number strictly less than the root of $P$, so there is always at least one pair of distinct numbers, giving an upper bound of $n - 1$ as well. Construction for $\boldsymbol{\deg P=1}$ Write $P(x) = c(ax + b)$ where $\gcd(a,b) = 1$, $c > 0$, and $a$, $b$, and $c$ are integers. It suffices to consider $n\geq 3$. Let the set of numbers be $x_1,\dots,x_n$. The operation $(x,y) \mapsto (x+P(y),y)$ does not change the quantity $\gcd(P(x), P(y))$. Thus, $v \coloneq \gcd(P(x_1), P(x_2), \ldots, P(x_n))$ is fixed throughout. We make the following key claim. Claim. Suppose the numbers on the board are $y_1,\ldots,y_m$ for $m \geq 3$. Let $v=\gcd(P(y_1),\ldots,P(y_m))$. If $y_1\equiv y_2\pmod v$, then Allen can make (the numbers in the positions holding) $y_1$ and $y_2$ equal without changing any of $y_3,\ldots,y_m$. Proof. Let $w=\gcd(P(y_3),\ldots,P(y_m))$, so that $v=\gcd(P(y_1),P(y_2),w)$. We first do the following two moves: Change $y_1$ to $y_1' \coloneq y_1 + \ell P(y_2)$, where $\ell$ is to determined later. Change $y_2$ to $y_2' \coloneq y_2 + kP(y_1')$ for some $k$. As $k$ ranges through positive integers, the value of $y_2'\bmod \gcd(P(y_2),w)$ varies on an arithmetic progression of common difference $v$ (i.e., we can get anything $\equiv y_2\pmod v$). Thus, since $y_2\equiv y_1\pmod v$, we may pick $k$ such that $y_2'\equiv y_1\pmod{\gcd(P(y_2),w)}$, and thus, we have $\gcd(P(y_2'), P(y_2), w) = v$. Now, we can turn $y_1' = y_1+\ell P(y_2)$ to $y_1 + \ell P(y_2) + e_2 P(y_2') + e_3P(y_3) +\dots + e_nP(y_n)$ for any positive integers $\ell$, $e_2$, $\dots$, $e_n$. Thus, by Bezout, we can add any sufficiently large multiple of $v$ to $y_1$, and consequently we can make turn $y_1'$ to $y_1^*\equiv y_2'\pmod w$. Finally, add a linear combination of $P(y_3),\dots,P(y_n)$ to $y_1^*$ and $y_2'$ to make them equal. $\blacksquare$ Claim. At most $c$ residue classes modulo $v$ are represented among the numbers on the board. Proof. Since $\gcd(a,b)=1$, \begin{align*} v &=\gcd\big(c(ax_1+b),c(ax_2+b),\ldots,c(ax_n+b)\big)\\ &=c\cdot\gcd(ax_1+b,ax_2+b,\ldots,ax_n+b)\\ &=c\cdot\gcd\big(ax_1+b,a(x_2-x_1),\ldots,a(x_n-x_1)\big)\\ &=c\cdot\gcd(ax_1+b,x_2-x_1,\ldots,x_n-x_1). \end{align*}So, $v$ divides $c(x_i-x_j)$ for each $i$ and $j$, meaning that the $x_i$ all lie in the same residue class modulo $v/c$. $\blacksquare$ Given these two claims, we now describe Allen's strategy. We first describe the strategy in the case where $c=1$. By the second claim, all of the numbers on the board are equivalent modulo $v$. Let $x_i$ denote the number in position $i$; $x_i$ can change over time. First, apply the first claim to the numbers $(x_1,\ldots,x_n)$. After this, $x_1=x_2$. Now, apply the first claim to the numbers $(x_2,\ldots,x_n)$; after this $x_2=x_3$. Every time something is added to $x_2$, also add it to $x_1$, so that $x_1=x_2$ at each step. So, at the end of this step, $x_1=x_2=x_3$. Repeat this process; we stop when $x_1=x_2=\cdots=x_{n-1}$. So, when $c=1$, we can make $n-1$ numbers equal. We now describe the approach when $c>1$. We define an auxiliary list $L$, which will always contain one of each distinct number. (For example, if the board consists of $[2,2,2,5,5]$, then $L$ may contain the first $2$ and the second $5$.) Note that we always have $v=\gcd(\{P(x)\colon x\in L\})$. While $L$ has size at least $3$ and contains two distinct numbers $y_1$ and $y_2$ which are equivalent $\pmod v$, use our claim with $(y_1,y_2,\ldots,y_m)=L$. Every time we replace $y_1$ with $y_1+P(y_i)$ for some $i$, replace every number equal to $y_1$ with the same quantity, so that numbers equal to $y_1$ remain equal to $y_1$; do the same for $y_2$. In this way, the number of distinct numbers on the board decreases. Once we can no longer do this anymore, we either have that $|L|=2$ or that $L$ contains at most one element in each residue class modulo $v$. In the first case, some number occurs at least $\lceil n/2\rceil$ times, so we are done. In the second case, $|L|\leq c$ by Claim 2, so some number occurs at least $\lceil n/c\rceil$ times, and we are done.

Physicsknight

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.

asdf334

08.07.2024 06:16

buh $ $

michael5210

08.07.2024 06:17

Not fun to read