2022 USAMO Problems/Problem 1

Problem

Let $a$ and $b$ be positive integers. The cells of an $(a+b+1)\times (a+b+1)$ grid are colored amber and bronze such that there are at least $a^2+ab-b$ amber cells and at least $b^2+ab-a$ bronze cells. Prove that it is possible to choose $a$ amber cells and $b$ bronze cells such that no two of the $a+b$ chosen cells lie in the same row or column.

Solution

https://www.youtube.com/watch?v=137-z4WahKQ

Solution 2

We proceed with induction. Base case: $a=b=1$ . We fill in a 3x3 grid that has at least one bronze and one amber cell. We choose one bronze and one amber cell. Note that if the given bronze and amber cells are not in the same row or column, we are done. However, if they are, consider a cell that is not in the same row or column as either cell. Regardless of the color of the cell, we can match it with an opposing color cell, hence proved.

Induction case: Given the assertion for $(a, b)$ is true, then $(a+1, b)$ is true as well. Label each cell in the $(a+b+1)(a+b+1)$ grid as either red, blue, or white. There must be exactly $a^2+ab-b$ red cells, $b^2+ab-a$ blue cells, and $(a+b+1)(a+b+1)-(a^2+ab-b)-(b^2+ab-a) = 3(a+b) + 1$ white cells. We show that we can achieve a combination regardless of the amber/bronze of the white cells.

Case 1: There are three or more white cells present in either the bottommost row or rightmost column. Let's ignore the bottom most row and rightmost column, and focus on the $(a+b+1)(a+b+1)$ grid of squares on the topleft. By the induction assumption, we know that this grid must have $a$ amber and $b$ bronze not in the same row or column pairwise. [cont]

Page

Toolbox

Search

2022 USAMO Problems/Problem 1

Problem

Solution

Solution 2