2022 USAJMO Problems/Problem 2
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
We claim that it is possible to choose amber cells such that no two lie in the same row or column.
Number the rows and columns from to In cell write the number Then two same-numbered cells will be on different rows and columns.
There are different numbers and amber cells. Using Pigeonhole, we have holes, and cells in the same hole are in different rows and columns, and pigeons, so there exists amber cells such that no two lie in the same row or column. Similarly, there exists b bronze cells such that no two lie in the same row or column.
Choose those amber cells and bronze cells. If no two chosen cells lie in the same row or column then we are done. Otherwise, since there are rows and columns, there exists a row and a column with no chosen cell. If their intersection is an amber cell, choose that cells and unchoose an amber cell that is in the same row or column as a bronze cell. If the intersection is a bronze cell, choose that cell and unchoose a chosen bronze cell that is in the same row or column as an amber cell. Repeating this process, we can obtain amber cells and bronze cells such that no two lie in the same row or column.
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.
See Also
2022 USAJMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.