Difference between revisions of "2022 USAMO Problems/Problem 1"
(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 there ar...") |
|||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
https://www.youtube.com/watch?v=137-z4WahKQ | https://www.youtube.com/watch?v=137-z4WahKQ | ||
| + | |||
| + | ==Solution 2== | ||
| + | We proceed with induction. | ||
| + | Base case: <math>a=b=1</math>. | ||
| + | We fill in a 3x3 grid that has at least one bronze and one amber cell. We choose one bronze and one amber cell. Note that if the given bronze and amber cells are not in the same row or column, we are done. However, if they are, consider a cell that is not in the same row or column as either cell. Regardless of the color of the cell, we can match it with an opposing color cell, hence proved. | ||
| + | |||
| + | Induction case: Given the assertion for <math>(a, b)</math> is true, then <math>(a+1, b)</math> is true as well. | ||
| + | Label each cell in the <math>(a+b+1)(a+b+1)</math> grid as either red, blue, or white. There must be exactly <math>a^2+ab-b</math> red cells, <math>b^2+ab-a</math> blue cells, and <math>(a+b+1)(a+b+1)-(a^2+ab-b)-(b^2+ab-a) = 3(a+b) + 1</math> white cells. We show that we can achieve a combination regardless of the amber/bronze of the white cells. | ||
| + | |||
| + | Case 1: There are three or more white cells present in either the bottommost row or rightmost column. | ||
| + | Let's ignore the bottom most row and rightmost column, and focus on the <math>(a+b+1)(a+b+1)</math> grid of squares on the topleft. By the induction assumption, we know that this grid must have <math>a</math> amber and <math>b</math> bronze not in the same row or column pairwise. | ||
| + | [cont] | ||
Latest revision as of 10:14, 21 September 2023
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
https://www.youtube.com/watch?v=137-z4WahKQ
Solution 2
We proceed with induction.
Base case: 
.
We fill in a 3x3 grid that has at least one bronze and one amber cell. We choose one bronze and one amber cell. Note that if the given bronze and amber cells are not in the same row or column, we are done. However, if they are, consider a cell that is not in the same row or column as either cell. Regardless of the color of the cell, we can match it with an opposing color cell, hence proved.
Induction case: Given the assertion for 
is true, then 
is true as well.
Label each cell in the 
grid as either red, blue, or white. There must be exactly red cells, blue cells, and 
white cells. We show that we can achieve a combination regardless of the amber/bronze of the white cells.
Case 1: There are three or more white cells present in either the bottommost row or rightmost column.
Let's ignore the bottom most row and rightmost column, and focus on the grid of squares on the topleft. By the induction assumption, we know that this grid must have amber and bronze not in the same row or column pairwise.
[cont]
