2007 IMO Problems/Problem 6

Problem

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 contain $S$ but does not include $(0,0,0)$ .

Solution

We will prove the result using the following Lemma, which has an easy proof by induction.

Lemma Let $S_1 = \{0, 1, \ldots, n_1\}$ , $S_2 = \{0, 1, \ldots, n_2\}$ and $S_3 = \{0, 1, \ldots, n_3\}$ . If $P$ is a polynomial in $\mathbb{R}[x, y, z]$ that vanishes on all points of the grid $S = S_1 \times S_2 \times S_3$ except at the origin, then $\deg P \geq n_1 + n_2 + n_3.$

Proof. We will prove this by induction on $n = n_1 + n_2 + n_3$ . If $n = 0$ , then the result follows trivially. Say $n > 0$ . WLOG, we can assume that $n_1 > 0$ . By polynomial division over $\mathbb{R}[y, z][x]$ we can write $P = (x - n_1)Q + R.$ Since $x-n_1$ is a monomial, the remainder $R$ must be a constant in $\mathbb{R}[y, z]$ , i.e., $R$ is a polynomial in two variables $y$ , $z$ . Pick an element of $S$ of the form $(n_1, y, z)$ and substitute it in the equation. Since $P$ vanishes on all such points, we get that $R(y, z) = 0$ for all $(y, z) \in S_2 \times S_3$ . Let $S_1' = \{0, 1, \ldots, n_1 - 1\}$ and $S' = S_1' \times S_2 \times S_3$ . For every point $(x, y, z)$ in $S'$ we have $P(x, y, z) = (x - n_1)Q(x, y, z) + R(y, z) = (x-n_1)Q(x, y, z),$ where $x - n_1 \neq 0$ . Therefore, the polynomial $Q$ vanishes on all points of $S'$ except the origin. By induction hypothesis, we must have $\deg Q \geq n_1 - 1 + n_2 + n_3$ . But, $\deg P \geq \deg Q + 1$ and hence we have $\deg P \geq n_1 + n_2 + n_3$ .

Now, to solve the problem let $H_1, \ldots, H_m$ be $m$ planes that cover all points of $S$ except the origin. Since these planes don't pass through origin, each $H_i$ can be written as $a_i x + b_i y + c_i z = 1$ . Define $P$ to be the polynomial $\prod (a_ix + b_iy + c_iz - 1)$ . Then $P$ vanishes at all points of $S$ except at the origin, and hence $\deg P = m \geq 3n$ .

Solution2( please check)

let $x_n$ be ways of doing so, we see easily $x_n$ = $x_{n-1}$ +3 hence $x_n$ = 3n +c put n=1, c=0 hence answer is 3n. ~SANSGANKRSNGUPTA

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2007 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

2007 IMO Problems/Problem 6

Problem

Solution

Solution2( please check)