2022 USAJMO Problems/Problem 2
Contents
[hide]Problem
Let and
be positive integers. The cells of an
grid are colored amber and bronze such that there are at least
amber cells and at least
bronze cells. Prove that it is possible to choose
amber cells and
bronze cells such that no two of the
chosen cells lie in the same row or column.
Solution 1: Pigeonhole
Let . There are
ways to select
cells such that no two are in the same row or column. Each such selection can be specified by
, a permutation of
, such that in the
row, the cell in column
is selected. Let
be the number of amber cells in the selection
. We just need to prove there exists a
such that
Using contradiction, assuming no such
exists.
In calculating , each amber cell is counted
times. We have
WLOG, let
. With the contradiction assumption
Similarly, let
.
One can always move from to
via a path in
space
such that in each step two numbers in the starting permutation are swapped to get the next permutation. For example if
one such path is
Then the value of
along the path changes by at most 2 in each step.
On the other hand since
, there is a gap of at least width 3 in the range of
. A path starting above the gap and ending below the gap with max step size two should not exist. Contradiction.
Therefore there must be an such that either
or
.
(Y)
Solution 2: Induction
Solution 3: Graph Theoretic
We can prove this statement by using the Hall's marriage theorem. Let us define a bipartite graph , where
is the set of rows of the grid,
is the set of columns of the grid, and
is the set of edges between
and
. We say that a row
is connected to a column
if and only if the cell in row
and column
is colored amber.
Now, we need to show that the conditions of Hall's marriage theorem are satisfied. That is, for any subset , the number of columns connected to
is at least
. To prove this, let
be any subset of
, and let
be the set of columns connected to
. Then, the number of amber cells in the rows of
is at least
, and the number of amber cells in the rows not in
is at least
. Therefore, the total number of amber cells is at least
, which is at least
by assumption. Hence, the number of columns connected to
is at least
.
Similarly, we can define a bipartite graph , where
is the set of rows of the grid, and an edge between a row
and a column
exists if and only if the cell in row
and column
is colored bronze. We can show that the conditions of Hall's marriage theorem are also satisfied for
.
Therefore, by Hall's marriage theorem, there exist matchings and
in
and
, respectively, such that each row and column in the grid is incident to at most one edge in
or
. Let
be the set of cells in the grid that are covered by
, and
be the set of cells in the grid that are covered by
. Then,
, since each matching covers a total of
cells. Moreover, no two cells in
or
lie in the same row or column, since each row and column is incident to at most one edge in
or
.
Finally, we can choose amber cells and
bronze cells from
and
, respectively, such that no two of the chosen cells lie in the same row or column. This is because
, and there are at least
amber cells in the grid and at least
bronze cells in the grid. Therefore, there are at least
cells colored amber in
, and at least
cells colored bronze in
. This implies that there are at least
amber cells in
and at least
bronze cells in
, so we can choose a subset of
amber cells from
and a subset of
bronze cells from
, such that no two of the chosen cells lie in the same row or column.