Difference between revisions of "2022 USAJMO Problems/Problem 2"
Mryang6859 (talk | contribs) (→Solution 1: Pigeonhole) |
(→Solution 2) |
||
(6 intermediate revisions by 3 users not shown) | |||
Line 27: | Line 27: | ||
(Y) | (Y) | ||
− | ==Solution 2: | + | ==Solution 2== |
+ | We claim that it is possible to choose <math>a</math> amber cells such that no two lie in the same row or column. | ||
+ | |||
+ | Number the rows and columns from <math>1</math> to <math>a+b+1.</math> In cell <math>(x,y),</math> write the number <math>x+y\pmod{a+b+1}.</math> Then two same-numbered cells will be on different rows and columns. | ||
+ | |||
+ | There are <math>a+b+1</math> different numbers and <math>\geq a^2+ab-b = (a-1)(a+b+1)+1</math> amber cells. Using Pigeonhole, we have <math>a+b+1</math> holes, and cells in the same hole are in different rows and columns, and <math>\geq(a-1)(a+b+1)+1</math> pigeons, so there exists <math>a</math> 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 <math>a</math> amber cells and <math>b</math> bronze cells. If no two chosen cells lie in the same row or column then we are done. Otherwise, since there are <math>a+b+1</math> 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 <math>a</math> amber cells and <math>b</math> 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 <math>G = (A \cup B, E)</math>, where <math>A</math> is the set of rows of the grid, <math>B</math> is the set of columns of the grid, and <math>E</math> is the set of edges between <math>A</math> and <math>B</math>. We say that a row <math>a \in A</math> is connected to a column <math>b \in B</math> if and only if the cell in row <math>a</math> and column <math>b</math> is colored amber. | ||
+ | |||
+ | Now, we need to show that the conditions of Hall's marriage theorem are satisfied. That is, for any subset <math>S \subseteq A</math>, the number of columns connected to <math>S</math> is at least <math>|S|</math>. To prove this, let <math>S</math> be any subset of <math>A</math>, and let <math>T</math> be the set of columns connected to <math>S</math>. Then, the number of amber cells in the rows of <math>S</math> is at least <math>a|S|</math>, and the number of amber cells in the rows not in <math>S</math> is at least <math>b(a+b+1)-a|S|</math>. Therefore, the total number of amber cells is at least <math>a|S| + b(a+b+1)-a|S| = ab + b(a+b)</math>, which is at least <math>a^2+ab-b</math> by assumption. Hence, the number of columns connected to <math>S</math> is at least <math>b</math>. | ||
+ | |||
+ | Similarly, we can define a bipartite graph <math>G' = (A \cup B', E')</math>, where <math>B'</math> is the set of rows of the grid, and an edge between a row <math>a</math> and a column <math>b' \in B'</math> exists if and only if the cell in row <math>a</math> and column <math>b'</math> is colored bronze. We can show that the conditions of Hall's marriage theorem are also satisfied for <math>G'</math>. | ||
+ | |||
+ | Therefore, by Hall's marriage theorem, there exist matchings <math>M</math> and <math>M'</math> in <math>G</math> and <math>G'</math>, respectively, such that each row and column in the grid is incident to at most one edge in <math>M</math> or <math>M'</math>. Let <math>X</math> be the set of cells in the grid that are covered by <math>M</math>, and <math>Y</math> be the set of cells in the grid that are covered by <math>M'</math>. Then, <math>|X| = |Y| = a+b</math>, since each matching covers a total of <math>a+b</math> cells. Moreover, no two cells in <math>X</math> or <math>Y</math> lie in the same row or column, since each row and column is incident to at most one edge in <math>M</math> or <math>M'</math>. | ||
+ | |||
+ | Finally, we can choose <math>a</math> amber cells and <math>b</math> bronze cells from <math>X</math> and <math>Y</math>, respectively, such that no two of the chosen cells lie in the same row or column. This is because <math>|X| = |Y| = a+b</math>, and there are at least <math>a^2+ab-b</math> amber cells in the grid and at least <math>b^2+ab-a</math> bronze cells in the grid. Therefore, there are at least <math>a^2+ab-b</math> cells colored amber in <math>X</math>, and at least <math>b^2+ab-a</math> cells colored bronze in <math>Y</math>. This implies that there are at least <math>a</math> amber cells in <math>X</math> and at least <math>b</math> bronze cells in <math>Y</math>, so we can choose a subset of <math>a</math> amber cells from <math>X</math> and a subset of <math>b</math> bronze cells from <math>Y</math>, such that no two of the chosen cells lie in the same row or column. | ||
+ | |||
+ | ==See Also== | ||
+ | {{USAJMO newbox|year=2022|num-b=1|num-a=3}} | ||
+ | {{MAA Notice}} |
Latest revision as of 02:08, 9 January 2024
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.