AoPS - Problem

Problem

Source: Iran MO Third Round N1

Tags: polynomial, number theory, Rational roots

Mehrshad

08.09.2022 11:34

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.

Shayan-TayefehIR

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$

Mehrshad

17.09.2022 09:23

I claim that for

$i=n$ your solution is incorrect. Shayan-TayefehIR wrote:

$n'^nP(r) \equiv n'^na_0 \equiv 0 \pmod m \implies m|a_0$ This equation doesn't necessarily hold. It doesn't seem that you handled the case that

$\exists k\not\in\{0,i\} : m \nmid a_{j}m^k$ . Shayan-TayefehIR wrote: it's enough to show that this function , doesn't procced all rational values for

$x=\frac{a_0}{j}$ . It's not enough. The value proceeded by the function should have the property

$\forall p\mid m: v_p(f(x))\ge0$ . So, it's enough to show that the function doesn't cover all nonzero integers instead. Shayan-TayefehIR wrote:

$\lim_{x \to 0}{\frac{\sum_{j \neq i}{a_jr^j}}{x^i}}{\color{red}\neq}\lim_{x \to 0}{\frac{a_nx^n}{x^i}}=\lim_{x \to 0} a_nx^{n-i}=a_n \text{or} 0$ But:

$\lim_{x \to 0^+}{\frac{\sum_{k \neq n}{a_kx^k}}{x^n}}=\lim_{x \to 0^+}{\frac{a_0}{x^n}}=\lim_{x \to 0^+} a_0x^{-n}=\pm\infty$

$\quad$ First, we prove that for even

$n$ s Ali wins. For even

$n$ s Ali performs the last move. Assume that all coefficients except

$a_k$ have been determined. Choose an arbitrary rational number

$q$ that isn't

$Q(x)=\sum_{i\neq k}a_ix^i$ 's root. Now Ali with choosing

$a_k=-\frac{Q(q)}{q^k}$ can do something that

$q$ be root of

$p$ . Now we show that for odd

$n$ s Amin can win. First, note the following lemma: Lemma. If in nonlinear polynomial with rational coefficients

$\sum_{i=0}^n a_ix^i$ all coefficients except one coefficient have been determined it's possible to set the last coefficient such that the polynomial doesn't have a rational root.

$\quad$ Proof: First assume that

$i\neq0,n$ occurs, assume that the common denominator of all specified coefficients is

$k$ . In this case, if for

$a_i$ we choose an integer coefficient and

$(a,b)=1$ ,

$\frac{a}{b}$ is root a of this polynomial, we have

$a\mid ka_0$ ,

$b\mid ka_n$ . Therefore we have finitely possible roots now choose

$a_i$ such that none of these numbers are a root of

$p$ .

$\quad$ In the case that

$i=0$ , consider the polynomial

$Q(x)=\sum_{i=1}^n a_ix^i$ , it's enough we to show that there exists a rational number that

$Q(x)=-a$ doesn't have a rational root. If

$a$ is an integer number similar to the previous case the denominator of every possible root of such equation divides

$ka_0$ . Now consider

$x_0$ so much big that for greater numbers than

$x_0$ we have

$Q(x+\frac{1}{ka_0})>Q(x)+1$ (Here we used nonlinearity of the polynomial.) Now if

$Q(x_0)=n$ then for all

$b$ ,

$Q(x_0+\frac{b}{ka_0})>n+1$ . So

$Q(x)=n+1$ doesn't have rational root.

$\quad$ In the case that

$i=n$ again consider the polynomial

$R(x)=\sum_{i=0}^n a_{n-i}x^i$ . Since the roots of

$P, R$ are inverse of each other it's enough for us to solve the problem for

$R$ that reduces to the previous case.

$\quad\blacksquare$

$\quad$ .Now because of the preceding lemma Amin can do something in the last step that the polynomial doesn't have any rational root. Tip 1. For solving this problem, in the lemma we didn't need the case that the undetermined coefficient is the leading coefficient.

Shayan-TayefehIR

18.09.2022 12:29

Mehrshad wrote:

I claim that for

$i=n$ your solution is incorrect. Shayan-TayefehIR wrote:

$n'^nP(r) \equiv n'^na_0 \equiv 0 \pmod m \implies m|a_0$ This equation doesn't necessarily hold. It doesn't seem that you handled the case that

$\exists k\not\in\{0,i\} : m \nmid a_{j}m^k$ . Shayan-TayefehIR wrote: it's enough to show that this function , doesn't procced all rational values for

$x=\frac{a_0}{j}$ . It's not enough. The value proceeded by the function should have the property

$\forall p\mid m: v_p(f(x))\ge0$ . So, it's enough to show that the function doesn't cover all nonzero integers instead. Shayan-TayefehIR wrote:

$\lim_{x \to 0}{\frac{\sum_{j \neq i}{a_jr^j}}{x^i}}{\color{red}\neq}\lim_{x \to 0}{\frac{a_nx^n}{x^i}}=\lim_{x \to 0} a_nx^{n-i}=a_n \text{or} 0$ But:

$\lim_{x \to 0^+}{\frac{\sum_{k \neq n}{a_kx^k}}{x^n}}=\lim_{x \to 0^+}{\frac{a_0}{x^n}}=\lim_{x \to 0^+} a_0x^{-n}=\pm\infty$

