Difference between revisions of "2007 IMO Problems/Problem 6"
m |
|||
Line 20: | Line 20: | ||
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>. | 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>. | 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>. | ||
==Solution2== | ==Solution2== | ||
let <math>x_n</math> be ways of doing so, we see easily <math>x_n</math>=<math>x_{n-1}</math> +3 hence <math>x_n</math> = 3n +c put n=1, c=0 hence answer is 3n. ~SANSGANKRSNGUPTA | let <math>x_n</math> be ways of doing so, we see easily <math>x_n</math>=<math>x_{n-1}</math> +3 hence <math>x_n</math> = 3n +c put n=1, c=0 hence answer is 3n. ~SANSGANKRSNGUPTA | ||
− | |||
− | |||
Revision as of 10:30, 23 March 2024
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 .
Solution2
let be ways of doing so, we see easily = +3 hence = 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 |