Difference between revisions of "2007 IMO Problems/Problem 6"
m (→Solution: corrected a grammatical mistake) |
|||
Line 8: | Line 8: | ||
==Solution== | ==Solution== | ||
− | We | + | We will 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> | '''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> |
Revision as of 07:39, 13 April 2015
Problem
Let be a positive integer. Consider
as a set of
points in three-dimensional space.
Determine the smallest possible number of planes, the union of which contain
but does not include
.
Solution
We will prove the result using the following Lemma, which has an easy proof by induction.
Lemma Let ,
and
. If
is a polynomial in
that vanishes on all points of the grid
except at the origin, then
Proof. We will prove this by induction on . If
, then the result follows trivially. Say
.
WLOG, we can assume that
.
By polynomial division over
we can write
Since
is a monomial, the remainder
must be a constant in
, i.e.,
is a polynomial in two variables
,
.
Pick an element of
of the form
and substitute it in the equation. Since
vanishes on all such points, we get that
for all
.
Let
and
.
For every point
in
we have
where
.
Therefore, the polynomial
vanishes on all points of
except the origin. By induction hypothesis, we must have
. But,
and hence we have
.
Now, to solve the problem let be
planes that cover all points of
except the origin. Since these planes don't pass through origin, each
can be written as
. Define
to be the polynomial
. Then
vanishes at all points of
except at the origin, and hence
.
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 |