Problem #6 from the Italian MO 2000

Problem

Problem #6 from the Italian MO 2000

Solution 1

The condition $p(0)=0\,$ implies that the free coefficient vanishes such that any integer $u\,$ divides $p(u).$

Thus, from $p(a)=1999\,$ it follows that $a|1999\,$ and, since $1999$ is a prime, $a=1\,$ or $a=1999.$ For $a=1\,$ we immediately have one case: $p(1)=1999.$ Assume $a=1999.$

Next, $p(b)=2001=3\cdot 23\cdot 29.\,$ Since $(b-a)|(b^k-a^k),\, k\ge 0,\,$ then also $(b-a)|(p(b)-p(a))=2.\,$ Thus, $|b-1999|=1\,$ or $|b-1999|=2.$ So, for $b$, we should check the values $1997,$ $1998,$ $2000,$ and $2001.$ But obviously, neither of $1997,$ $1998,$ $2000,$ divides $2001\,$ as they could be expected from $b|p(b)=2001.$

In the case $b=2001,\,$ $p(x)-x=x(x-1999)(x-2001)q(x),\,$ so that $p(1)=q(1)\cdot 1998\cdot 2000+1,\,$ which is in $[0,10^7]\,$ for $q(1)\in\{0,1,2\}.$

Solution 2

Let the polynomial be $P(x)=\sum_{k=1}^Nu_kx^k$, where $u_k\in \mathbb{Z}$ and $u_N\neq 0$. Thus, $P(0)=0$.

From the constraint,

$\displaystyle \begin{align} &\sum_{k=1}^N u_k(b^k-a^k)=2 \\ &(b-a)Q=2~\text{(For some integer $Q$)}. \end{align}$

Moreover, both $a$ and $b$ are odd (and thus $|b-a|$ is even) because $1999$ and $2001$ are odd. Thus, $b=a\pm 2$.

Suppose $a$ is divisible by a prime number - $p$ - other than $1999$. Then, $LHS=P(a)\equiv0~(mod~p)$. However, this is a contradiction because $RHS=1999\not\equiv0~(mod~p)$. Thus, $a=1$ or $a=1999$.

If $a=1$, then $P(a)=P(1)=1999$. The possible positive value for $b$ is $3$. The existence of a second degree polynomial for this case can be proven by solving the system $u_1+u_2=1999$, $3u_1+9u_2=2001$ to give $P(x)=2665-666x^2$.

Alternately, if $a=1999$, then

$\displaystyle \sum_{k=1}^N u_k(1999)^k=1999,~\sum_{k=1}^N u_k(1997)^k=2001$

or

$\displaystyle \sum_{k=1}^N u_k(1999)^k=1999,~\sum_{k=1}^N u_k(2001)^k=2001.$

The first situation is not feasible because the $2001\not\equiv 0~(mod~1997)$.

Thus, $P(x)-x=0$ has at least two roots in $1999$ and $2001$. Hence, $P(x)=x+(x-1999)(x-2001)K(x)\Rightarrow P(1)=1+3996000\cdot K(1)\geq 10^7\Rightarrow \\ 0\leq K(1) \leq 2.$

Thus, $P(1)\in\{1,1+3996000=3996001,1+2\cdot3996000=7992001\}$ for this case.

Solution 3

# 1

Define the polynomial $h(x) := x(x-a)(x-b)$ and let $p(x)$ be a polynomial satisfying

(1)

$p(0) = 0, \qquad p(a) = 1999, \qquad p(b) = 2001.$

Let $q(x) $be an integer polynomial satisfying the equations (1) as well. After dividing $q(x) - p(x)$ successively by $x, x-a, x-b$ we get a polynomial $r$ with integer coefficients satisfying

$q(x) - p(x) = x(x-a)(x-b)r(x) = h(x)r(x).$

Conversely we can choose an arbitrary integer polynomial $r(x)$ and obtain $q(x)$ this way. Evaluating at $1:$

$ q(1) = p(1) + (1-a)(1-b)r(1).$

Because $r(x)$ was arbitrary, the solution set for fixed $a,b$ is

$S_{a,b} = p(1) + (a-1)(b-1)\mathbb{Z}.$

It remains to find a polynomial $p(x)$ (if it exists) for each $a,b$ and compute the value $p(1).$

# 2

Write $q(x) = xq'(x).$ From $1999 = q(a) = aq'(a)$ we can deduce that $a \in \{1,1999\}$ and similarly $2001 = q(b) = bq'(b)$ implies $b \in \{1,3,23,29,2001\},$ i.e. the divisors of $2001.$

# 3

This observation is blatantly stolen from Alexander Bogomolny: $b-a $divides $p(b)-p(a) = 2.$ This means $(a,b) \in \{ (1999,2001), (1,3) \}.$

Case $(a,b) = (1999,2001)$

Choose $p(x) = x$ so that $S_{1999,2001} = \{ 1 \}.$

Case $(a,b) = (1,3)$

We have $1999 = q(1) = 1q'(1) \Rightarrow q'(1) = 1999$ and $2001 = q(3) = 3q'(3) \Rightarrow q'(3) = 667.$ $q'(x) := 2665 - 666x$ works. Thus we set $p(x) = x(2665-666x).$ Of course $p(1) = 1999,$ by design.

So $S_{1,3} \cap [0,10^7] = (1999 + 3996000 \mathbb{Z}) \cap [0,10^7] = \{ 1999, 3997999, 7993999 \}.$

# Answer

$\{ 1, 1999, 3997999, 7993999 \}$.

Acknowledgment

The problem has been posted by Lorenzo Villa on twitter.com. Solution 2 is by Amit Itagi; Solution 3 is by Long Huynh Huu.

 

|Contact| |Up| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny

71471355