Let $n \in \mathbb{N}$. We define

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

as a set of $(n+1)^{3}-1$ points in three-dimensional space. Determine the minimum number of planes whose union contains $S$ but not the point $(0,0,0)$.

## Hints:

$\triangleright$ Start by finding a set of planes that work, possibly by considering the analogous problem in two dimensions to better visualize the situation.

$\triangleright$ Try to understand how a polynomial in several variables can be involved. It is important to keep in mind Proposition 20 stated below.

$\triangleright$ Consider trying to reduce the degree of the polynomial found, by using well-chosen operators.

Proposition 20. A plane in three dimensions can be described as the set of points whose coordinates $(x, y, z)$ satisfy a linear equation of the form $a x+b y+c z+d=0$ where $a, b, c, d$ are four real numbers such that $(a, b, c) \neq(0,0,0)$ (similarly, a line in two dimensions is characterized by an equation of the form $a x+b y+c=0$ where $a, b, c$ are three real numbers such that $(a, b) \neq(0,0))$.
We can find a solution with $3 n$ planes, for example, the planes with the equation $x+y+z-k=0$, for $k$ taking all values in $\{1, \ldots, 3 n\}$.

Surprisingly, the only known proofs to show that this number is minimal use algebraic methods, such as the use of a polynomial in three variables.

Suppose we can find $m$ planes, with $m<2 n$, which cover $S$ and do not pass through the origin. Each of them can be described by a linear equation of the form $a_{i} x+b_{i} y+c_{i} z+d_{i}=0$ with $d_{i} \neq 0$ for $i \in\{1, \ldots, m\}$. We then obtain the polynomial of degree $m$:

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

which vanishes at all points of $S$ but not at the origin.

We now define the operator $\Delta_{x}$ which acts on polynomials in three variables by replacing a polynomial $Q$ with the polynomial $\Delta_{x} Q$ defined by:

$$
\Delta_{x} Q(x, y, z)=Q(x+1, y, z)-Q(x, y, z)
$$

We define the operators $\Delta_{y}$ and $\Delta_{z}$ similarly. (These operators are discrete versions of differentiation operators, and the idea can be useful in other contexts).

We note that each of these operators reduces the degree of the polynomial to which it is applied by at least 1. By applying these operators successively to our polynomial $P$, we observe (and prove by induction) that $\Delta_{x}^{r} \Delta_{y}^{s} \Delta_{z}^{t} P(0,0,0)$ (which means applying $\Delta_{x}$ $r$ times, $\Delta_{y}$ $s$ times, and $\Delta_{z}$ $t$ times to the polynomial $P$ and evaluating at $\left.(0,0,0)\right)$ is never zero for $r, s, t \leq n$. In particular, we have $\Delta_{x}^{n} \Delta_{y}^{n} \Delta_{z}^{n} P(0,0,0) \neq 0$. But since $\Delta_{x}^{n} \Delta_{y}^{n} \Delta_{z}^{n} P$ is of degree at most $m-3 n<0$, it must be the zero polynomial, leading to a contradiction.

## A Little Theory

A priori, the use of polynomials in several variables in olympiad exercises does not require extensive knowledge. However, while some definitions and properties adapt well from polynomials in one variable to polynomials in several variables, others do not work the same way, and one must be careful not to make mistakes! After some formal definitions, we will see which properties adapt well and which require more attention.

## Definitions

Definition 21. A real polynomial in $n$ variables is a function from $\mathbb{R}^{n}$ to $\mathbb{R}$ that associates with an $n$