Define permutations $\pi \in [a+b+1]$ on the grid in an obvious way. We want a permutation which has either $a$ A's and $b+1$ B's or $a+1$ A's and $b$ B's. Define the score of a permutation $s_A(\pi)$ to be the number of A's in it. We want $s_A(\pi) \in \{a,a+1\}$ for some $\pi$. Claim: There exists $\pi_1$ with $s_A(\pi_1) \le a-1$, and there exists $\pi_2$ with $s_A(\pi_2) \ge a+2$. Proof: This is due to global reasons. Call $\mathcal{A}$ and $\mathcal{B}$ the set of A's and B's on the grid, respectively. Note that over all $\pi\in [a+b+1]$ randomly chosen, \[ \mathbb{E}[s_A(\pi)] = \mathbb{E}\left[\sum_{i=1}^{a+b+1} \mathbf{1}_{(i,\pi(i))=``A"} \right] = \sum_{i=1}^{a+b+1} \text{Pr}[(i,\pi(i))=``A"] = \frac{|\mathcal{A}|}{(a+b+1)^2} \ge a-1+\frac{1}{a+b+1}\]since $|\mathcal{A}| \ge a^2+ab-b$. Therefore there must exist at least one $\pi_1$ for which $s_A(\pi_1) \le a-1$. A similar argument for $B$ gives $\mathbb{E}[s_B(\pi)] \ge b-1+\tfrac{1}{a+b+1}$, but since $s_A(\pi)+s_B(\pi)=a+b+1$, we get $\mathbb{E}[s_A(\pi)] \le a+2-\tfrac{1}{a+b+1}$, so there exists some $\pi_2$ with $s_A(\pi_2)\ge a+2$. $\blacksquare$ Now the main idea is to notice that for any transposition $(x,y)$, \[ |s_A(\pi) - s_A(\pi \circ (x,y))| \le 2, \]which is a very obvious bound. Hence, by performing transpositions to get $\pi_1\to \pi_2$, we must hit either a score of $a$ or $a+1$ at some step.

Let a chain be a set of $a+b+1$ cells that do not share rows or columns. Note that $a^2+ab-b = (a-1)(a+b+1) + 1$ and $b^2+ab-a = (b-1)(a+b+1)+1$. By Expected Value, there exists a chain with $\geq a$ amber cells, and a chain with $\geq b$ bronze cells. Note that we can get from the first chain to the second chain by swapping one set of corners in a rectangle to another set of corners in a rectangle, and each time the number of amber cells changes by at most 2. Thus, at least one of $(a,b+1)$ or $(a+1,b)$ will appear as the number of (ambers, bronzes), which finishes. I totally didn't die in contest by hard focusing on induction

I've heard this problem was 25 MOHS?

