Assume natural number $n\ge2$. Amin and Ali take turns playing the following game: In each step, the player whose turn has come chooses index $i$ from the set $\{0,1,\cdots,n\}$, such that none of the two players had chosen this index in the previous turns; also this player in this turn chooses nonzero rational number $a_i$ too. Ali performs the first turn. The game ends when all the indices $i\in\{0,1,\cdots,n\}$ were chosen. In the end, from the chosen numbers the following polynomial is built: $$P(x)=a_nx^n+\cdots+a_1x+a_0$$Ali's goal is that the preceding polynomial has a rational root and Amin's goal is that to prevent this matter. Find all $n\ge2$ such that Ali can play in a way to be sure independent of how Amin plays achieves his goal.
Problem
Source: Iran MO Third Round N1
Tags: polynomial, number theory, Rational roots
08.09.2022 12:16
Firstly , for each even $n$ we'll show that Ali has the winning strategy. Consider that the coefficient $a_i$ stays undetermined till the last move ( which Ali will make it. ). Then Ali can choose an arbitrary rational number $r$ and one can see that if we put $a_i$ like below , then we have $P(r)=0$ and we're done. $$a_i=\frac{\sum_{j \neq i}{a_jr^j}}{r^i}\in \mathbb Q$$Now if $n$ is an odd number , then since $n \ge 3$ Amin can play somehow $a_0$ be determined before his last move and if he wants to determine coefficient $a_i$ at last , we'll show that there exist such a rational number , such that $P(x)$ doesn't have a rational root. Suppose that for a $a_i$ , number $r=\frac{m}{n'}$ is a rational root for $P(x)$ such that $gcd(m,n')=1$ , then one can see that : $$n'^nP(r) \equiv n'^na_0 \equiv 0 \pmod m \implies m|a_0$$So all possible rational roots are numbers in the form $\frac{a_0}{j}$ for a $j \in \mathbb{Z}$ which are all in the interval $[-a_0 , a_0]$. So if we procced rational function $f(x)$ such below , it's enough to show that this function , doesn't procced all rational values for $x=\frac{a_0}{j}$. $$f(x)=\frac{\sum_{j \neq i}{a_jr^j}}{x^i}$$Which is true since this function values are limited in interval $[-a_0 , a_0]$ because the limit of this function doesn't tend to infinity while $x$ tends to $0$. $$\lim_{x \to 0}{\frac{\sum_{j \neq i}{a_jr^j}}{x^i}}=\lim_{x \to 0}{\frac{a_nx^n}{x^i}}=\lim_{x \to 0} a_nx^{n-i}=a_n \text{or} 0$$
17.09.2022 09:23
18.09.2022 12:29
Mehrshad wrote:
Yes , actually there is the step that the second player should make all the coefficients integer and then determine $a_i$ , which corrects the $m|a_{j}m^{k}$ part and I forgot to wrote. And while all possible roots are going to be in the form $\frac{a_0}{j}$ , where is that function part problem ? :// Anyway , this is not totally my sol in exam , I changed the last part for posting that here )
19.09.2022 16:53
Shayan-TayefehIR wrote: And while all possible roots are going to be in the form $\frac{a_0}{j}$ , where is that function part problem ? :// Okay, I didn't say the roots aren't in the form $\frac{a_0}{j}$. But the limit that you wrote was wrong. When $x$ approaches $0$, the $a_nx^n$ is not so effective but $a_0$ is the most important nominal and $\frac{a_0}{x^i}$ approaches infinity.
28.03.2023 14:28
Mehrshad wrote: Shayan-TayefehIR wrote: And while all possible roots are going to be in the form $\frac{a_0}{j}$ , where is that function part problem ? :// Okay, I didn't say the roots aren't in the form $\frac{a_0}{j}$. But the limit that you wrote was wrong. When $x$ approaches $0$, the $a_nx^n$ is not so effective but $a_0$ is the most important nominal and $\frac{a_0}{x^i}$ approaches infinity. how can you find the official solution
20.06.2023 18:00
ylt_chn wrote: Mehrshad wrote: Shayan-TayefehIR wrote: And while all possible roots are going to be in the form $\frac{a_0}{j}$ , where is that function part problem ? :// Okay, I didn't say the roots aren't in the form $\frac{a_0}{j}$. But the limit that you wrote was wrong. When $x$ approaches $0$, the $a_nx^n$ is not so effective but $a_0$ is the most important nominal and $\frac{a_0}{x^i}$ approaches infinity. how can you find the official solution There is a channel in the Bale messenger named دوره تابستانی المپیاد ریاضی 1401 here which in addition to solutions also has marking schemes.
19.09.2024 17:30
Not the most interesting polynomial game (as everything could be made up to depend only on the last move), but certainly a nice number theory thing to try out!