Difference between revisions of "2022 USAJMO Problems/Problem 2"

Latest revision as of 01:08, 9 January 2024

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 1: Pigeonhole

Let $n=a+b+1$ . There are $n!$ ways to select $n$ cells such that no two are in the same row or column. Each such selection can be specified by $p_i=(p_{i1},p_{i2},\cdots,p_{in})$ , a permutation of $1,2,3,\cdots,n$ , such that in the $k^\text{th}$ row, the cell in column $p_{ik}$ is selected. Let $A(p_i)$ be the number of amber cells in the selection $p_i$ . We just need to prove there exists a $p_i$ such that $A(p_i)=a,\text{ or } A(p_i)=a+1.$ Using contradiction, assuming no such $p_i$ exists.

In calculating $\sum A(p_i)$ , each amber cell is counted $(n-1)!$ times. We have $\sum A(p_i) \ge (n-1)!(a^2+ab-b).$ $\Rightarrow\max(A(p_i))\ge\left\lceil\frac{(n-1)!(a^2+ab-b)}{n!}\right\rceil=\left\lceil\frac{n(a-1)+1}{n}\right\rceil = a.$ WLOG, let $A(p_1)=\max(A(p_i))$ . With the contradiction assumption $A(p_1)\ge a+2.$ Similarly, let $A(p_2)=\min(A(p_i))$ . $\sum A(p_i) \le (n-1)![n^2-(b^2+ab-a)] \Rightarrow \min(A(p_i))\le a+1 \Rightarrow A(p_2)\le a-1.$

One can always move from $p_1$ to $p_2$ via a path in $p$ space $p_1\rightarrow q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_k \rightarrow p_2$ such that in each step two numbers in the starting permutation are swapped to get the next permutation. For example if $p_1=(5,4,3,1,2), p_2=(1,2,3,4,5)$ one such path is $(5,4,3,1,2)\rightarrow (1,4,3,5,2) \rightarrow (1,2,3,5,4) \rightarrow (1,2,3,4,5).$ Then the value of $A$ along the path changes by at most 2 in each step. On the other hand since $A(p_i)\neq a, a+1$ , there is a gap of at least width 3 in the range of $A$ . 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 $i$ such that either $A(p_i)=a$ or $A(p_i)=a+1$ . (Y)

Solution 2

We claim that it is possible to choose $a$ amber cells such that no two lie in the same row or column.

Number the rows and columns from $1$ to $a+b+1.$ In cell $(x,y),$ write the number $x+y\pmod{a+b+1}.$ Then two same-numbered cells will be on different rows and columns.

There are $a+b+1$ different numbers and $\geq a^2+ab-b = (a-1)(a+b+1)+1$ amber cells. Using Pigeonhole, we have $a+b+1$ holes, and cells in the same hole are in different rows and columns, and $\geq(a-1)(a+b+1)+1$ pigeons, so there exists $a$ 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 $a$ amber cells and $b$ bronze cells. If no two chosen cells lie in the same row or column then we are done. Otherwise, since there are $a+b+1$ 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 $a$ amber cells and $b$ 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 $G = (A \cup B, E)$ , where $A$ is the set of rows of the grid, $B$ is the set of columns of the grid, and $E$ is the set of edges between $A$ and $B$ . We say that a row $a \in A$ is connected to a column $b \in B$ if and only if the cell in row $a$ and column $b$ is colored amber.

Now, we need to show that the conditions of Hall's marriage theorem are satisfied. That is, for any subset $S \subseteq A$ , the number of columns connected to $S$ is at least $|S|$ . To prove this, let $S$ be any subset of $A$ , and let $T$ be the set of columns connected to $S$ . Then, the number of amber cells in the rows of $S$ is at least $a|S|$ , and the number of amber cells in the rows not in $S$ is at least $b(a+b+1)-a|S|$ . Therefore, the total number of amber cells is at least $a|S| + b(a+b+1)-a|S| = ab + b(a+b)$ , which is at least $a^2+ab-b$ by assumption. Hence, the number of columns connected to $S$ is at least $b$ .

