Let n be a positive integer, and consider the set
S=\{(x,y,z)\in\{0,\ldots ,n\}^{3}|x+y+z\gt 0\}
as a set of (n+1)^{3}-1 points in three-dimensional space. Determine the smallest number of planes whose union contains S but does not contain the point (0,0,0).

(This problem was judged as particularly difficult. It was solved by only five participants - out of 237.)

Solution 1 (An Invitation to Mathematics, pp. 92-93)

In 1- and 2-dimensional analogs the answer is almost certainly n and 2n, respectively. By analogy, the expected answer for the given problem is 3n. Obviously, 3n planes suffice: x=k, y=k, z=k, k=1,\ldots ,n cover the whole of S. The task is to show that no m \lt 3n planes could cover S entirely.

Assume to the contrary that the planes

a_{i}x + b_{i}y + c_{i}z + d_{i} = 0, (d_{i} \ne 0, 1 \le i \le n)

cover the whole of S. Multiplying the left-hand sides of all m equation gives a polynomial

P(x,y,z)=\prod_{i=1}^{m}(a_{i}x + b_{i}y + c_{i}z + d_{i})

of degree m that vanishes at every point of S but not at the origin (0,0,0).

On the space of polynomials in three variables \{Q(x,y,z)\} define an operator \Delta _{x} by

\Delta _{x}Q(x,y,z)=Q(x+1,y,z)-Q(x,y,z),

and similarly define \Delta _{y} and \Delta _{z}. Observe that each of these operators decreases the degree of a non-zero polynomial by at least 1.

It can be shown by induction, that \Delta _{x}^r \Delta _{y}^s \Delta _{z}^t P(0,0,0) is never zero for r,s,t\le n, in particular,

\Delta _{x}^n \Delta _{y}^n \Delta _{z}^n P(0,0,0) \ne 0.

This is in contradiction to the fact that the degree of \Delta _{x}^n \Delta _{y}^n \Delta _{z}^n P(x,y,z) is at most m-3n\lt 0, making it a zero polynomial.

Solution 2 (The IMO Compendium, p. 756)

We construct polynomial P as in the first solution, under the same assumptions, but the proceed differently.

Set \delta_0=1, and choose the numbers \delta_1, \delta_2, \ldots , \delta_n such that \sum_{i=0}^{n}\delta_{i} i^{m}=0 for m=0,1,2,\ldots ,n-1, where we assume that 0^{0}=1. The choice of such numbers is possible because the implied linear system in \delta_{1},\ldots ,\delta_{n} has the .



By the construction of P, we know that P(0,0,0)\ne 0 and P(i,j,k)=0 for all other i,j,k\in \{0,\ldots ,n\}. Therefore S = \delta_{0}^{3}P(0,0,0). On the other hand, expanding P as

P(x,y,z)=\sum_{\alpha+\beta+\gamma\le N}P_{\alpha,\beta,\gamma}x^{\alpha}y^{\beta}z^{\gamma}

we get

S=\sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{n}\delta_{i}\delta_{j}\delta_{k}\sum_{\alpha+\beta+\gamma\le N}P_{\alpha,\beta,\gamma}x^{\alpha}y^{\beta}z^{\gamma} = \sum_{\alpha+\beta+\gamma\le N}P_{\alpha,\beta,\gamma}\big(\sum_{i=0}^{n}\delta_{i} i^{\alpha}\big)\big(\sum_{j=0}^{n}\delta_{j} j^{\beta}\big)\big(\sum_{k=0}^{n}\delta_{k} k^{\gamma}\big)=0

because, for every choice of \alpha,\beta,\gamma at least one of them is less than n, making the corresponding sum in the last expression equal to 0. This is a contradiction, hence necessarily m=3n.