Problem 1922

We establish the following key lemma.

Lemma 1. Consider a nonzero polynomial $P(x_1, \dots, x_k)$ in $k$ variables. Suppose that $P$ vanishes at all points $(x_1, \dots, x_k)$ such that $x_1, \dots, x_k \in \{0, 1, \dots, n\}$ and $x_1 + \dots + x_k > 0$, while $P(0, 0, \dots, 0) \ne 0$. Then $\deg P \ge kn$.

*Proof.* We induct on $k$. The base case $k=0$ is clear since $P \ne 0$. We assume that the statement is true for $k = \ell - 1$ for some positive integer $\ell$. Now we consider the case $k = \ell$. Denote for clarity $y = x_k = x_\ell$.

Let $R(x_1, \dots, x_{k-1}, y)$ be the residue of $P$ modulo $Q(y) = y(y-1)\dots(y-n)$. Polynomial $Q(y)$ vanishes at each $y=0, 1, \dots, n$, hence $P(x_1, \dots, x_{k-1}, y) = R(x_1, \dots, x_{k-1}, y)$ for all $x_1, \dots, x_{k-1}, y \in \{0, 1, \dots, n\}$. Therefore, $R$ also satisfies the condition of the Lemma; moreover, $\deg_y R \le n$. Clearly, $\deg R \le \deg P$, so it suffices to prove that $\deg R \ge nk$.

Now, expand polynomial $R$ in the powers of $y$:
$$R(x_1, \dots, x_{k-1}, y) = R_n(x_1, \dots, x_{k-1})y^n + R_{n-1}(x_1, \dots, x_{k-1})y^{n-1} + \dots + R_0(x_1, \dots, x_{k-1}).$$
We show that the polynomial $R_n(x_1, \dots, x_{k-1})$ satisfies the condition of the induction hypothesis.

Consider the polynomial $T(y) = R(0, \dots, 0, y)$ of degree $\le n$. This polynomial has $n$ roots $y = 1, \dots, n$; on the other hand, $T(y) \ne 0$ since $T(0) \ne 0$. Hence $\deg T = n$, and its leading coefficient is $R_n(0, 0, \dots, 0) \ne 0$. (For example, in the case $k=1$ we obtain that coefficient $R_n$ is nonzero.)

Similarly, take any numbers $a_1, \dots, a_{k-1} \in \{0, 1, \dots, n\}$ with $a_1 + \dots + a_{k-1} > 0$. Substituting $x_i = a_i$ into $R(x_1, \dots, x_{k-1}, y)$, we get a polynomial in $y$ which vanishes at all points $y = 0, \dots, n$ and has degree $\le n$. Therefore, this polynomial is null, hence $R_i(a_1, \dots, a_{k-1}) = 0$ for all $i = 0, 1, \dots, n$. In particular, $R_n(a_1, \dots, a_{k-1}) = 0$.

Thus, the polynomial $R_n(x_1, \dots, x_{k-1})$ satisfies the condition of the induction hypothesis. So, we have $\deg R_n \ge (k-1)n$ and $\deg P \ge \deg R \ge \deg R_n + n \ge kn$. $\square$

Now we can finish the solution. Suppose that there are $N$ planes covering all the points of $S$ but not containing the origin. Let their equations be $a_i x + b_i y + c_i z + d_i = 0$. Consider the polynomial
$$P(x, y, z) = \prod_{i=1}^{N} (a_i x + b_i y + c_i z + d_i).$$
It has total degree $N$. This polynomial has the property that $P(x_0, y_0, z_0) = 0$ for any $(x_0, y_0, z_0) \in S$, while $P(0, 0, 0) \ne 0$. Hence by Lemma 1 we get $N = \deg P \ge 3n$, as desired.

Suppose $r$ planes are given. As in the first solution, let $A_1, \dots, A_r$ be (nonzero) linear functions over $\mathbb{R}^3$ such that the equations of the planes are $A_i(x, y, z) = 0$. Define the polynomial $P_0 = A_1A_2\cdots A_r$, whose degree is $r$. If a lattice point $(x, y, z)$ satisfies $0 \le x \le a$, $0 \le y \le b$, $0 \le z \le c$, and $x + y + z > 0$, then $P_0(x, y, z) = 0$; however, $P_0(0, 0, 0) \ne 0$.

Polynomials $P_1, \dots, P_a$ are defined recursively by $P_{i+1}(x, y, z) = P_i(x+1, y, z) - P_i(x, y, z)$. By induction, we see that $P_i(x, y, z) = 0$ if $0 \le x \le a-i$, $0 \le y \le b$, $0 \le z \le c$, and $x+y+z > 0$, while $P_i(0, 0, 0) \ne 0$. Furthermore, if $P_i$ is a nonzero polynomial, then its degree is $r-i$.

