Difference between revisions of "2002 IMO Problems/Problem 1"
(→Proof sketch) |
(→Proof sketch) |
||
| Line 6: | Line 6: | ||
{{solution}} | {{solution}} | ||
===Proof sketch=== | ===Proof sketch=== | ||
| − | Okay this is going to be really bad because it's going to be one of my first solutions to an IMO problem, but basically, we can choose to interpret <math>h+k<n</math> graphically by | + | Okay this is going to be really bad because it's going to be one of my first solutions to an IMO problem, but basically, we can choose to interpret <math>h+k<n</math> graphically by graphing it on the coordinate plane. It turns out that it will just create a right isosceles triangle of lattice points that has legs of length n-1 and a right angle at the origin. This is simple because h and k have to be non negative, or <math>0</math> and above, while h+k<n will make a triangle. However, we can't count the points on the line since it's dotted. A lattice of blue points will look like this: |
{Insert diagram here, preferably at some lower n like n=5} | {Insert diagram here, preferably at some lower n like n=5} | ||
| Line 14: | Line 14: | ||
{Insert diagram here, like two rectangles, clearly highlighted points at n=5 along with their respective rectangles} | {Insert diagram here, like two rectangles, clearly highlighted points at n=5 along with their respective rectangles} | ||
| − | Lastly, we will consider what it means to find the | + | Lastly, we will consider what it means to find the amount of ways to choose <math>n</math> points with distinct coordinate points. This means that we will have to choose one point from each row or column because you have to choose strictly <math>n</math> points. In other words, to find <math>A</math>, the amount of points with distinct x-coordinates, just multiply the amount of blue dots in each row. To find <math>B</math>, the amount of points with distinct y-coordinates, just multiply the amount of blue dots in each column. |
| + | |||
| + | In summary, we need to prove that the product of blue dots in a row is equal to the product of red dots in a column. With some fiddling around, we can guess that we need to prove that there is a bijection between the two sets, which proves that A=B as a consequence. | ||
| + | |||
| + | ==Actual Proof== | ||
| + | Let <math>a_x</math> denote the amount of points with a given x-coordinate. Let <math>a_y</math> denote the amount of points with a given y-coordinate. | ||
| + | Lemma: We claim that <math>alpha</math> | ||
==See Also== | ==See Also== | ||
{{IMO box|year=2002|before=First Question|num-a=2}} | {{IMO box|year=2002|before=First Question|num-a=2}} | ||
Revision as of 04:37, 6 December 2023
Problem
is the set of all 
with 
non-negative integers such that 
. Each element of is colored red or blue, so that if is red and 
, then 
is also red. A type 
subset of has 
blue elements with different first member and a type 
subset of has blue elements with different second member. Show that there are the same number of type and type subsets.
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
Proof sketch
Okay this is going to be really bad because it's going to be one of my first solutions to an IMO problem, but basically, we can choose to interpret 
graphically by graphing it on the coordinate plane. It turns out that it will just create a right isosceles triangle of lattice points that has legs of length n-1 and a right angle at the origin. This is simple because h and k have to be non negative, or 
and above, while h+k<n will make a triangle. However, we can't count the points on the line since it's dotted. A lattice of blue points will look like this:
{Insert diagram here, preferably at some lower n like n=5}
Second, we will consider what happens if we color an arbitrary point red. The problem states that all points with coordinate points equal to less than that arbitrary point will be colored red. Graphically, this means that the point colored red, along with all the points that are in the rectangle containing the origin and point as their corners, will be colored red. Notice how coloring other nontrivial points red will just create a block shape that's all red for the triangle. An example is shown below
{Insert diagram here, like two rectangles, clearly highlighted points at n=5 along with their respective rectangles}
Lastly, we will consider what it means to find the amount of ways to choose points with distinct coordinate points. This means that we will have to choose one point from each row or column because you have to choose strictly points. In other words, to find 
, the amount of points with distinct x-coordinates, just multiply the amount of blue dots in each row. To find 
, the amount of points with distinct y-coordinates, just multiply the amount of blue dots in each column.
In summary, we need to prove that the product of blue dots in a row is equal to the product of red dots in a column. With some fiddling around, we can guess that we need to prove that there is a bijection between the two sets, which proves that A=B as a consequence.
Actual Proof
Let 
denote the amount of points with a given x-coordinate. Let 
denote the amount of points with a given y-coordinate.
Lemma: We claim that 
See Also
| 2002 IMO (Problems) • Resources | ||
| Preceded by First Question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
| All IMO Problems and Solutions | ||
