Let $n$ be a positive integer. Consider the set of $(n+1)^{3}-1$ points in three-dimensional space:

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

Determine the minimum number of planes such that their union contains all points of the set $S$, but does not contain the point $(0,0,0)$.
Nagy Csaba's solution. The answer to the problem's question is $3 n$. Indeed, this many planes are sufficient, for example, the planes with equations $x+y+z=1$, $x+y+z=2, \ldots, x+y+z=3 n$ are suitable.

Conversely, suppose we covered $S$ with some planes, but not the origin. We will show that the number of planes is at least $3 n$. Let's write the equations of the planes in the form $a x+b y+c z+d=0$ (where $a, b, c$ are not all zero). Multiply the expressions on the left side of the equations; we get a polynomial $p(x, y, z)$ which is zero at the points of $S$, but not at the origin. We need to prove that the degree of $p$ is at least $3 n$. Instead, we will prove the following, more general statement: $a, b, c$ are natural numbers, and let

$$
\begin{aligned}
S(a, b, c)= & \{(x, y, z) \mid x \in\{0,1, \ldots, a\}, y \in\{0,1, \ldots, b\} \\
& z \in\{0,1, \ldots, c\}, x+y+z>0\}
\end{aligned}
$$

If the polynomial $f(x, y, z)$ is zero at the points of $S(a, b, c)$, but not at $(0,0,0)$, then its degree is at least $a+b+c$.

We prove this by induction on $(a+b+c)$. If $a+b+c=1$, then the polynomial is at least of the first degree (i.e., not constant), since it takes two different values. If $a+b+c>1$, then consider a polynomial $f$ that meets the conditions, and let its degree be $t$. Among the numbers $a, b, c$, there exists a positive one, let it be $a$. Form the polynomial $g(x, y, z)=f(x+1, y, z)-f(x, y, z)$. The degree of the polynomial $g$ is clearly at most $t$; however, the corresponding $t$-th degree terms in $f(x+1, y, z)$ and $f(x, y, z)$ have the same coefficients, so they cancel each other out in $g$. Therefore, the degree of $g$ is at most $t-1$. The polynomial $g$ is zero at the points of $S(a-1, b, c)$, but not at the origin; by the induction hypothesis, the degree of $g$ is at least $a-1+b+c$, so $t-1 \geq a-1+b+c$, which implies $t \geq a+b+c$.