Let $Q_0 = P_a$, and construct polynomials $Q_1, \dots, Q_b$ as above. Specifically, define $Q_{i+1}(x, y, z) = Q_i(x, y+1, z) - Q_i(x, y, z)$. Again, we have $Q_i(x, y, z) = 0$ provided $x = 0, 0 \le y \le b-i, 0 \le z \le c$, and $x+y+z > 0$, while $Q_i(0, 0, 0) \ne 0$. If $Q_i$ is nonzero, then its degree is $r-a-i$.

Finally, let $R_0 = Q_b$, and define $R_1, \dots, R_c$ by $R_{i+1}(x, y, z) = R_i(x, y, z+1) - R_i(x, y, z)$. As above, $R_i(x, y, z) = 0$ if $x = y = 0, 0 \le z \le c-i$, and $x+y+z > 0$. If $R_i$ is nonzero then its degree is $r-a-b-i$.

Consider the polynomial $R_c(x, y, z)$. Its value at $(0, 0, 0)$ is nonzero, so it is a nonzero polynomial. Its degree, which must be nonnegative, is $r-a-b-c$. Therefore, we have $r \ge a+b+c$, as desired.

Therefore, $a+b+c$ planes are necessary, and it is possible to cover all the points with $a+b+c$ planes. In the original problem, $a=b=c=n$, so the answer is $3n$.

Real numbers $x_0, \dots, x_a, y_0, \dots, y_b, z_0, \dots, z_c$ are given such that the $x_i$ are distinct, the $y_i$ are distinct, and the $z_i$ are distinct. If a collection of planes covers all points $(x_i, y_j, z_k)$ except $(x_0, y_0, z_0)$, the collection contains at least $a+b+c$ points.

To prove this we need a more general form of the method of finite differences used above.

Lemma 2. Suppose distinct reals $t_0, \dots, t_n$ are given. Then there exist weights $w_0, \dots, w_n$, with $w_0 \neq 0$, such that for each nonnegative integer $i < n$, we have $w_0 t_0^i + \dots + w_n t_n^i = 0$, while $w_0 t_0^n + \dots + w_n t_n^n \neq 0$.

*Proof.* The $n+1$ vectors $(1, t_j, t_j^2, \dots, t_j^{n-1})$ are linearly dependent over $\mathbb{R}^n$, so there exist weights $w_j$ such that $w_0 t_0^i + \dots + w_n t_n^i = 0$ for each $i < n$. However, since the $t_j$ are distinct, the vectors $(1, t_j, t_j^2, \dots, t_j^n)$ are linearly independent over $\mathbb{R}^{n+1}$. (This follows from the fact that their determinant, the Vandermonde determinant, is nonzero.) Therefore, we must have $w_0 t_0^n + \dots + w_n t_n^n \neq 0$. Also, the vectors $(1, t_j, \dots, t_j^{n-1})$, for $j = 1, \dots, n$, are independent. Thus we cannot have $w_0 = 0$. $\square$

Next we prove an essential result about the weights found above.

Lemma 3. Let reals $t_0, \dots, t_n$ be given, and weights $w_0, \dots, w_n$ be defined as above. Let $P(t)$ be any polynomial, and define $Q(t) = w_0 P(t+t_0) + \dots + w_n P(t+t_n)$. If the degree of $P(t)$ is less than $n$, then $Q(t) = 0$; otherwise, the degree of $Q$ is $n$ less than the degree of $P$.

*Proof.* First we prove the result for $P(t) = t^s$. The $t^r$ coefficient of $Q$ is $\frac{s!}{r!(s-r)!} (w_0 t_0^{s-r} + \dots + w_n t_n^{s-r})$. This is zero if $r > s-n$ and nonzero if $r \le s-n$, provided $s \ge n$. If $s < n$, then all coefficients of $Q$ are zero.

Now suppose $P$ is a general polynomial of degree $s$. Then the $t^s$ term of $P$ is nonzero. Also, the $t^{s-n}$ term of $Q$ depends only on the $t^s$ term of $P$, so it is also nonzero. Thus the degree of $Q$ is $s-n$. $\square$

Finally, we solve the general form of IMO Problem 6. Suppose there are $r$ planes in the collection, so there exists a polynomial $P$ of degree $r$ such that $P(x_i, y_j, z_k) = 0$ unless $i = j = k = 0$. Apply Lemma 3 to $P$ (regarded as a polynomial in its first variable) with $t_0 = x_0, \dots, t_a = x_a$, to obtain a polynomial $P_1$ of degree $r-a$ such that $P_1(0, y_j, z_k) = 0$ unless $j = k = 0$. Apply Lemma 3 again (this time on the second variable) to produce a polynomial $P_2$ of degree $r-a-b$ such that $P_2(0, 0, z_k) = 0$ unless $k = 0$. Apply Lemma 3 one more time (on the third variable) to produce a polynomial $P_3$ of degree $r-a-b-c$ such that $P_3(0, 0, 0) \neq 0$. Since $P_3$ is a nonzero polynomial, we have $r \ge a+b+c$. This completes the proof.