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 "2002 IMO Problems/Problem 1"

(→‎Actual Proof)
(→‎Proof sketch)
 
(2 intermediate revisions by the same user not shown)
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 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.  
+
Lastly, we will consider what it means to find the amount of subsets with different x coordinates and different y coordinates. It's worded really badly, but what it's trying to say is how many ways are there 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.
 
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.
Line 23: Line 23:
  
  
−
Lemma: We claim that there is a bijection between the sets of X={<math>a_x</math> | x} and Y={<math>a_y</math> | y}. We will prove this via induction on an arbitrary points colored red.
+
Lemma: We claim that the elements of the sets of X={<math>a_x</math> | x} and Y={<math>a_y</math> | y} are the same. We will prove this via induction on an arbitrary points colored red.
  
 
Start with the base case, where there are no red points. This is trivial. X=Y={1,2,3,...n} because the amount of points in <math>a_x=a_y</math>, or <math>a_1=a_1</math>, <math>a_2=a_2</math>, etc.
 
Start with the base case, where there are no red points. This is trivial. X=Y={1,2,3,...n} because the amount of points in <math>a_x=a_y</math>, or <math>a_1=a_1</math>, <math>a_2=a_2</math>, etc.
Line 31: Line 31:
  
  
−
Multiplying the elements in a set when there's a bijection between them means that they are equal. Therefore, AX=Y implies A=B.
+
Multiplying the elements in a set when their elements are the same means that they are equal. Therefore, <math>X=Y</math> implies <math>A=B</math>.
  
−
~Someone who is in love with JASMINE LI
+
~Wesserrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=2002|before=First Question|num-a=2}}
 
{{IMO box|year=2002|before=First Question|num-a=2}}

Latest revision as of 04:12, 6 December 2023

Problem

$S$ is the set of all $(h,k)$ with $h,k$ non-negative integers such that $h + k < n$. Each element of $S$ is colored red or blue, so that if $(h,k)$ is red and $h' \le h,k' \le k$, then $(h',k')$ is also red. A type $1$ subset of $S$ has $n$ blue elements with different first member and a type $2$ subset of $S$ has $n$ blue elements with different second member. Show that there are the same number of type $1$ and type $2$ 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. I probably don't need this "proof sketch" part, but I find IMO solutions to be extremely hard to interpret because they have a million (different) ideas going on with little justification, so here's my thought process going into the problem. Anyway, we can choose to interpret $h+k<n$ 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 $0$ 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 subsets with different x coordinates and different y coordinates. It's worded really badly, but what it's trying to say is how many ways are there to choose $n$ 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 $n$ points. In other words, to find $A$, the amount of points with distinct x-coordinates, just multiply the amount of blue dots in each row. To find $B$, 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 $a_x$ denote the amount of points with a given x-coordinate. Let $a_y$ denote the amount of points with a given y-coordinate.


Lemma: We claim that the elements of the sets of X={$a_x$ | x} and Y={$a_y$ | y} are the same. We will prove this via induction on an arbitrary points colored red.

Start with the base case, where there are no red points. This is trivial. X=Y={1,2,3,...n} because the amount of points in $a_x=a_y$, or $a_1=a_1$, $a_2=a_2$, etc.


Now for the inductive step. This is not so simple, however. Instead of considering an entire rectangle, we will focus on coloring one point. Call this point $(p,q)$. If we color a point red, then the amount of blue points in row p is going to be $a_x=n-(x+y)-1$, where as $a_y=n-(y+x)-1$. They're both the same! Repeatedly adding a point will give us any shape of red points that we want, or the amount of "blocky shapes". (Apparently called a young's tabeulux, idk what that is.) Therefore, we have completed the induction.


Multiplying the elements in a set when their elements are the same means that they are equal. Therefore, $X=Y$ implies $A=B$.

~Wesserrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2002_IMO_Problems/Problem_1&oldid=206564"