I figured this one out like 15 minutes before the contest ended, and rushed up my induction solution by deleting stuff. one case was fine, the other case works out but i totally got a wrong argument. it's fixable but I didn't have time (didn't actually realize this) Also did not do induction base case, just called it trivial for the "degenerate" cases of a=0 and b=0 (fairly sure my cases work for deleting when a=1 or b=1) How many points? 20-25M imo, i'd personally lean towards 25. Possibly the hardest j2/5 ever

Jeez, this was really hard. Induction on a+b+1 actually works. Here is a sketch: Either - # of amber cells >= a^2+ab+a+b+1 - # of bronze cells >= b^2+ab+a+b+1 (Due to symmetry there is no loss of generality.) Assume # of bronze cells is the condition satisfied. Then we remove an amber cell; we will never lose too many bronze cells (we can lose 2(a+b) and still satisfy the bronze bound w/ our new grid). Then you can do some EV argument on # of amber cells removed; it will always be possible to not remove too many amber cells. This doesn't work for a=1 or b=1, so you have to take care of that case separately.

Use contradiction. Define a diagonal of the grid to be a set of $a+b+1$ cells such that no two lie in the same column. By contradiction assumption, every diagonal has either at least $a+2$ amber cells or at least $b+2$ bronze cells. We can prove that there must be diagonals of both of these types (otherwise, there would not be enough amber cells or there would not be enough bronze cells). Call the former type A and the latter type B. We define $D_A$ to be the $A$ diagonal with a minimum number of amber cells (among $A$ diagonals; $B$ diagonals, of course, will have smaller numbers of amber cells), and we define $D_B$ similarly. We define $d_A$ to be the number of amber cells in $D_A$, and define $d_B$ similarly. We define $S_A$ to be the set of all cells such that both the cell in $D_A$ that is in the same column and the cell in $D_A$ that is in the same row are amber, and we define $S_B$ similarly. We can prove that all cells of $S_A$ are amber, and all cells in $S_B$ are bronze, meaning that $S_A$ and $S_B$ do not intersect. From here, we prove that $S_A$ and $S_B$ cannot intersect any of the same rows, or else they would necessarily both intersect some cell on that row (because of the amount of cells in the row each set must have; the total amount is more than there are cells in the row, so the cells could not all be distinct). Then, we can also prove that $S_A$ and $S_B$ must intersect the same row, as they have at least $a+b+4$ rows in total, whereas the grid has only $a+b+1$ rows (similarly to how if they intersect the same row, then they share a cell). This is our contradiction.

CircleInvert wrote: Use contradiction. Define a diagonal of the grid to be a set of $a+b+1$ cells such that no two lie in the same column. By contradiction assumption, every diagonal has either at least $a+2$ amber cells or at least $b+2$ bronze cells. We can prove that there must be diagonals of both of these types (otherwise, there would not be enough amber cells or there would not be enough bronze cells). Call the former type A and the latter type B. We define $D_A$ to be the $A$ diagonal with a minimum number of amber cells (among $A$ diagonals; $B$ diagonals, of course, will have smaller numbers of amber cells), and we define $D_B$ similarly. We define $d_A$ to be the number of amber cells in $D_A$, and define $d_B$ similarly. We define $S_A$ to be the set of all cells such that both the cell in $D_A$ that is in the same column and the cell in $D_A$ that is in the same row are amber, and we define $S_B$ similarly. We can prove that all cells of $S_A$ are amber, and all cells in $S_B$ are bronze, meaning that $S_A$ and $S_B$ do not intersect. From here, we prove that $S_A$ and $S_B$ cannot intersect any of the same rows, or else they would necessarily both intersect some cell on that row (because of the amount of cells in the row each set must have; the total amount is more than there are cells in the row, so the cells could not all be distinct). Then, we can also prove that $S_A$ and $S_B$ must intersect the same row, as they have at least $a+b+4$ rows in total, whereas the grid has only $a+b+1$ rows (similarly to how if they intersect the same row, then they share a cell). This is our contradiction. I apologize if I'm missing something, but how would you prove that all cells in $S_A$ are amber?

testguy11111 wrote:

@2above If $c$ is a cell in $S_A$, let $c_1$ and $c_2$ be the cells of $D_A$ in the same column and row respectively. Then $c_1$ and $c_2$ are both amber; suppose $c$ was not; then $c$ is distinct from $c_1$. Let $c'$ be the cell in the same row and column as $c_1$ and $c_2$ respectively. Notice that $c$, $c_1$, $c_2$, and $c'$ are pairwise distinct. Now, let $D'$ be $D_A$ except with $c_1$ and $c_2$ replaced by $c$ and $c'$. $D'$ has either one or two less amber cells than $D_A$, which is a contradiction. Thus, all cells in $S_A$ must indeed be amber.

EDIT: @below That's a very clean solution, my favorite in this thread so far.

Chad solution by a friend (did not this beauty during the test): Pick a mutually nonconflicting ambers and b mutually nonconflicting bronzes (inequalities guarantee this exists). Now for each amber and bronze in the same row, there exists a row and column without any elements of our set in them. So take their intersection: if it is amber, replace the conflicting amber in our set with that amber, and if it is bronze, replace the conflicting bronze in our set with that bronze. The total number of conflicting pairs decreases by at least one after each such correction, so we eventually find an entirely nonconflicting set, gg.

Inconsistent wrote: Chad solution by a friend (did not this beauty during the test): Pick a mutually nonconflicting ambers and b mutually nonconflicting bronzes (inequalities guarantee this exists). Now for each amber and bronze in the same row, there exists a row and column without any elements of our set in them. So take their intersection: if it is amber, replace the conflicting amber in our set with that amber, and if it is bronze, replace the conflicting bronze in our set with that bronze. The total number of conflicting pairs decreases by at least one after each such correction, so we eventually find an entirely nonconflicting set, gg. This is what I did too, but I kinda had some trouble proving the easy part that you could pick the a non-conflicting ambers somehow, do you think that will take too much away?

Beautiful problem, but a bit hard for P1. Here is my solution. The key claim is the following. Claim: One can pick $a$ amber cells so that no two are in the same row/column. Proof: This is essentially the same as the $41$ rooks in $10\times 10$ grid problem. Number the cells $0,1,2,\dots,a+b$ and color the cell $(i,j)$ by $i+j\pmod{a+b+1}$. There are $a+b+1$ colors, but $$a^2+ab-b = (a+b+1)(a-1) + 1,$$so at least $a$ amber cells is assigned to the same colors. These cells work because the way we color the grid. $\blacksquare$ Analogously, one can pick $b$ bronze cells so that no two are in the same row/column. Now, we will use discrete continuity. Number the cells $0,1,\dots,a+b$, and for any permutation $\pi$ of $\{0,1,\dots,a+b\}$, define $S(\pi)$ as the number of amber cells in the cells $(0,\pi(0)), (1,\pi(1)),\dots,(a+b,\pi(a+b))$. By the lemma, one can find $\pi_1$ such that $S(\pi_1) \geq a$ and $\pi_2$ such that $S(\pi_2) \leq (a+b+1)-b = a+1$. Moreover, if we start with $\pi_1$ and repeatedly perform transposition (i.e., swap $\pi(x)$ with $\pi(y)$) until we reach $\pi_2$, then each transposition changes the value of $S$ by at most $2$. Thus, at one point, $S(\pi)\in\{a,a+1\}$, implying the conclusion by removing one amber/bronze cells.

Change amber and bronze to red and blue. Define a $k$ rook set to be a set of $k$ cells no two of which are in the same row or column. The problem asks to find a $b+r$ rook set with $b$ blue cells and $r$ red cells. Note that $b^2 + br - r = (b+r+1)(b-1) + 1$ so by EV, we can find a blue rook set with $b$ elements, and the same for a red rook set with $r$ elements. Induct on $b+r$ on the hypothesis that given an red $r$ rook set and a $b$ blue rook set in a $b+r+1$ board, we can find a $b+r$ rook set with $b$ blue and $r$ red. The case when one of them is $0$ is direct. Now, say $R$ and $B$ are the red and blue rook sets with $r$ and $b$ elements respectively. Since there are $b+r+1$ rows/columns, there exist a row and column which are not part of $R$ or $B$, WLOG their intersection is blue. Consider this cell, delete this row and column, and delete an arbitrary blue cell from $B$, and induct, done. $\blacksquare$

I think the following is equivalent to the "local" solutions to this problem posted above. Define a $\emph{left diagonal}$ as the set of cells with $\text{row}-\text{column}=\text{constant},$ and define a $\emph{right diagonal}$ as the set of cells with $\text{row}+\text{column}=\text{constant},$ where all row/column numbers are taken mod $a+b+1.$ Note that $(a-1)(a+b+1)=a^2+ab-b-1.$ Therefore, since there are $a+b+1$ disjoint left diagonals, there is some left diagonal with at least $a$ amber cells. However, if this diagonal contains $a$ or $a+1$ amber cells, then we are already done: just choose the $a$ amber and $b$ bronze cells in the diagonal. Thus, we may assume this left diagonal contains at least $a+2$ amber cells. Similarly, we can find a right diagonal containing at least $b+2$ bronze cells, or at most $a-1$ amber cells. Assume WLOG that the chosen left diagonal goes from top left to bottom right, and the chosen right diagonal goes from bottom left to top right. Let $x_1,\dots,x_k$ denote the number of ambers among pairs of opposite cells in the left diagonal, and let $y_1,\dots,y_k$ denote the number of ambers among pairs of opposite cells in the right diagonal. Now consider the sequence $$x_1+x_2+x_3+\dots+x_k,$$$$y_1+x_2+x_3+\dots+x_k,$$$$y_1+y_2+x_3+\dots+x_k,$$$$\vdots$$$$y_1+y_2+y_3+\dots+y_k.$$The sequence starts at at least $a+2,$ ends at at most $a-1,$ and proceeds in increments of $-2,-1,0,1,$ or $2.$ This is enought to imply that it hits $a$ or $a+1$ at some point, say $(x_1+\dots+x_i)+(y_{i+1}+\dots+y_k).$ But it is easy to see that this sum corresponds to a set of $a+b+2$ cells, no two of which share a row or column. So we can take $a$ ambers and $b$ bronzes from this set, as desired.

what is local or global about these solutions? local means close and global means around the world are the only definitions i know - can someone define these

I did diagonal as well, diagonals are mod $a+b+1$. Note that if we have one diagonal with $a$ or $a+1$ amber cells, we are done. Assume the opposite. Now by some inequality we can see that $(a-1)(a+b+1)<amber\leq (a+b+1)(a+b+1)-b^2-ab+a<(a+b+1)(a+b+1)-b^2-ab+a+1=(a+2)(a+b+1)$ Therefore it is impossible for all $a+b+1$ diagonals to have less than $a$ amber cells, and for it to be all more than $a+1$ amber cells. So there exist 2 consecutive diagonals, one with less than $a$ amber cells, one with more than $a+1$ amber cells Let the the right diagonal be $U_1, U_2,...U_{a+b+1}$, and the left diagonal be $D_1,D_2,...,D_{a+b+1}$. $U_k,D_k$ gives 1 if the cell on that diagonal and on the $k_{th}$ column is amber, 0 otherwise. WLOG suppose that $U_1+U_2+...+U_{a+b+1}\leq a-1$ and $D_1+D_2+...+D_{a+b+1}\geq a+2$ Consider the following process: $$U_1+U_2+...+U_{a+b+1}$$$$D_1+U_2+...+U_{a+b+1}$$$$D_1+D_2+...+U_{a+b+1}$$$$\vdots$$$$D_1+D_2+...+D_{a+b+1}$$each step we swap 2 number $U_k$ and $D_k$, and this can +1,-1,or do nothing to the previous sum. Since the sum transforms from $\leq a-1$ to $\geq a+2$, there exist 2 inbetween steps such that: $$D_1+D_2+...+D_{k-1}+U_k+U_{k+1}+...+U_{a+b+1}=a$$$$D_1+D_2+...+D_{k-1}+D_k+U_{k+1}+...+U_{a+b+1}=a+1$$Since the sum changes from $a$ to $a+1$, $U_k$ must be 0. Since the diagonals are consecutive, we can show that $D_1+D_2+...+D_{k-1}+U_{k+1}+...+U_{a+b+1}=a$ works (just show that there are no 2 cell on the same row), then woohoo and you color your box black $\blacksquare$ This is strikingly similar to the solution above, which is nice (Edit: Would this garantee 2 distinct solution? I think I can say there are 2 pairs of such consecutive diagonal, or there are one or more diagonals with exactly $a$ or $a+1$ cells, and in both cases there are 2 distinct solutions. I wonder given the conditions stated in the problem, what is the minimum number of solutions.) (Edit 2: This probably garantee a lot of solutions, we can have diagonals with increment $p$ coprime to $a+b+1$ and it would still work. Working on finding the minimum number of solutions) (Edit 3: doesn't have to be diagonals, any sequence works. Fixing a top cell at one corner, there are $(a+b)!$ arrangements. This gives a lot of solutions, but double counts a lot.) (Edit 4: some very very vague idea that shows $minsol\geq \frac{2(a+b)!\times min(a+1,b+1)}{a+b+1}$)

pad wrote: Define permutations $\pi \in [a+b+1]$ on the grid in an obvious way. We want a permutation which has either $a$ A's and $b+1$ B's or $a+1$ A's and $b$ B's. Define the score of a permutation $s_A(\pi)$ to be the number of A's in it. We want $s_A(\pi) \in \{a,a+1\}$ for some $\pi$. Claim: There exists $\pi_1$ with $s_A(\pi_1) \le a-1$, and there exists $\pi_2$ with $s_A(\pi_2) \ge a+2$. Proof: This is due to global reasons. Call $\mathcal{A}$ and $\mathcal{B}$ the set of A's and B's on the grid, respectively. Note that over all $\pi\in [a+b+1]$ randomly chosen, \[ \mathbb{E}[s_A(\pi)] = \mathbb{E}\left[\sum_{i=1}^{a+b+1} \mathbf{1}_{(i,\pi(i))=``A"} \right] = \sum_{i=1}^{a+b+1} \text{Pr}[(i,\pi(i))=``A"] = \frac{|\mathcal{A}|}{(a+b+1)^2} \ge a-1+\frac{1}{a+b+1}\]since $|\mathcal{A}| \ge a^2+ab-b$. Therefore there must exist at least one $\pi_1$ for which $s_A(\pi_1) \le a-1$. A similar argument for $B$ gives $\mathbb{E}[s_B(\pi)] \ge b-1+\tfrac{1}{a+b+1}$, but since $s_A(\pi)+s_B(\pi)=a+b+1$, we get $\mathbb{E}[s_A(\pi)] \le a+2-\tfrac{1}{a+b+1}$, so there exists some $\pi_2$ with $s_A(\pi_2)\ge a+2$. $\blacksquare$ Now the main idea is to notice that for any transposition $(x,y)$, \[ |s_A(\pi) - s_A(\pi \circ (x,y))| \le 2, \]which is a very obvious bound. Hence, by performing transpositions to get $\pi_1\to \pi_2$, we must hit either a score of $a$ or $a+1$ at some step.

oops what this is a genius solution

Good problem to do out of contest, bad problem to do in contest. Randomly take $a+b+1$ cells that are in different rows and columns. It follows from the conditions that \begin{align*} \mathbb{E}[\text{Amber cells}] &\ge a \\ \mathbb{E}[\text{Bronze cells}] &\ge b \end{align*} Take two such selections $\pi_1$ and $\pi_2$, one with at least $a$ amber cells, and one with at least $b$ bronze cells. Starting from the leftmost column, if $\pi_1$ takes a different cell than $\pi_2$, then change the cell to the cell of $\pi_2$, altering another column on the right to satisfy the different row condition. This process never repeats, and the number of amber cells changes by at most $2$ with each step. It follows that there must exist a step where the selection has either $a$ or $a+1$ amber cells, and this suffices. $\fbox{}$

Well, basic induction totally works but I don't see many people talking about it.

Assume towards a contradiction there is no way to choose $a$ amber and $b$ bronze cells that satisfy the given condition. Consider a set $S$ of $a+b+1$ cells where no two are in the same row or column. It cannot have exactly $a+1$ amber and exactly $b$ bronze cells or exactly $a$ amber and exactly $b+1$ bronze cells. So, it either has at least $a+2$ amber cells or at least $b+2$ bronze cells. Assume WLOG there are at least $a+2$ amber cells. Then, let $A$ be a set of $a+b+1$ cells where no two are in the same row or column that has at least $a$ amber cells such that the number of amber cells in $A$ is minimized. $A$ must exist because $S$ exists. Let $A$ have $k$ amber cells. Then, $A$ must have at least $a+2$ amber cells. So, $k\geq a+2$ Let $(x_1, y_1)$ and $(x_2, y_2)$ be two amber cells in $A$. If $(x_1, y_2)$ and $(x_2, y_1)$ aren't both amber, then we can replace $(x_1, y_1)$ and $(x_2, y_2)$ with $(x_1, y_2)$ and $(x_2, y_1)$ to get a new set $A'$. The number of amber cells in $A'$ is less than the number of amber cells in $A$. Also, since two cells of $A$ are replaced to get $A'$, the difference between the number of amber cells of $A$ and the number of amber cells of $A'$ is at most $2$. So, $A'$ has at least $a$ amber cells. This is a contradiction, since then $A$ doesn't have the minimal number of amber cells. So, for all amber cells $(x_1, y_1), (x_2, y_2)\in A$, $(x_1, y_2)$ and $(x_2, y_1)$ are amber. So, any cell (including cells in $A$) that shares both coordinates with amber cells in $A$ must also be amber. There are $k^2$ such cells, since there are $k$ x coordinates of amber cells in $A$ and $k$ y coordinates of amber cells in $A$. Let amber $(x_1, y_1)$ and bronze $(x_2, y_2)$ be in $A$. Then, if $(x_1, y_2)$ and $(x_2, y_1)$ are both bronze, then we can replace $(x_1, y_1)$ and $(x_2, y_2)$ with $(x_1, y_2)$ and $(x_2, y_1)$ to get a new set $A'$. $A'$ has one less amber cell than $A$, so it still has at least $a$ amber cells. So, $A$ doesn't have the minimal amount of amber cells. So, at least one of $(x_1, y_2)$ and $(x_2, y_1)$ is amber. There are $k(a+b+1-k)$ ways to choose an amber cell and a bronze cell, so there are at least $k(a+b+1-k)$ amber cells with either the $x$ coordinate of an amber cell in $A$ and a $y$ coordinate of a bronze cell in $A$ or vice versa. Adding $k^2$ to $k(a+b+1-k)$, we find that there are at least $k(a+b+1)\geq (a+2)(a+b+1)=a^2+ab+3a+2b+2$ amber cells. Also, there are at least $b^2+ab-a$ bronze cells. So, there are at least $a^2+b^2+2ab+2a+2b+2$ cells. However, there are only $a^2+b^2+2ab+a+b+1$ cells, a contradiction.

Global? Let $n=a+b+1$. Consider two permutations on $1, 2, \dots n$. Call them $x,y$ and fix $x$ to be $1, 2 \dots n$. The problem bijects to finding some permutation $y$ such that if we look at the pairs $(x_i,y_i)$, $a+1$ are amber and $b$ bronze or $b+1$ bronze and $a$ amber. WLOG $a \geq b$. Let $f(y)$ denote the number of bronze cells in the respective permutation. Claim: There exists $y$ such that $f(y) \geq b$. Proof: We use expected value here. Consider all permutations of $y$. On average, they have \[(a+b+1) \frac{b^2+ba-a}{(a+b+1)^2} = \frac{(b-1)(a+b+1)+1}{a+b+1} > b-1\]bronze cells. Thus, there exists a permutation with at least $b$ bronze cells. Finally, note that we can get from fixing $y=(1,2 \dots n)$ to a permutation that satisfies $f(y) \geq b$ by swapping two elements in the permutation over and over until we hit $y$ (to see this, we can employ something like bubble sort). Now if $f(y) \leq b+1$, we are done, so assume that the only $y$ that satisfy the claim above also satisfy $f(y) >b+1$. Then, note that each swap can increase $f(y)$ by at least two, so at some point, the number of bronze cells must be $b$ or $b+1$, so we are done.

先利用行数与列数之和模 $a+b+1$ 的余数将方格表分成 $a+b+1$ 组, 如下图. 则每组内部的方格不同行且不同列. 由抽屉原理, 必有一组有至少 $\left\lceil\frac{a^2+ab-b}{a+b-1}\right\rceil\geq a$ 个 amber cell, 也必有一组有至少 $\left\lceil\frac{b^2+ab-a}{a+b-1}\right\rceil\geq b$ 个 bronze cell. 如下图不断调整, 运用介值定理即可.

Color the grid such that for each $0\le i\le a+b$, all cells $(j,k)$ with $j-k\equiv i\pmod{a+b+1}$ are assigned color $i$. Then PHP implies the existence of a set of $a$ amber cells of the same color, which will be in pairwise distinct rows and columns. Similarly, we can find a set of $b$ bronze cells in pairwise distinct rows and columns. Denote these $a+b$ cells as $\emph{good}$. Now, consider the following algorithm: Pick an amber good cell and a bronze good cell in the same row or column. Then pick a row with no good cells and a column with no good cells and look at their intersection. If it is amber, replace the amber good cell with this cell, and similarly if it is bronze. This algorithm decreases the number of such pairs of an amber good cell and a bronze good cell in the same row or column, and hence eventually terminates on our desired set of $a+b$ cells.

Very beautiful question. Nice for a P1

This is more local than global. We say that the score of a permutation of $[a+b+1]$ is the number of $A$s. We will show using an ``algorithm" that we can construct a permutation with score $a$ or $a+1$. First, we need some permutations whose score we know of, preferably close to $a$. We can use PHP for this purpose; this gives the existence of a permutation $\pi_1$ with score at most $(a^2+ab-b)/(a+b+1)$, or rather a score of at most $a-1$, and similarly there exists a permutation $\pi_2$ with a score of at least $(a+b+1)-(b-1)=a+2$. Now $a-1$ and $a+2$ are extremely close to $a$ and $a+1$, so while we are not quite finished, we need to find a way to perturb the permutation so that it has a score of $a$ or $a+1$. The easiest way to transform one permutation into another by a series of small changes is by swapping two elements of the permutation. Note that this changes the score by at least $-2$ and at most $2$ at a time. We consider a series of swaps taking $\pi_1$ to $\pi_2$. Since the total delta in the score is $3$, we will eventually hit a score of $a$ or $a+1$, as desired.

Consider the bipartite graph $G\cong K_{a+b+1,a+b+1}$ with vertices in one part being the rows of the grid and the vertices in the other part being the columns of the grid. Let $V:=V(G)$. Define $A\subseteq G$ to be the spanning subgraph having $rc$ as an edge if and only if cell $(r,c)$ of the grid is amber. Define $B\subseteq G$ analogously. Note that $||A||\geq a^2+ab-b$ and $||B||\geq b^2+ab-a$, and $E(A)\sqcup E(B)=E(G)$. It suffices to prove that there exists a $1$-factor $M$ of $G$ with $|E(M)\cap E(A)|\geq a$ and $|E(M)\cap E(B)|\geq b$. Since $d_A(v)\leq a+b+1$ for all $v\in V$, a minimum vertex cover of $E(A)$ has cardinality at least \[ \frac{a^2+ab-b}{a+b+1}>a-1. \]By König's theorem, $A$ has a matching of cardinality at least $a$. This matching can be extended to a $1$-factor of $G$. Thus there exists a $1$-factor of $G$ containing at least $a$ edges from $A$. Let $M$ be a $1$-factor of $G$ with $|E(M)\cap E(A)|\geq a$, and $x:=|E(M)\cap E(B)|$ maximal. Let $m:V\rightarrow V$ be the map sending a vertex to its neighbor in $M$. Assume for the sake of contradiction $x\leq b-1$. Note that $|E(M)\cap E(A)|\geq a+2$. Let $X$ be the set of endpoints of the edges in $E(M)\cap E(B)$. Clearly there must be no edge $vu$ in $B[V\setminus X]$, as otherwise \[ M':=M-vm(v)-um(u)+vu+m(v)m(u) \]contradicts the maximality of $x$ (at most $2$ edges in $A$ are removed from $M$). Since $|E(B[X])|\leq x^2$, we have $|E_B(X,V\setminus X)|\geq b^2+ab-a-x^2$. Since $(a+b)(b-x)>a+x$, it follows that \[ \frac{b^2+ab-a-x^2}{x}>a+b+1-x \]so there exists an edge $b_1b_2\in E(M)\cap E(B)$ with both $N_B(b_1)\setminus X$ and $N_B(b_2)\setminus X$ nonempty (by pigeonhole applied two times). Find $a_1\in N_B(b_1)\setminus X$ and $a_2\in N_B(b_2)\setminus X$. Then \[ M':=M-a_1m(a_1)-a_2m(a_2)-b_1b_2+a_1b_1+a_2b_2+m(a_1)m(a_2) \](or $M':=M-a_1a_2-b_1b_2+a_1b_1+a_2b_2$ if $a_2=m(a_1)$) contradicts the minimality of $x$. Thus we must have $x\geq b$. $\square$

Define a set $S$ of cells in the $(a + b + 1) \times (a + b + 1)$ grid to be "non-conflicting" if it satisfies the following properties: 1. Each column has exactly 1 cell in $S$ 2. Each row has exactly 1 cell in $S$ These conditions imply that $|S| = a+b+1$. Claim: there exists a non-conflicting set $A$ with at least $a$ amber cells, and a non-conflicting set $B$ with at least $b$ bronze cells. Proof: Label each cell with a coordinate so that the bottom left square is $(0, 0)$ and the top right square is $(a+b, a+b)$. Consider the set $T = \{ (x, y) \mid x + y \equiv k \pmod{a+b+1} \}$ for some constant $k$. Clearly this set is non-conflicting. If we consider the sets generated by letting $k = 0, 1, \dots, a+b$, we can see that the non-conflicting sets that we generate are pairwise disjoint. Since we have $a+b+1$ pairwise disjoint non-conflicting sets, by pigeonhole principle we know there must exist a non-conflicting set with \[ \left \lceil \frac{a^2+ab-b}{a+b+1} \right \rceil = a \]amber cells. Similarly, there must exist a non-conflicting set containing \[ \left \lceil \frac{b^2+ab-a}{a+b+1} \right \rceil. = b \]bronze cells. $\blacksquare$ Let the non-conflicting set containing at least $a$ amber cells be $S_A$, and the non-conflicting set containing at least $b$ bronze cells be $S_B$. Notice that if $S_A$ has $a$ or $a+1$ amber cells, then we are done ($S_A$ satisfies the problem), so say $S_A$ has at least $a+2$ amber cells. Similarly, $S_B$ must have $b+2$ bronze cells (or else we are done). Now, let us define an operation "swap" on any given non-conflicting set $S$. Let a "swap" be taking two cells in $S$, say located at $(a, b)$ and $(c, d)$ (with $a \neq c$, $b \neq d$), and replace those two cells with the cells at $(a, d)$ and $(c,b)$. Clearly, after a swap, a non-conflicting set is still non-conflicting. Claim: It is possible to get to from any non-conflicting set $X$ to another non-conflicting set $Y$ using only swaps. Proof: Consider the 1st column. Then, we can perform a swap to match the cell in the first column of $X$ to the cell in the first column of $Y$. After this operation, there should no longer be any other cell in $X$ or $Y$ that lies in the same row or same column (by the definition of a non-conflicting set). We will never touch this cell again. We can do the same for the 2nd column, swapping the cell in the 2nd column in $X$ to the cell in the 2nd column of $Y$. Similarly, no other cell in $X$ or $Y$ should lie in the same row or same column. We can repeat this process until $X = Y$. $\blacksquare$ Consider the graph $G$ created such that the nodes represent a possible non-conflicting set, and an edge exists between two nodes $V, W$ is it is possible to get from $V$ to $W$ via one swap. Clearly these edges are bidirectional, so we have an undirected graph. Now, label each node with the number of amber cells it contains. The problem is equivalent to showing that there exists a node with label $a$ or $a+1$. Consider the path generated by swapping from $S_A$ to $S_B$. Then, we start from a node with label $\geq a+2$ to a node with label $\leq a-1$. Since a swap only changes two cells, the label can change by at most 2 after moving once. Since it is impossible to go directly from a node with label $a+2$ to a node with label $a-1$ (change of 3), thus, at some point in the path from $S_A$ to $S_B$, we must encounter a node with exactly $a$ or $a+1$ amber cells, and we are done. $\blacksquare$

This solution is somewhat verbose even though it's not that complex, but better to err on the long side. It is essentially divided into two steps: Finding $a$ amber and $b$ bronze cells that individually satisfy the condition, and Making alterations to this configuration to make sure the cells don't mess with each other. Claim. [Setup] We can pick $a$ amber cells such that no two share a row or column, and similarly we can also pick $b$ bronze cells. Proof. We go hardcore with contradiction. Suppose we currently have $k < a$ amber cells picked in such a way; I claim that we can get $k+1$. Assume for the sake of contradiction that we can't. Then, notice that there exists a $(a+b+1-k) \times (a+b+1-k)$ lattice of squares that share neither a column or a row with our already picked squares that must all be bronze. Furthermore, for any amber square $A$ we've already picked, define the neighborhood of $A$ to be all squares that share a row or column with $A$ but not a row or column with any other square we've picked. In particular, if there exists an amber square in the row-neighborhood of $A$ and one also in the column-neighborhood of $A$, we can pick those squares and de-select $A$. So in particular, one of these two neighborhoods must be filled with bronze squares, more precisely, $a+b+1-k$ of them. Across all $k$ squares, this means that there are at least $$B \geq (a+b+1-k)^2 + k(a+b+1-k) = (a+b+1)(a+b+1-k)$$bronze squares. But then $$(a+b+1)(b+2) \leq (a+b+1)(a+b+1-k) \leq B \leq (a+b+1)(b+2) - 1$$as there are at least $a^2+ab-b$ amber cells, clear contradiction. $\blacksquare$ Now, we will select $a$ amber and $b$ bronze cells that satisfy this condition and tailor them to work. To do this, consider a set $A_1, A_2, \dots, A_a$ amber and $B_1, B_2, \dots, B_b$ bronze cells that satisfies the previous condition. Let $D$ be the number of pairs $(i, j)$ such that $(A_i, B_j)$ share a row or a column. In particular, for each of these pairs $(A_i, B_j)$, consider any square formed by the intersection of a row with no chosen squares and a column with no chosen squares. Depending on whether it is amber or bronze, we may swap it with $A_i$ or $B_j$, strictly decreasing $D$. Thus, eventually, we will arrive at a valid selection.

Call a set of $a+b+1$ cells "diverse" if no two of the cells share a row or column. It is equivalent to show that there exist $a+b+1$ diverse cells where either $a$ or $a+1$ of them are colored amber. The weird bounds we're given guarantee that there exists a diverse set of $a+b+1$ cells, at least $a$ of which are amber; since $\tfrac{a^2 + ab - b}{(a+b+1)^2}$ is slightly greater than $a-1$, if we just choose a random diverse set, by expectation there must exist one with $a$ amber cells or possibly more. Let this diverse set be called $S$. Similarly, there must exist a diverse set of $a+b+1$ cells with $b$ bronze cells or possibly more – this is equivalent to a diverse set with $a+1$ amber cells or possibly less, Let this divere set be called $T$. Starting from $S$, we will repeatedly perform the operation of replacing cells $(a,b)$ and $(c,d)$ with $(a,d)$ and $(b,c)$. It is possible to perform this operation on $S$ repeatedly until we are left with $T$, since we can think of this operation as swapping the columns of two cells in $S$; it is possible to get from any list to a permutation just by making swaps between items. This operation will change the number of amber cells in our set by at most $2$, so if we start out with at least $a$ amber cells and finish with at most $a+1$ amber cells, there must be some point at which we have either exactly $a$ amber cells or exactly $a+1$ amber cells in our set. This is the set we desired, so we're done.

Solved with guidance from Michael Ren. Call a set of $a+b+1$ cells a permutation if no two lie in the same row or column. Each of the $\ge a^2+ab-b$ amber cells is part of $(a+b)!$ of the $(a+b+1)!$ permutations, meaning the average number of amber cells per permutation is $\ge\tfrac{(a^2+ab-b)(a+b)!}{(a+b+1)!}=a-1+\tfrac{1}{a+b+1}$. In other words, there exists a permutation $\pi_A$ with $\ge a$ amber cells; and analogous computations show that there exists a permutation $\pi_B$ with $\ge b$ bronze cells, i.e., $\le a+1$ amber cells. Finally, since there exists a sequence of ``swappings" (i.e. transpositions) from $\pi_A$ to $\pi_B$, where the number of amber cells goes from $\ge a$ to $\le a+1$ and varies by at most $2$ with each transformation, we are forced to hit a permutation with either $a$ or $a+1$ amber cells along the way (by the Discrete Intermediate Value Theorem). $\square$

Let a sword be a selection of squares such that no two are in the same row or column. Note that $a^2+ab-b=(a-1)(a+b+1)+1, b^2+ab-a=(b-1)(a+b+1)+1.$ Therefore there is always a sword with at least $a$ amber squares and a diagonal with at least $b$ bronze squares. Now, consider the operation on two points in a sword that swaps their $x$ coordinate relative to the square. As all rows and columns still only have one selected square, these $a+b+1$ squares also are a sword. As there is a sword with at least $a$ amber squares and a sword of at most $a+1,$ at some point after using the operation there must be a sword with either $a$ or $a+1$ amber squares, so we're done$.\blacksquare$