Let $t$ and $n$ be fixed integers each at least $2$. Find the largest positive integer $m$ for which there exists a polynomial $P$, of degree $n$ and with rational coefficients, such that the following property holds: exactly one of \[ \frac{P(k)}{t^k} \text{ and } \frac{P(k)}{t^{k+1}} \] is an integer for each $k = 0,1, ..., m$. Proposed by Michael Kural
Problem
Source: ELMO 2014 Shortlist N3, by Michael Kural
Tags: algebra, polynomial, induction, binomial theorem, number theory proposed, number theory
tahanguyen98
26.07.2014 09:14
This is my solution, I hope that it is correct
My solution
Firstly, notice that for all $k=\overline{0,m}$ then $\dfrac{P(k)}{t^k}$ is an integer but $\dfrac{P(k)}{t^{k+1}}$ is not, this is because if $\dfrac{P(k)}{t^{k+1}}$ is an integer, then let $A$ be $\dfrac{P(k)}{t^{k+1}}$, and of course $A \in Z$ thus $A*t$ is an integer, which implies $\dfrac{P(k)}{t^k}$ is an integer, a contradiction! Consequently, $P(k)$ is an integer for all $k=0,..,m$ and $t^k$ divides $P(k)$ but $t^{k+1}$ doesn't
Denote $t^k||P(k)$ such that $t^k$ divides $P(k)$ but $t^{k+1}$ doesn't
We will prove by induction that $m$ has the maximum value is $n$
For n=2, assume the contrary, that is $m>n=2$ or $m\geq 3$
Let $P(x)$ be $ax^2+bx+c$ with $a,b,c$ are rational numbers, then we can derive easily:
1) $c$ is not divisible by $t$ and it's an integer
2) $a+b+c, 4a+2b+c, 9a+3b+c$ is divisible by $t$
3) $a+b$ is an integer
4) $3a+b$ is an integer and $3a+b$ is divisible by $t$ and this implies $t|9a+3b$, combining this with $t|9a+3b+c$, we obtain $t|c$ which contradicts 1)
Thus the assumption for $m\geq 3$ is wrong, which remains to us $m\le 2$
Assume that we have had the conclusion for all number which is less than $n$, we will prove it for $n$
We consider $Q(k)=P(k+1)-P(k)$, in which $P(x)$ is a polynomial with rational coefficents, and its degree is $n$
By analyzing Binomial theorem, we derive at $deg Q=n-1$ and we also have $t^k||P(k)$ as well as $t^{k+1}||P(k+1)$ hence $t^k||P(k+1)-P(k)=Q(k)$
Now we have built $Q(0),Q(1),....,Q(m-1)$ in which $Q(x)$ is a polynomial with rational coeffients and $degQ=n-1$, and we also have $t^k||Q(k)$ for all $k=0,1,...,m-1$, applying the assumption of induction, we obtain $m-1\le n-1$ or $m\le n$ as desired.
Now, in conclusion, we will prove that there exist a polynomial which satisfies the desired condition
Let $P(0)=t^{n+1}+1,...,P(k)=t^{n+1}+t^k,...,P(n)=t^{n+1}+t^n$
Notice that deg P=n and we have already had $n+1$ values of $P(x)$ where $x=0,1,2,...,n$, then by interpolation polynomial in the Lagrange form Click to reveal hidden textfor reference see http://en.wikipedia.org/wiki/Lagrange_polynomial we have
$P(x)=\sum_{i=0}^{n}{P(i)*\dfrac{(x-1)(x-2)...(x-(i-1))(x-(i+1)...(x-n)}{(i-1)(i-2)...(i-(i-1))(i-(i+1))...(i-n)}}$ and now we can easily and quickly check that $P(x)$ is in fact a polynomial with rational coeffients and it satisfied all condition <>
AnonymousBunny
29.07.2014 11:37
Since $\dfrac{P(k)}{t_k}$ is an integer whenever so is $\dfrac{P(k)}{t^{k+1}},$ the condition is equivalent to $v_t (P(k)) = k.$ The answer is $n.$ The construction is easy, just select some numbers $a_0, a_2, \cdots , a_n$ such that $v_t (a_i) = i$ for all $i$ and use Lagrange Interpolation to construct a polynomial $P(x)$ of degree $n$ such that $P(i) = a_i \quad \forall \ i \leq n.$ Now, I shall use induction to show that $m$ cannot exceed $n.$ The base case is easy. Suppose for some $n,$ $m$ cannot exceed $n.$ Suppose there exists a $n+1$ degree polynomial for which $m$ can be more than $n+2.$ Consider its first order difference $\triangle_1 (x).$ Note that $\triangle_1 (x)$ is a $n$ degree polynomial, and $v_t (\triangle_1 (k)) = k$ for all $0 \leq k \leq n+1$ because $t^{k+1} \mid f(k+1), t^{k+1} \nmid f(k),$ and $t^{k} \mid f(k).$ This contradicts our inductive hypothesis. $\blacksquare$
anantmudgal09
19.01.2017 22:34
We claim that $m=n$ is the desired maximum value. Note that the required condition is just a cute way of saying $t^k \mid P(k)$ and $t^{k+1} \nmid P(k)$ for $k=0, 1, \dots, m$. For construction, take $P(j)=t^j$ for $j=0, 1, \dots, n$ and apply Lagrange Interpolation to get $P$ with rational coefficients. For the estimate, suppose some $m>n$ works. Applying the finite differences operator, we obtain $$\Delta^{(n)} P(x)=\sum^n_{j=0} (-1)^{n-j}\binom{n}{j}P(x+j)$$is the constant function. Note that $t \mid \Delta^{(n)} P(1)$ but $t \nmid \Delta^{(n)} P(0)$ giving us the desired contradiction. $\, \square$ P.S. I am writing this at a late hour; hopefully there are no errors.
rah4927
16.02.2018 23:07
We claim that the answer is $n$. Use the set of equations $P(k)=t^k$ for $k=0\rightarrow n$ to construct such a polynomial using Lagrange interpolation. We'll use the same technique for the next part. Assume for sake of contradiction that we have $P(k)=t^k\cdot a_k$ for $k=0\rightarrow n+1$ where $(a_k,t)=1$. Since the degree of $P$ must be $n$, it suffices to show that the coefficient of $k^{n+1}$ can never be $0$. Using Lagrange interpolation, this coefficient is equal to $\sum \dfrac{t^i\cdot a_i}{\prod_{i \neq j} (i-j)}$ which can be rewritten as $\frac{1}{(n+1)!}\sum^n_{i=0} \dbinom{n+1}{i}\cdot t^i \cdot a_i$. The last one can never be $0$ because the summation evaluates to $a_0$ modulo $t$, but $(a,t)=1$, hence non-zero mod $t$.
onyqz
11.08.2024 19:29
posting for storage
Notice that for $m=n$ we can simply take $P(k)=t^k, \forall 0\leq k\leq m$. Hence we suppose, that $m>n$. Now also notice, that if $\frac{P(k)}{t^{k+1}}=a$ is an integer, then $\frac{P(k)}{t^k}=a\cdot t$ is also an integer, which is a contradiction and thus we have $\frac{P(k)}{t^k}$ is an integer $\forall 0\leq k \leq m$. Therefore set $P(k) = a_kt^k, \gcd(a_k,t)=1$.
Now we use Lagrange Interpolation as follows:
$$P(x) = \sum_{k=0}^mP(k)\prod_{l\neq k}\frac{x-l}{k-l} \, .$$Since this would imply $\deg P = m > n$, we must have the coefficient of $x^m$ equal to $0$:
\begin{align*}
0&=\sum_{k=0}^mP(k)\prod_{l\neq k}\frac{1}{k-l}\\
&=\sum_{k=0}^m a_kt^k\prod_{l\neq k}\frac{1}{k-l}\\
&=\sum_{k=0}^ma_kt^k\frac{(-1)^{m-k}}{k!(m-k)!}\\
&=\sum_{k=0}^ma_kt^k {m \choose k} (-1)^{m-k}\\
\end{align*}Now $t$ divides this sum, especially each summand for $k \geq 1$. However, then $t$ must divide the summand for $k=0$, i.e. $t$ must divide $a_0$. But we know $\gcd(a_k,t)=1, \forall 0\leq k \leq m$, contradiction! We conclude that $m=n$ is the maximal $m$. $\square$