A positive integer is called downhill if the digits in its decimal representation form a nonstrictly decreasing sequence from left to right. Suppose that a polynomial $P(x)$ with rational coefficients takes on an integer value for each downhill positive integer $x$. Is it necessarily true that $P(x)$ takes on an integer value for each integer $x$?
Problem
Source: Nikolai Beluhov, USAMTS 2017
Tags: algebra, polynomial, USAMTS
Naysh
02.05.2018 23:08
The answer is no.
First, note that any downhill integer with $d > 0$ digits can be written as a sum of at most nine terms (with repeats allowed) taken from the set of $d$ numbers
\[\left\{\frac{10^d - 1}{9}, \frac{10^d - 10}{9}, \dots, \frac{10^d - 10^{d-1}}{9}\right\}.\]
Hence there are $\binom{d+9}{9} - 1$ downhill integers on $d$ digits.
For a given positive integer $N$ then, there are
\[\sum_{d = 1}^N \left[\binom{d+9}{9} - 1\right] = \binom{N+10}{10} - (N+1)\]downhill integers with at most $N$ digits.
Pick an integer $N$ large enough so that $\binom{N+10}{10} - N < 2^N$.
Now, any downhill integer with greater than $N$ digits is either congruent modulo $10^N$ (hence modulo $2^N$) to zero, or to a downhill integer with at most $N$ digits. It follows that there exists some positive integer $m$ such that no downhill integer is congruent to $m$ modulo $2^N$.
Now, with this setup, consider the polynomial
\[f(x) = \frac 12\binom{x - m + 2^N - 1}{2^N - 1}.\]
Since $f(m) = 1/2$, the polynomial $f$ is not integer-valued.
However, for any integer $\ell\not\equiv m\pmod {2^N}$, we see that $f(\ell)$ is an integer.
This follows from the fact that \[\binom{n}{2^N-1}\]is even for all nonnegative integers $n$ such that $2^N \nmid n +1$, which in turn follows from the observation that
\[\frac{1}{1-x^{2^N}} \equiv \frac{1}{(1-x)^{2^N}} \pmod 2.\]
Taking this all together, we see that $f$ is an example of a polynomial that takes on integer values for all downhill integers, yet is not integer-valued at all integers.
Plasma_Vortex
03.05.2018 03:59
Let $S$ be the set of downhill integers, and let $Q(x) = \prod_{d \in S} (x-d)$. Let $p$ be a prime that does not divide $Q(-1)$. Then $P(x) = \frac 1p Q(x)$ is $0$ for all downhill integers $x$, but $P(-1)$ is not an integer.
Naysh
03.05.2018 06:06
@above: There are infinitely many downhill integers, so the definition of $Q$ in your solution doesn't make sense.
bobthesmartypants
03.05.2018 06:49
It can be amended with the fact that no downhill integers are $10\pmod{11}$ though.
Naysh
03.05.2018 07:27
@above: The integer $10$ is downhill.
bobthesmartypants
04.05.2018 03:12
My bad, I assumed the problem was the same as the USAMTS problem cited in the source.
parmenides51
31.07.2019 00:17
this problem was Balkan BMO Shortlist 2016 N5, it's alternate (easier) version was posted in USAMTS