Difference between revisions of "2022 USAJMO Problems/Problem 2"
(Created page with "==Problem== Let <math>a</math> and <math>b</math> be positive integers. The cells of an <math>(a + b + 1)\times (a + b + 1)</math> grid are colored amber and bronze such that...") |
Mryang6859 (talk | contribs) (→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 | ||
+ | <cmath>A(p_i)=a,\text{ or } A(p_i)=a+1.</cmath> | ||
+ | Using contradiction, assuming no such <math>p_i</math> exists. | ||
+ | |||
+ | 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 only two of the numbers in the permutations are swapped. 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 <math>A</math> along the path changes by at most 2 in each step. But 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>. | ||
==Solution 2: Induction== | ==Solution 2: Induction== |
Revision as of 21:03, 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
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 only two of the numbers in the permutations are swapped. For example if
one such path is
Then the value
along the path changes by at most 2 in each step. But 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
.