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 5 of 5: Exhibit 3n planes that cover S and miss the origin

Previous step Next step

In plain words

Any grid point in $S$ has at least one coordinate in $\{1,\ldots,n\}$ , so the $3n$ axis-parallel planes for positive coordinates cover $S$ while missing $(0,0,0)$ .

x = i,\quad y = i,\quad z = i \qquad (i = 1, 2, \ldots, n)

Detailed analysis

The $3n$ planes $x=i$ , $y=i$ , $z=i$ for $i=1,\ldots,n$ all miss $(0,0,0)$ , and every $(x,y,z) \in S$ has $x+y+z > 0$ so at least one of $x, y, z$ lies in $\{1,\ldots,n\}$ , placing $(x,y,z)$ on one of these $3n$ planes. Together with $m \ge 3n$ from Step 4, the smallest possible number of planes is $3n$ .