2002 IMO Problems/Problem 1

Revision as of 03:14, 6 December 2023 by Wes (talk | contribs) (Solution)

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, but basically, we can choose to interpret $h+k<n$ graphically by putting it on the graph. 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 missing from the triangle. An example is shown below

{Insert diagram here, like two rectangles, clearly highlighted points at n=5}

Lastly,

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