IMO 2007 Problem 6

Let $ n$ be a positive integer. Consider

$S=\left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x+y+z > 0 \right\}$

as a set of $(n+1)^3-1$ points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains $S$ but does not include $ (0,0,0)$.

Author: Gerhard Wöginger, Netherlands

================================

Solution:

The key point is to prove that you can't do it without $3n$ planes. We follow Alon and Furedi's usage of Combinatorial NullStellensatz in 1993 for almost the same problem with $m$ rather than $3$ dimensions and $n=1$.

Let $f(x,y,z)$ be the product of the planes that contains $S$ but not $(0,0,0)$. Then

$g(x,y,z):=(n!)^3f(x,y,z)-f(0,0,0)\prod_{i\in[n]}(i-x)\prod_{j\in[n]}(j-y)\prod_{k\in[n]}(k-z)$

is zero for any $(x,y,z)\in\{0,1,\dots,n\}^3$.

Suppose $\deg(f)<3n$, then the highest-degree term of $g(x,y,z)$ is $x^ny^nz^n$. Thus by Combinatorial NullStellensatz, for $X=Y=Z=\{0,1,\dots,n\}$ there must be some $(x,y,z)\in X\times Y\times Z$ such that $g(x,y,z)\ne 0$. This contradicts with the assumption.

$\diamond$