Similarly, we can define a bipartite graph $G' = (A \cup B', E')$ , where $B'$ is the set of rows of the grid, and an edge between a row $a$ and a column $b' \in B'$ exists if and only if the cell in row $a$ and column $b'$ is colored bronze. We can show that the conditions of Hall's marriage theorem are also satisfied for $G'$ .

Therefore, by Hall's marriage theorem, there exist matchings $M$ and $M'$ in $G$ and $G'$ , respectively, such that each row and column in the grid is incident to at most one edge in $M$ or $M'$ . Let $X$ be the set of cells in the grid that are covered by $M$ , and $Y$ be the set of cells in the grid that are covered by $M'$ . Then, $|X| = |Y| = a+b$ , since each matching covers a total of $a+b$ cells. Moreover, no two cells in $X$ or $Y$ lie in the same row or column, since each row and column is incident to at most one edge in $M$ or $M'$ .

Finally, we can choose $a$ amber cells and $b$ bronze cells from $X$ and $Y$ , respectively, such that no two of the chosen cells lie in the same row or column. This is because $|X| = |Y| = a+b$ , and there are at least $a^2+ab-b$ amber cells in the grid and at least $b^2+ab-a$ bronze cells in the grid. Therefore, there are at least $a^2+ab-b$ cells colored amber in $X$ , and at least $b^2+ab-a$ cells colored bronze in $Y$ . This implies that there are at least $a$ amber cells in $X$ and at least $b$ bronze cells in $Y$ , so we can choose a subset of $a$ amber cells from $X$ and a subset of $b$ bronze cells from $Y$ , such that no two of the chosen cells lie in the same row or column.

@@ Line 3: / Line 3: @@
 ==Solution 1: Pigeonhole==
+Let <math>n=a+b+1</math>. There are <math>n!</math> ways to select <math>n</math> cells such that no two are in the same row or column. Each such selection can be specified by <math>p_i=(p_{i1},p_{i2},\cdots,p_{in})</math>, a permutation of <math>1,2,3,\cdots,n</math>, such that in the <math>k^\text{th}</math> row, the cell in column <math>p_{ik}</math> is selected. Let <math>A(p_i)</math> be the number of amber cells in the selection <math>p_i</math>. We just need to prove there exists a <math>p_i</math> such that
+<cmath>A(p_i)=a,\text{ or } A(p_i)=a+1.</cmath>
+Using contradiction, assuming no such <math>p_i</math> exists.
-==Solution 2: Induction==
+In calculating <math>\sum A(p_i)</math>, each amber cell is counted <math>(n-1)!</math> times. We have
+<cmath>\sum A(p_i) \ge (n-1)!(a^2+ab-b).</cmath>
+<cmath>\Rightarrow\max(A(p_i))\ge\left\lceil\frac{(n-1)!(a^2+ab-b)}{n!}\right\rceil=\left\lceil\frac{n(a-1)+1}{n}\right\rceil = a.</cmath>
+WLOG, let <math>A(p_1)=\max(A(p_i))</math>. With the contradiction assumption
+<cmath>A(p_1)\ge a+2.</cmath>
+Similarly, let <math>A(p_2)=\min(A(p_i))</math>.
+<cmath>\sum A(p_i) \le (n-1)![n^2-(b^2+ab-a)] \Rightarrow \min(A(p_i))\le a+1 \Rightarrow A(p_2)\le a-1.</cmath>
+One can always move from <math>p_1</math> to <math>p_2</math> via a path in <math>p</math> space
+<cmath>p_1\rightarrow q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_k \rightarrow p_2</cmath>
+such that in each step two numbers in the starting permutation are swapped to get the next permutation. For example if
+<cmath>p_1=(5,4,3,1,2), p_2=(1,2,3,4,5)</cmath>
+one such path is
+<cmath>(5,4,3,1,2)\rightarrow (1,4,3,5,2) \rightarrow (1,2,3,5,4) \rightarrow (1,2,3,4,5).</cmath>
+Then the value of <math>A</math> along the path changes by at most 2 in each step.
+On the other hand since <math>A(p_i)\neq a, a+1</math>, there is a gap of at least width 3 in the range of <math>A</math>. 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 <math>i</math> such that either <math>A(p_i)=a</math> or <math>A(p_i)=a+1</math>.
+(Y)
+==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}}

2022 USAJMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search