$\quad$ First, we prove that for even

$n$ s Ali wins. For even

$n$ s Ali performs the last move. Assume that all coefficients except

$a_k$ have been determined. Choose an arbitrary rational number

$q$ that isn't

$Q(x)=\sum_{i\neq k}a_ix^i$ 's root. Now Ali with choosing

$a_k=-\frac{Q(q)}{q^k}$ can do something that

$q$ be root of

$p$ . Now we show that for odd

$n$ s Amin can win. First, note the following lemma: Lemma. If in nonlinear polynomial with rational coefficients

$\sum_{i=0}^n a_ix^i$ all coefficients except one coefficient have been determined it's possible to set the last coefficient such that the polynomial doesn't have a rational root.

$\quad$ Proof: First assume that

$i\neq0,n$ occurs, assume that the common denominator of all specified coefficients is

$k$ . In this case, if for

$a_i$ we choose an integer coefficient and

$(a,b)=1$ ,

$\frac{a}{b}$ is root a of this polynomial, we have

$a\mid ka_0$ ,

$b\mid ka_n$ . Therefore we have finitely possible roots now choose

$a_i$ such that none of these numbers are a root of

$p$ .

$\quad$ In the case that

$i=0$ , consider the polynomial

$Q(x)=\sum_{i=1}^n a_ix^i$ , it's enough we to show that there exists a rational number that

$Q(x)=-a$ doesn't have a rational root. If

$a$ is an integer number similar to the previous case the denominator of every possible root of such equation divides

$ka_0$ . Now consider

$x_0$ so much big that for greater numbers than

$x_0$ we have

$Q(x+\frac{1}{ka_0})>Q(x)+1$ (Here we used nonlinearity of the polynomial.) Now if

$Q(x_0)=n$ then for all

$b$ ,

$Q(x_0+\frac{b}{ka_0})>n+1$ . So

$Q(x)=n+1$ doesn't have rational root.

$\quad$ In the case that

$i=n$ again consider the polynomial

$R(x)=\sum_{i=0}^n a_{n-i}x^i$ . Since the roots of

$P, R$ are inverse of each other it's enough for us to solve the problem for

$R$ that reduces to the previous case.

$\quad\blacksquare$

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 )

Mehrshad

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.

ylt_chn

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

Mehrshad

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.

Assassino9931

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!

Firstly, we show that

$A$ wins for even

$n$ . (Note also that

$A$ wins for

$n=1$ , since then it is a linear equation.) Observe that

$A$ performs the last move for even

$n$ , since the number of coefficients is odd. Assume that all coefficients except

$a_k$ have been determined. Choose an arbitrary rational number

$r$ that is not a root of

$Q(x)=\sum_{i\neq k}a_ix^i$ . Now

$A$ chooses

$\displaystyle a_k=-\frac{Q(r)}{r^k}$ and hence

$r$ will be a root of the resulting equation. Now we show that

$B$ wins for odd

$n\geq 3$ . It suffices to prove that if in a polynomial with rational coefficients

$\sum_{i=0}^n a_ix^i$ , of degree

$n\geq 2$ , all coefficients except one have been determined, then it is possible to set the last coefficient so that the polynomial does not have a rational root.

$\begin{itemize} \item Suppose that $a_i$ for some $i\neq 0,n$ is the undetermined coefficient. Let $k$ be the common denominator of all specified coefficients. If $\frac{a}{b}$, with $\gcd(a,b) = 1$, is a root of the final polynomial, then we have $a\mid ka_0$ and $b\mid ka_n$. Therefore, we have finitely many possibilities for a root -- for each of these we can calculate the corresponding value of $a_i$ and hence we can pick a value of $a_i$ distinct from these values. \item Suppose that $a_0$ or $a_n$ is the undetermined coefficient; by replacing $x$ with $\frac{1}{x}$, if necessary, we may assume it is $a_0$. Consider $Q(x)=\sum_{i=1}^n a_ix^i$, it is enough we to show that there exists a rational number $a$ that $Q(x)=-a$ does not have a rational root. By multiplying by $(-1)$, if necessary, we may assume $a_n > 0$. If $a$ is an integer, then similarly to the previous case the denominator of every possible root of such an equation divides $ka_n$, which is independent of $a$. Now consider $x_0$ such that for all $x\geq x_0$ we have $Q\left(x+\frac{1}{ka_n}\right)>Q(x)+1$ and $Q(x)$ is increasing. (Here we used that the degree of $Q$ is at least $2$.) Now if $Q(x_0)=m$ then for all positive integers $b$ we have $Q\left(x_0+\frac{b}{ka_n} \right)>m+1$. Therefore $Q(x)=m+1$ has no rational roots, as it has no rational root with denominator dividing $ka_n$, and we are done. \end{itemize}$

As the solution shows, the hardest case is when

$n$ is odd and the last coefficient is

$a_0$ or

$a_n$ . However, if

$n\geq 5$ ,

$B$ can play so that for sure the final coefficient will not be

$a_0$ or

$a_n$ , so in fact it is enough to consider this case only for

$n=3$ . This does not seem to overall simplify the required argument, but perhaps helps to figure it out.