IMO 2002 Problem 1
The previous approach fails because it moves between different colorings instead of staying inside a fixed configuration.
Proposed by: -
Verified: no
Verdicts: FAIL + PASS
Solve time: 8m44s
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.
Exploration
The previous approach fails because it moves between different colorings instead of staying inside a fixed configuration. A correction must compare type $1$ and type $2$ subsets within the same blue region.
Small cases clarify the structure. When $n=1$, $S={(0,0)}$ and either the point is red or blue. In the blue case both type $1$ and type $2$ subsets are either empty or contain the single point, so equality holds.
When $n=2$, $S={(0,0),(0,1),(1,0)}$. Any admissible coloring is an order ideal in this poset, so the red set is one of the initial segments closed downward. Direct inspection shows that choosing one blue point per column is equivalent to choosing a system of representatives in a $2\times 2$ matrix with a forbidden position pattern, and the same holds for rows after transposition of that matrix. The structure suggests a matrix-based symmetry rather than a geometric one.
This eliminates the need to transport the coloring. The correct invariant object is the incidence matrix of blue points, where symmetry comes from transposition.
Problem Understanding
The set $S$ consists of lattice points $(h,k)$ with $0 \le h,k \le n-1$ and $h+k<n$. A subset is red if it is downward closed in both coordinates, so the blue set is the complement of an order ideal in this triangular grid.
A type $1$ subset is a selection of $n$ blue points with all first coordinates distinct. Since there are exactly $n$ possible first coordinates, this means exactly one blue point is chosen in each column. A type $2$ subset is exactly one blue point in each row.
The task is to prove that for every fixed admissible coloring, the number of such column-complete selections equals the number of row-complete selections.
Key Observations
Each coloring determines an $n \times n$ $0$-$1$ matrix $A$ defined by $A_{h,k}=1$ if $(h,k)$ is blue and $A_{h,k}=0$ if it is red. The order ideal condition restricts which matrices can occur, but the counting problem depends only on the support of $A$.
A type $1$ subset corresponds exactly to a permutation $\sigma$ of ${0,\dots,n-1}$ such that $A_{h,\sigma(h)}=1$ for every $h$. Thus type $1$ subsets are permutation matrices supported inside $A$.
A type $2$ subset corresponds exactly to a permutation $\tau$ such that $A_{\tau(k),k}=1$ for every $k$. This is the same condition applied to the transpose matrix $A^{\mathsf T}$.
The essential fact is that counting permutation-supported selections is invariant under matrix transposition.
Solution
Let $A$ be the $n \times n$ matrix defined by
$$A_{h,k} = \begin{cases} 1 & \text{if } (h,k)\text{ is blue},\ 0 & \text{if } (h,k)\text{ is red}. \end{cases}$$
A type $1$ subset is a set of $n$ blue points with distinct first coordinates. Since there are exactly $n$ possible first coordinates, such a subset selects exactly one blue point in each column index $h$. This is equivalent to choosing a permutation $\sigma$ of ${0,1,\dots,n-1}$ such that for every $h$ the entry $(h,\sigma(h))$ is blue, or equivalently $A_{h,\sigma(h)}=1$ for all $h$.
Thus the number of type $1$ subsets equals the number of permutations $\sigma$ satisfying
$$\prod_{h=0}^{n-1} A_{h,\sigma(h)} = 1.$$
A type $2$ subset is a set of $n$ blue points with distinct second coordinates. Since there are $n$ possible second coordinates, this corresponds to choosing exactly one blue point in each row index $k$, which is equivalent to a permutation $\tau$ such that $A_{\tau(k),k}=1$ for all $k$.
Thus the number of type $2$ subsets equals the number of permutations $\tau$ satisfying
$$\prod_{k=0}^{n-1} A_{\tau(k),k} = 1.$$
Now consider the transpose matrix $A^{\mathsf T}$ defined by $(A^{\mathsf T}){k,h}=A{h,k}$. A permutation $\sigma$ contributes to a type $1$ subset if and only if it satisfies
$$\prod_{h=0}^{n-1} A_{h,\sigma(h)} = 1,$$
which is equivalent to
$$\prod_{h=0}^{n-1} (A^{\mathsf T})_{\sigma(h),h} = 1.$$
Writing $\tau=\sigma^{-1}$, this becomes
$$\prod_{k=0}^{n-1} (A^{\mathsf T})_{\tau(k),k} = 1.$$
This shows that permutations contributing to type $1$ subsets for $A$ are in bijection with permutations contributing to type $2$ subsets for $A^{\mathsf T}$.
Finally, transposition does not change the number of such permutations, since inversion of permutations gives a bijection between $\sigma$ and $\sigma^{-1}$, and the defining condition is preserved under exchanging indices. Therefore the number of valid permutations for $A$ equals the number for $A^{\mathsf T}$, which is exactly the equality between type $1$ and type $2$ counts for the original coloring.
This completes the proof. ∎
Verification of Key Steps
The encoding of type $1$ subsets as permutations is exact because distinct first coordinates force each column index to be used exactly once among $n$ selected points, leaving no possibility of omission or repetition.
The translation from blue-point selections to permutation conditions depends only on membership in the support of $A$, not on the downward-closure structure, so no hidden assumption about the red set is used in the counting step.
The passage from $A$ to $A^{\mathsf T}$ preserves validity conditions entrywise, since $(A^{\mathsf T}){k,h}=A{h,k}$ by definition. The inversion map $\sigma \mapsto \sigma^{-1}$ is a bijection on the symmetric group, ensuring no loss or duplication of admissible selections.
The identification of type $2$ selections with permutations in the transpose formulation is consistent with the index swap and uses the same support condition without alteration.
Alternative Approaches
A different method interprets admissible colorings as Ferrers diagrams inside an $n \times n$ triangle and applies the theory of permutation matrices in Ferrers bipartite graphs, where equality follows from invariance of the permanent under matrix transposition.
Another approach uses order ideals in the product poset to describe the boundary path of the red region and reformulates both types of selections as non-attacking rook placements in complementary regions, again reducing the problem to symmetry of rook polynomials under transposition.