Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$.

Question

Let $n$ be a positive integer and $S$ the set of points $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers such that $x + y < n$. The points of $S$ are colored in red and blue so that if $(x, y)$ is red, then $(x', y')$ is red as long as $x'\leq x$ and $y'\leq y$. Let $A$ be the number of ways to choose $n$ blue points such that all their $x$-coordinates are different and let $B$ be the number of ways to choose $n$ blue points such that all their $y$-coordinates are different. Prove that $A = B$.

How one can set up a proof like this? I've tried but to me seems really hard...

Answer 1

This is the first problem of the $2002$ IMO. You can find various solutions here