Taiwan IMO Selection Camp

We transform the problem to a single variable question by the following.

Lemma. Let $a_1, \dots, a_n$ be nonnegative integers and let $G(x)$ be a nonzero polynomial with $\deg G \le a_1 + \dots + a_n$. Suppose that some polynomial $F(x_1, \dots, x_n)$ satisfies
$$F(x_1, \dots, x_n) = G(x_1 + \dots + x_n)$$
for $(x_1, \dots, x_n) \in \{0, 1, \dots, a_1\} \times \dots \times \{0, 1, \dots, a_n\}$.
Then $F$ cannot be zero polynomial, and $\deg F \ge \deg G$.

For proving the lemma, we will use forward differences of polynomials. If $p(x)$ is a polynomial with a single variable, then define
$$(\Delta p)(x) = p(x + 1) - p(x).$$
It is well-known that if $p$ is a nonconstant polynomial then
$$\deg \Delta p = \deg p - 1.$$
If $p(x_1, \dots, x_n)$ is a polynomial with $n$ variables and $1 \le k \le n$ then let
$$\Delta_k(p)(x_1, \dots, x_n) = p(x_1, \dots, x_{k-1}, x_k+1, x_{k+1}, \dots, x_n) - p(x_1, \dots, x_n).$$

It is also well-known that either $\Delta_k p$ is the zero polynomial or
$$\deg(\Delta_k p) \leq \deg p - 1.$$

Proof of the lemma. We apply induction on the degree of $G$, If $G$ is a constant polynomial then we have $F(0, \dots, 0) = G(0) \neq 0$, so $F$ cannot be the zero polynomial.
Suppose that $\deg G \geq 1$ and the lemma holds true for lower degrees. Since
$$a_1 + \dots + a_n \geq \deg G > 0,$$
at least one of $a_1, \dots, a_n$ is positive; without loss of generality suppose $a_1 \geq 1$.
Consider the polynomials $F_1 = \Delta_1 F$ and $G_1 = \Delta G$. On the grid $\{0, \dots, a_1 - 1\} \times \{0, \dots, a_2\} \times \dots \{0, \dots, a_n\}$ we have
$$\begin{aligned} F_1(x_1, \dots, x_n) &= F(x_1 + 1, x_2, \dots, x_n) - F(x_1, x_2, \dots, x_n) \\ &= G(x_1 + \dots + x_n + 1) - G(x_1 + \dots + x_n) \\ &= G_1(x_1 + \dots + x_n). \end{aligned}$$
Since $G$ is nonconstant, we have
$$\deg G_1 = \deg G - 1 \leq (a_1 - 1) + a_2 + \dots + a_n.$$
Therefore we can apply the induction hypothesis to $F_1$ and $G_1$ and conclude that $F_1$ is not the zero polynomial and $\deg F_1 \geq \deg G_1$. Hence,
$$\deg F \geq \deg F_1 + 1 \geq \deg G_1 + 1 = \deg G.$$

To prove the problem statement, take the unique polynomial $g(x)$ so that
$$g(x) = \left[ \frac{x}{m} \right] \text{ for } x \in \{0, 1, \dots, n(m-1)\} \text{ and } \deg g \le n(m-1).$$
Notice that precisely $n(m-1)+1$ values of $g$ are prescribed, so $g(x)$ indeed exists and is unique. Notice further that the constraints $g(0) = g(1) = 0$ and $g(m) = 1$ together enforce $\deg g \ge 2$.
By applying the lemma to $a_1 = \dots = a_n = m-1$ and the polynomials $f$ and $g$, we achieve $\deg f \ge \deg g$. Hence we just need a suitable lower bound on $\deg g$.

Consider the polynomial
$$h(x) = g(x + m) - g(x) - 1.$$
The degree of $g(x+m) - g(x)$ is $\deg g - 1 \ge 1$, so
$$\deg h = \deg g - 1 \geq 1,$$
and therefore $h$ cannot be the zero polynomial. On the other hand, $h$ vanishes at the points $0, 1, \dots, n(m-1)-m$, so $h$ has at least $(n-1)(m-1)$ roots. Hence,
$$\deg f \geq \deg g = \deg h + 1 \geq (n-1)(m-1) + 1 \geq n.$$

At the point $(b_1, \dots, b_n)$ we have
$$H(b_1, \dots, b_n) = G(d) - G_0(d) \neq 0.$$
At all other points of the grid we have $F = G$ and therefore
$$H = G - G_0 = 0.$$
So, by the Alon-Füredi bound,
$$\deg H \geq b_1 + \dots + b_n = d.$$
Since $\deg G_0 < d$, this implies
$$\deg F = \deg (H + G_0) = \deg H \geq d = \deg G.$$