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
26.07.2014 09:14
This is my solution, I hope that it is correct
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$
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.
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$.
11.08.2024 19:29
posting for storage