Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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...")
 
(→‎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 $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 $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 only two of the numbers in the permutations are swapped. 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 $A$ along the path changes by at most 2 in each step. But 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$.

Solution 2: Induction

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2022_USAJMO_Problems/Problem_2&oldid=174576"