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)

Step 2 of 5: State and set up the induction lemma on rectangular grids

Previous step Next step

In plain words

Generalizing from $\{0,\ldots,n\}^3$ to an arbitrary box $\{0,\ldots,n_1\}\times\{0,\ldots,n_2\}\times\{0,\ldots,n_3\}$ allows induction on the sum $n_1+n_2+n_3$ by peeling off one top face at a time.

S_1 \times S_2 \times S_3 = \{0,\ldots,n_1\}\times\{0,\ldots,n_2\}\times\{0,\ldots,n_3\} \implies \deg P \ge n_1 + n_2 + n_3

Detailed analysis

Lemma: if $P \in \mathbb{R}[x,y,z]$ vanishes on $(S_1\times S_2\times S_3)\setminus\{(0,0,0)\}$ where $S_k=\{0,1,\ldots,n_k\}$ , and $P(0,0,0)\ne 0$ , then $\deg P \ge n_1+n_2+n_3$ . We prove this by induction on $n_1+n_2+n_3$ ; the base case $n_1=n_2=n_3=0$ is immediate since $\deg P \ge 0$ .