IMO 2007 · Problem 6

Let \(n\) be a positive integer. Consider \[ S=\{(x,y,z):x,y,z\in\{0,1,\ldots,n\},\ x+y+z>0\} \] as a set of \((n+1)^3-1\) points in three-dimensional space. Determine the smallest possible number of planes, the union of which contains \(S\) but does not include \((0,0,0)\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{3n} \]

Solution

The \(3n\) planes \[ x+y+z=k,\qquad k=1,2,\ldots,3n, \] cover \(S\), since every point of \(S\) has an integer coordinate sum between \(1\) and \(3n\). None of these planes contains the origin. Thus \(3n\) planes suffice.

For the lower bound, suppose \(m<3n\) planes cover \(S\) and avoid the origin. Write their equations as \[ a_rx+b_ry+c_rz+d_r=0,\qquad 1\le r\le m. \] Since each plane avoids the origin, every \(d_r\ne0\). The polynomial \[ P(x,y,z)=\prod_{r=1}^{m}(a_rx+b_ry+c_rz+d_r) \] therefore satisfies \[ \deg P\le m<3n,\qquad P(0,0,0)=\prod_{r=1}^{m}d_r\ne0, \] while \(P\) vanishes at every point of \(S\).

We show that these properties are impossible by taking finite differences. For any polynomial \(F\), define \[ \Delta_xF(x,y,z)=F(x+1,y,z)-F(x,y,z), \] and define \(\Delta_y,\Delta_z\) similarly.

Each difference reduces total degree by at least one, unless it gives the zero polynomial. Indeed, on a monomial, \[ \Delta_x(x^ay^bz^c)=\bigl((x+1)^a-x^a\bigr)y^bz^c. \] This is zero if \(a=0\); otherwise the binomial theorem shows that its total degree is at most \(a+b+c-1\). The same reasoning applies in the other variables. Consequently, since \(\deg P<3n\), \[ \Delta_x^n\Delta_y^n\Delta_z^nP\equiv0. \tag{1} \]

On the other hand, expanding the repeated differences gives \[ \begin{aligned} &\bigl(\Delta_x^n\Delta_y^n\Delta_z^nP\bigr)(0,0,0)\\ &\quad= \sum_{i=0}^{n}\sum_{j=0}^{n}\sum_{k=0}^{n} (-1)^{3n-i-j-k} \binom ni\binom nj\binom nk\,P(i,j,k). \end{aligned} \tag{2} \] To justify the coefficients, in the \(n\) differences in \(x\), choosing the shifted term \(i\) times and the negative unshifted term \(n-i\) times gives the coefficient \((-1)^{n-i}\binom ni\). Applying this independently in all three coordinates yields (2).

Every value on the right of (2) vanishes except the value at \((0,0,0)\). Hence \[ \bigl(\Delta_x^n\Delta_y^n\Delta_z^nP\bigr)(0,0,0) =(-1)^{3n}P(0,0,0)\ne0, \] contradicting (1).

Thus at least \(3n\) planes are necessary. Together with the construction, this proves that the minimum is \(\boxed{3n}\).

The solution was checked against the official IMO shortlist solutions.