Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 IMO Problems/Problem 6"

(Created page with "== Problem == Let <math>n</math> be a positive integer. Consider <cmath>S=\{(x,y,z)~:~x,y,z\in \{0,1,\ldots,n \},~x+y+z>0\}</cmath> as a set of <math>(n+1)^3-1</math> points in ...")
 
Line 7: Line 7:
  
 
==Solution==
 
==Solution==
 +
 +
We would prove the result using the following Lemma, which has an easy proof by induction.
 +
 +
'''Lemma''' Let <math>S_1 = \{0, 1, \ldots, n_1\}</math>, <math>S_2 = \{0, 1, \ldots, n_2\}</math> and <math>S_3 = \{0, 1, \ldots, n_3\}</math>. If <math>P</math> is a polynomial in <math>\mathbb{R}[x, y, z]</math> that vanishes on all points of the grid <math>S = S_1 \times S_2 \times S_3</math> except at the origin, then <cmath>\deg P \geq n_1 + n_2 + n_3.</cmath>
 +
 +
''Proof.''  We will prove this by induction on <math>n = n_1 + n_2 + n_3</math>. If <math>n = 0</math>, then the result follows trivially. Say <math>n > 0</math>.
 +
WLOG, we can assume that <math>n_1 > 0</math>.
 +
By polynomial division over <math>\mathbb{R}[y, z][x]</math> we can write <cmath>P = (x - n_1)Q + R.</cmath>
 +
Since <math>x-n_1</math> is a monomial, the remainder <math>R</math> must be a constant in <math>\mathbb{R}[y, z]</math>, i.e., <math>R</math> is a polynomial in two variables <math>y</math>, <math>z</math>.
 +
Pick an element of <math>S</math> of the form <math>(n_1, y, z)</math> and substitute it in the equation. Since <math>P</math> vanishes on all such points, we get that <math>R(y, z) = 0</math> for all <math>(y, z) \in S_2 \times S_3</math>.
 +
Let <math>S_1' = \{0, 1, \ldots, n_1 - 1\}</math> and <math>S' = S_1' \times S_2 \times S_3</math>.
 +
For every point <math>(x, y, z)</math> in <math>S'</math> we have <cmath>P(x, y, z) = (x - n_1)Q(x, y, z) + R(y, z) = (x-n_1)Q(x, y, z),</cmath> where <math>x - n_1 \neq 0</math>.
 +
Therefore, the polynomial <math>Q</math> vanishes on all points of <math>S'</math> except the origin. By induction hypothesis, we must have <math>\deg Q \geq n_1 - 1 + n_2 + n_3</math>. But, <math>\deg P \geq \deg Q + 1</math> and hence we have <math>\deg P \geq n_1 + n_2 + n_3</math>.
 +
 +
 +
 +
Now, to solve the problem let <math>H_1, \ldots, H_m</math> be <math>m</math> planes that cover all points of <math>S</math> except the origin. Since these planes don't pass through origin, each <math>H_i</math> can be written as <math>a_i x + b_i y + c_i z = 1</math>. Define <math>P</math> to be the polynomial <math>\prod (a_ix + b_iy + c_iz - 1)</math>. Then <math>P</math> vanishes at all points of <math>S</math> except at the origin, and hence <math>\deg P = m \geq 3n</math>.
 +
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 06:17, 13 April 2015

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 would 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$.


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
Problem 6
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_IMO_Problems/Problem_6&oldid=69915"