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 1 of 5: Convert a plane cover avoiding the origin into a polynomial

Previous step Next step

In plain words

Any plane missing $(0,0,0)$ has equation $a_i x + b_i y + c_i z = 1$ , so multiplying the linear factors turns a union of $m$ planes covering $S$ into a degree- $m$ polynomial vanishing on $S$ but nonzero at $(0,0,0)$ .

P(x,y,z) = \prod_{i=1}^m (a_i x + b_i y + c_i z - 1), \qquad \deg P = m, \quad P|_S = 0, \quad P(0,0,0) = (-1)^m \ne 0

Detailed analysis

Let $m$ planes $H_1,\ldots,H_m$ cover $S$ and miss $(0,0,0)$ . Each $H_i$ can be written as $a_i x + b_i y + c_i z = 1$ . Then $P(x,y,z) = \prod_{i=1}^m (a_i x + b_i y + c_i z - 1)$ has degree $m$ , vanishes at every point of $S$ (since each point of $S$ lies on some $H_i$ ), and satisfies $P(0,0,0) = (-1)^m \ne 0$ .