*Problem*

(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

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

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

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,

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 .

Let

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

we get

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.

*References*

- D. Djukić et al,
*The IMO Compendium* - D. Schleicher, M. Lackmann,
*An Invitation to Mathematics*