, 2016

A downhill number can always be written as $a - b_1 - b_2 - \dots - b_9$, where $a$ is of the form $\overline{99\dots99}$ and each $b_i$ either equals $0$ or is of the form $\overline{11\dots11}$.
Let $n$ be a positive integer. The numbers of the form $\overline{99\dots99}$ yield at most $n$ different remainders upon division by $2^n$, as do the numbers of the form $\overline{11\dots11}$. Therefore, downhill numbers yield at most $n(n+1)^9$ different remainders upon division by $2^n$.
Let $n$ be so large that $n(n+1)^9 < 2^n$. ($n = 63$ works: $63 \times 64^9 < 64^{10} = 2^{60} < 2^{63}$.) Let $0 \le r < 2^n$ be such that no downhill number is congruent to $r$ modulo $2^n$.
Consider the polynomial
$$P(x) = \frac{1}{2 \times (2^n - 1)!} \prod_{1 \le i < 2^n} (x - r + i).$$
We have that $P(r) = \frac{1}{2}$ is not an integer.
Let, then, $x$ be a downhill number. The number $(x - r + 1) \dots (x - r + 2^n - 1)$ is a multiple of $(2^n - 1)!$ (as a product of $2^n - 1$ consecutive integers); therefore, $2P(x)$ is an integer. On the other hand, the number $(x - r)(x - r + 1) \dots (x - r + 2^n - 1)$ is a multiple of $2^n!$ (as a product of $2^n$ consecutive integers); therefore, $2(x - r)P(x)$ is an integer multiple of $2^n$. Since $x$ is downhill, $x - r$ is not divisible by $2^n$. Therefore, $2P(x)$ is even and $P(x)$ is an integer.