Difference between revisions of "2022 USAJMO Problems/Problem 2"
Mryang6859 (talk | contribs) (→Solution 1: Pigeonhole) |
Mryang6859 (talk | contribs) m (→Solution 1: Pigeonhole) |
||
| Line 3: | Line 3: | ||
==Solution 1: Pigeonhole== | ==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 <math>p_i</math> such that | + | 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> | <cmath>A(p_i)=a,\text{ or } A(p_i)=a+1.</cmath> | ||
Using contradiction, assuming no such <math>p_i</math> exists. | Using contradiction, assuming no such <math>p_i</math> exists. | ||
| Line 17: | Line 17: | ||
One can always move from <math>p_1</math> to <math>p_2</math> via a path in <math>p</math> space | 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> | <cmath>p_1\rightarrow q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_k \rightarrow p_2</cmath> | ||
| − | such that in each step | + | 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> | <cmath>p_1=(5,4,3,1,2), p_2=(1,2,3,4,5)</cmath> | ||
one such path is | 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> | <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 <math>A</math> along the path changes by at most 2 in each step. | + | 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>. | 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>. | ||
==Solution 2: Induction== | ==Solution 2: Induction== | ||
Revision as of 21:14, 9 June 2022
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
![\[A(p_i)=a,\text{ or } A(p_i)=a+1.\]](http://latex.artofproblemsolving.com/3/0/7/30759590b19717864da037143a3cd2cdb79058ec.png)
Using contradiction, assuming no such exists.
In calculating 
, each amber cell is counted 
times. We have
![\[\sum A(p_i) \ge (n-1)!(a^2+ab-b).\]](http://latex.artofproblemsolving.com/6/9/9/699966e3a75f0299b73e294d3078c44268aaf3a8.png)
![\[\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.\]](http://latex.artofproblemsolving.com/1/d/c/1dc184a038597052aa510a73fb9b4e8a5e9fbe4c.png)
WLOG, let 
. With the contradiction assumption
![\[A(p_1)\ge a+2.\]](http://latex.artofproblemsolving.com/c/9/3/c93da6f302d5c5a6bb53c7c5b08bc51bc98c97d8.png)
Similarly, let 
.
![\[\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.\]](http://latex.artofproblemsolving.com/1/0/c/10c3b80b02637a1e83c597fbefbe382b593585ba.png)
One can always move from 
to 
via a path in 
space
![\[p_1\rightarrow q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_k \rightarrow p_2\]](http://latex.artofproblemsolving.com/1/9/a/19a509de37326d806587bea29cca382b8daaf6aa.png)
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)\]](http://latex.artofproblemsolving.com/6/8/d/68d032cf2da8fc3c3516d2933db5569878b2bef3.png)
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).\]](http://latex.artofproblemsolving.com/7/6/f/76fcd2e5cafc667cf3c71a3cc1b0a9b45a084a92.png)
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 
.
