Divide the grid up in to $mn$ $2 \times 2$ squares. Call these big squares. Each big square contains exactly $1$ counter as there are $mn$ of them and each can contain at most one counter. WLOG the top-left corner of our board is white. Label each big square $A$ or $B$ if the counter is in the top-left/bottom-right square respectively. Any big square labelled $A$ must have the $3$ big squares directly to the left, above and diagonally to the left and above also labeled $A$. Similarly any big square labelled $B$ must have the $3$ big squares directly below, right and diagonally below and to the right labelled $B$. It's also easy to see if this is satisfied then the configuration is valid. From the above we see each of the $m$ rows is labelled: $$\underbrace{AA \cdots A}_{r_i} \underbrace{BB \cdots B}_{n-r_i}$$If we label the rows $1,\cdots m$ where the top row is labelled $1$ then our configuration is valid iff: $$r_1 \geq r_2 \geq \cdots \geq r_m$$So this is equivalent to finding a decreasing function $f: \{1,2, \cdots m\} \rightarrow \{0,1,\cdots, n \}$ which there are many ways to find for example consider $n-f(1), f(1)-f(2), \cdots, f(m-1)-f(m), f(m)$ and then observe a partition of $n$ in to $m+1$ parts uniquely determines the function so using stars and bars there are: $$\boxed{\binom{m+n}{n}}$$valid configurations

The answer is $\boxed{{m + n \choose n}}.$ Split the entire grid into $2 \times 2$ squares. The first key observation to be made is that none of these squares contain more than $1$ counter. In fact, since there are $mn$ counters, there must be exactly $1$ counter per $2 \times 2$ square. First, observe that if a counter is placed in the bottom right cell of a $2 \times 2$ square, then all counters to the right and under the cell are fixed; they must be in the bottom right position. Otherwise, we are free to decide. Now, view the entire grid as an $m \times n$ board, where we color a square blue if it's counter is in the bottom right position, and red otherwise. Observe that the amount of ways to color this grid bijects to a path taken from the bottom left corner to the top right corner, so the answer is ${m + n \choose n}$ as requested.

So first off, we will analyze the case for the table $2 \times 2m$ So let's start off with following: All the counters are in the bottom row, that way we will have all the $m$ counters. We number the counters from $1$ to $m$ So now we devise our first algorithm: First algorithm: Define a non-costly move as the following: A counter is moved diagonally once to the right if possible.We denote this as $\eta(C_n)$, where $C_n$ denotes the $n^{th}$ counter. The algorithm does a $\eta(C_m)$, then it does $\eta(C_{m-1})$,.. etc. By that way we generate always a new way. So obviously the number of ways will be the number of times the algorithm has done $\eta(C_n)$ +1. The $+1$ is there because of the starting permutations. So let's start counting... We will denote this by $X(1,m)$, more generally we denote by $X(n,m)$ the number of ways for a grid of dimensions $2n \times 2m$ For our case for when $n=1$. The algorithm does a $\eta(C_n)$ $m$ times, so the number $X(1,m)$, is $X(1,m)=m+1 = {m+1 \choose 1}$ Which still doesn't give us a clue to the final solution, so we must do another case. Let's do a case for the grid $4 \times 2m$. So now let's start by number the rows from $1$ to $4$.(from bottom to up) We place the counters in the rows numbered with the numbers $1$ and $3$. Now we devise another algorithm. Second algorithm: The algorithm first does the first algorithm for the upper half of the table. After that process finishes, the gird is brought back to the starting grid , then we number the counter from $1$ to $2m$, in the third row we have the counters numbered from $1$ to $m$, then in the first row have them numbered $m+1$ to $2m$. Then it does $\eta(C_{2m})$, which then forces it to also do a $\eta(C_m)$, then it cuts them off the grid, then it does the first algorithm on all the counters in the third row.After that finishes we return all the counters (except the ones with cut off) into their starting position before the cutting. Then it repeats this process for $C_{2m-1}$, and this process terminates at some points. So from the algorithm we get: $$ X(2,m) = 1 + \sum_{k=1}^{m} X(1,k) = 1 + 2 + \dots + m + (m+1) = \frac{(m+1)(m+2)}{2} = {m+2 \choose 2}$$ We can now go on and on, we would still get the result ${m+n \choose n}$. So now to prove this we do an induction combined with a generalized algorithm. General algorithm (the n-th algorithm}: If we have a grid of dimensions $2n \times 2m$, with numbered rows from $1$ to $2n$ (from bottom to up). We place all the counters numbered in the odd numbered rows. This algorithm first does the $n-1$ algorithm on the rows numbered with a odd number from $3$ to $2n-1$ (the $n$ algorithm and the $n-1$ algorithm are in the same relation as are the second and the first algorithm).Then it numbers all the counters from $1$ to $mn$, now we have the counters numbered in the $2n-1$ row from $1$ to $m$, then in the $2n-3$ from $m+1$ to $2m$, etc. Then what it does is the following: It does a $\eta(C_{mn})$, forcing it to do $\eta(C_{km})$, it does this $\forall k \in \mathbb{Z}_{n-1}$, and cuts all the counters $C_{km}$, for all $k \in \mathbb{Z}_n$ and does the $n-1$ algorithm for the row numbered with a odd number from $3$ to $2n-1$ and on the remaining counters. Then it return the remaining counters into their original positions.It repeats that process until all the counter are cut off the grid. So now we get the following: $$ X(n,m) = 1+ \sum_{k=1}^{m} X(n-1,k)$$This is now proven by induction, let's say that we have our formula ${m+n \choose n}$ working for some $n=t$. ( we have already done 2 cases, so our base of induction isn't a problem) We use the result we got from our algorithm so now we get that: $$ X(t+1,m)=1+\sum_{k=1}^{m} X(t,k)$$. Because of induction we get that $X(t,k) = {k+t \choose t}$, plugging in that back we get that: $$X(t+1,m)= 1+ {t+1 \choose t} + {t+2 \choose t} + {t+3 \choose t} + \dots + {t+m \choose t} = {t \choose t} + {t+1 \choose t} + {t+2 \choose t} + {t+3 \choose t} + \dots + {t+m \choose t} = {m+t+1 \choose t+1}$$Which is what we wanted to prove by induction. So the total number of ways is ${m+n \choose n}$.....

Cute. The answer is $\binom{m+n}{m}$. The main idea is to divide the $2m \cdot 2n$ grid into a $m \cdot n$ grid of $2 \cdot 2$ squares. Claim: Each $2 \cdot 2$ square must contain exactly $1$ counter. Proof: Note that each square obviously can't contain more than $1$ counter. But there are $mn$ squares and $mn$ counters, proving the claim. Now suppose the top-left corner of the grid is white. let a square be colored red if the bottom-right corner of the square has a counter, and green otherwise. Note that each red square must also have a red square to its right and bottom. Therefore, each row will appear to be a string of blue squares, followed by a string of red squares. Now, let $f(n)$ be the number of blue squares in the $n$th row. Remark that $f$ is non-increasing as $n$ decreases; by stars and bars, we get our desired answer.

We claim the answer is $\boxed{\binom{m+n}{n}}$. Let an mega square be a square of size $2\times2$. We start by splitting the grid into $mn$ mega squares. Note that each mega square must have exactly counter, as there are $mn$ counters and $mn$ mega squares, but there can't be two counters in a mega square as then that would violate the condition that no two counters are diagonally adjacent. Note that if we place a counter in the bottom right square of a mega square, then all of the counters that are below and to the right of that square are fixed, as they must all be in the bottom right position of the mega square. For all of the other counters, we can put them wherever we want. We can just think of the entire grid as a $m\times n$ board, with each square of this $m\times n$ board being a mega square. If label this grid with numbers 0 and 1 such that if the counter is in the bottom right position we label it with 0, and if the counter is not then we label it 1. But the number of ways to do this is equivalent to the number of ways to find a path from the bottom left corner to the top right corner, so the answer is $\boxed{\binom{m+n}{n}}$, as desired.

Consider labeling each row from up to down as $M_1, M_2, ... M_{2m}$ and each column from left to right as $N_1, N_2, ... N_{2n}.$ Place a counter in all $(M_{2k},N_{2i})$ for $1 \leq k \leq m$ and $1 \leq i \leq n.$ Suppose the top right corner, or $(M_1, N_{2n})$ is white. Notice that all possible configurations are reachable by some shift of counters in the current sequence. In each $2$ by $2$ cell, let the state $a$ be where the white cell $(M_{2k}, N_{2i-1})$ has a counter and $b$ be the state where the white cell $(M_{2k-1}, N_{2i})$ has a counter. Now, consider a $m$ by $n$ matrix full of $a's$ and $b's$ (each entry is the state of each $2$ by $2$ cell). The conditions given implies that in the matrix, we can only have a $b$ if and only if the entry above the $b$ and to the right of the $b$ are both $b's.$ This condition has a bijection between the number of right-down blockwalks with $m$ down and $n$ right, where entries above the path is a $b$ and the entries below is an $a.$ Therefore, the answer for this question is $\binom{m+n}{n}.$

The answer is $\binom{m+n}{m}=\binom{m+n}{n}$. We'll let there be $2m$ rows and $2n$ columns (it doesn't actually matter) in the grid. Denote the cells of the grid as $a_{i,j}$ where $i$ denotes the row and $j$ denotes the column. We'll let $a_{1,1}$ be the upper left cell. WLOG let $a_{1,1}$ be white, so $a_{i,j}$ is odd if any only if $i+j$ is even. Define a bar as a set of cells which consists of all cells of the form $a_{x,2y-1}$ and $a_{x,2y}$ for some $1 \leq x \leq 2m$ and $1 \leq y \leq n$. First we notice that a grid can be partitioned into exactly $n$ bars (one for each value of $y$), and that ignoring everything else a bar can only have at most $m$ counters on it. Since there are $mn$ total bars it follows that in this partition each bar must have exactly $m$ counters on it. In fact, we can see that the last $k$ counters (from top down) are of the form $a_{2x,2y}$ and the rest are of the form $a_{2x-1,2y-1}$, where $0 \leq k \leq m$. For a bar $B$, let $f(B)$ denote this value of $k$. Note that $0 \leq f(B) \leq m$. We partition the grid into bars $B_1,B_2,\ldots,B_n$ starting from left to right. The key claim is that the sequence $(f(B_i))$ must be nondecreasing, and that every such sequence will result in a valid arrangement. We will prove both of these at the same time. If there exists an $k$ such that $f(B_k)>f(B_{k+1})$, we will show that there must exist diagonally adjacent white squares. Indeed, we must have white counters on $a_{2i,2k}$ for $m-f(B_k)<i \leq m$. We must also have white counters white counters on $a_{2j-1,2k+1}$ for $1 \leq j \leq m-f(B_{k-1})$. Since $f(B_k)>f(B_{k+1})$ this means that there exists some $a$ such that there are white counters on $a_{2a,2k}$ and $a_{2a-1,2k+1}$, which are diagonally adjacent: contradiction! Thus $(f(B_i))$ must be nondecreasing. Conversely, if $(f(B_i))$ is nondecreasing, then the same exact argument (just spun backwards) means we don't get adjacent counters. Thus we just have to count the number of nondecreasing sequences $f(B_1),f(B_2),\ldots,f(B_n)$ such that $0 \leq f(B_i) \leq m$ for all $i$. This is equivalent to finding the number of nonnegative, nondecreasing integer sequences $a_1,a_2,\ldots,a_n,m$. We can consider a sequence defined by $d_1=a_1$, $d_i=a_i-a_{i-1}$ for all $2 \leq i \leq n$, and $d_{n+1}=m-a_n$. Since the original sequence is nondecreasing it follows that $d_i$ is nonnegative for all $i$. It's not hard to see that each $a_i$ sequence corresponds to exactly one unique $d_i$ sequence and vice versa. Also realize that $\sum_{i=1}^{n+1} d_i=m$. Thus we can just count the number of $d_i$ sequences, which by stars and bars is just $\binom{m+n}{m}=\binom{m+n}{n}$, as desired. $\blacksquare$ Dang no whitespace

Here's my solution, which I think is different from the others. Let $f(m,n)$ be the required number of ways. First, observe that every $2 \times 2$ square must have exactly one counter since it cant have more than $1$ and there are $mn$ $2 \times 2$ squares and $mn$ counters Take a $(2m+2)\times (2n+2)$ board and consider the top-right $2 \times 2$ square. Suppose that the top left and bottom right of that $2 \times 2$ square is white (If its the other way around, instead look at the top-left $2 \times 2$). If a counter is placed on the top left of this $2 \times 2$, then there is only one way the counters can be placed in the rest of the $2 \times 2$ squares of that row. Then, the remaining $(2m) \times (2n+2)$ board can be tiled in $f(m,n+1)$ ways. Similarly, if the bottom right square of the $2 \times 2$ square is coloured, the remaining board can be coloured in $f(m+1,n)$ ways. So, $f(m+1,n+1) = f(m,n+1) + f(m+1,n)$ Now, just check that the formula $f(m,n) = \binom{m+n}{m}$ works by checking that $f(1,x) = f(x,1) = 1+x$ and then inducting by using the common identity $\binom{m+n+2}{m+1} = \binom{m+n+1}{m} + \binom{m+n+1}{m+1}$

Split the grid into mn 2x2 squares. It's obvious that in each 2x2, there is exactly 1 counter. If a 2x2 has a counter in its bottom right corner (assume that square to be white), then all 2x2s to the bottom and right of it will also have counters in their bottom right corners. Now, if we trace along the border of 2x2s with counters in top left and bottom right corners, we get a path from the top left corner to the bottom right corner. There are (m+n) choose m ways to do so.

The answer is ${m+n \choose m}$. Parition the grid into $mn$ two-by-two squares. Clearly, each two-by-two square must contain exactly one counter. Begin from any 2 by 2 square in one of the four corners, where the corner square is black. By placing a counter in the top-right square, we must then place counters in the top-right square of every mini-grid in the entire row. Similarly, if we place a counter in the bottom-left square, we must then place counters in the bottom-left square of every mini-grid in the entire column. After fixing the row or column, however, we are free to choose any other white square in any other mini-grid to place a counter in. Therefore, at any point, we can either choose to fix an entire row of 2-2 squares, or fix an entire column of 2-2 squares. The grid is complete if and only if we fix all $n$ rows, or fix all $m$ columns. Biject this problem to one involving paths on a grid, where we start at $(0, 0)$, and end when we move to any point with $x$-coordinate $m$ or $y$-coordinate $n$. There are $${n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2}+\cdots+{m+n-1 \choose m-1}+ {m \choose 0}+{m+1 \choose 1} + \cdots + {m+n-1 \choose n-1}$$ways to do this, based on casework relating to the last tile se land on. This simplifies to $${m+n-1 \choose m-1} + {m+n-1 \choose n-1} = {m+n \choose m}$$by two applications of Pascal's identity, as desired.

Since bijections are hard. The answer is $\displaystyle{\binom{m+n}{m} = \binom{m+n}{n}}$. Perform double variable induction on $m,n$. Define a block to be a $2\times 2$ square of the form \[\begin{bmatrix} a&b \\ c&d \end{bmatrix}\]where $a,d$ represents white cell and $b,c$ represents black cell. Let $T(m,n)$ denote the number of placing $mn$ counters for a $2m\times 2n$ grid. Also note that the entire grid can be covered with exactly $mn$ blocks ``in the usual way" so there will be exactly one counter in each block. Base case when $(m,n)=(1,1)$ is easy. If the top right corner block contains a counter in the $d$ cell then all the blocks below this block (in the same column) must have counters placed in the $d$ cell as well, in this case $T(m,n)=T(m,n-1)$. If the counter is placed in the $a$ cell of this block then notice that all the blocks to the right of this block (in the same row) must have counters placed in their $a$ cell as well, in that case $T(m,n)=T(m-1,n)$. Combining both the recurrences we get that $$T(m,n)=T(m-1,n)+T(m,n-1)$$Expanding one of the terms \begin{align*} T(m-1,n)&=T(m-2,n)+T(m-1,n-1)\\ &= T(m-2,n)+\binom{m+n-2}{n-1}\\ &= T(m-3,n)+T(m-2,n-1)+\binom{m+n-2}{n-1}\\ &= T(m-3,n)+\binom{m+n-3}{n-1}+\binom{m+n-2}{n-1}\\ &\vdots \\ &= T(1,n) + \sum_{i=m-1}^{2} \binom{m+n-i}{n-1}\\ &= 1 + n + \sum_{i=m-1}^{2} \binom{m+n-i}{n-1}\\ &= \binom{n-1}{n-1} + \binom{n}{n-1} + \sum_{i=m-1}^{2} \binom{m+n-i}{n-1} \\ &= \binom{m+n-1}{n} \qquad \text{(using Hockey Stick Identity)} \end{align*}Note that $T(1,n)=1+n$ can be easily proven via single variable induction on $n$. Similarly we can get $T(m,n-1)=\displaystyle{\binom{m+n-1}{m}}$ and adding both gives that $$T(m,n)=\binom{m+n}{m}=\binom{m+n}{n}$$which completes the induction.

The answer is $\binom{m+n}{m}$. We first solve the problem for a $2 \times 2n$ board, i.e. when $m = 1$. WLOG, assume the top-left corner of our board is white (throughout this entire solution). Because there's only $2$ rows, we can view the $2n$ white squares on our board as a single line of $2n$ white squares. Hence, we can fix the following, where $C$ represents a white square with a counter and $W$ denotes an unoccupied white square: $$\underbrace{CWCWCW \ldots CWC}_{n\rm\ \text{C's}}.$$Now, we have one extra $W$ left to place. Clearly, there's $$n+1 = \binom{n+1}{1}$$ways to place it, as desired. Furthermore, it's easy to see the $k$ left-most counters must be in the first $k$ squares of the top row, and the last $n-k$ counters must be in the last $n-k$ squares of the bottom row, where $0 \le k \le n$. We denote each of the $n+1$ distinct placements by $(k, n-k)$ for corresponding values of $k$. Now, we claim the maximum number of counters we can place on a $2 \times 2n$ board (in a satisfactory manner) is precisely $n$. FTSOC, assume it's possible to place $n+1$ counters. Then, we'd have $n+1$ $C$'s and $n-1$ $W$'s. But at least $n$ $W$'s are needed to ensure no two of the $n+1$ counters are adjacent, so we have a contradiction. Hence, the maximum amount is precisely $n$, as required. Now, we solve the problem for a general $2m \times 2n$ board. View the board as $m$ copies of a $2 \times 2n$ board. Clearly, each individual board can contain a maximum of $n$ counters. Hence, the total number of counters on our $2m \times 2n$ board is at most $$\underbrace{n + n + \ldots + n}_{m\rm\ \text{times}} = mn.$$But we want $mn$ counters to be on our board, so it follows that each $2 \times 2n$ board must contain exactly $n$ counters for the desired outcome to occur. Now, suppose our top-most $2 \times 2n$ board has placement $(k, n-k)$. Then, because occupied white squares in the third row cannot be adjacent to occupied white squares in the second row, our second $2 \times 2n$ board (from the top) has placement $(j, n-j)$ where $j \le k$. Repeating this process, we find that our $m$ copies of $2 \times 2n$ boards have placements $$(a_1, n-a_1), (a_2, n-a_2), \ldots, (a_m, n-a_m)$$such that $$n \ge a_1 \ge a_2 \ge \ldots \ge a_m \ge 0.$$This is equivalent to the condition $$1 \le a_m + 1 < a_{m-1} + 2 < a_{m-2} + 3 < \ldots < a_1 + m \le n+m.$$Since all pairwise terms of the form $a_i + ([m+1] - i)$ are distinct in the previous inequality chain, we know there's $\binom{m+n}{m}$ ways to pick satisfactory values, as desired. $\blacksquare$

So cute We will claim that the answer is $\binom{m+n}{m}$. It is easy to see that in every $2\times 2$ square grid, there must contain exactly one counter. Now define the base configuration as the one such that it is a composition of [asy][asy] size(3cm); real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } draw((0, 0)--(0, 2)--(2, 2)--(2, 0)--(0, 0)); draw((0, 1)--(2, 1)); draw((1, 0)--(1, 2)); fill(rect(0, 0, 1, 1), black); [/asy][/asy] where the counter is in the bottom left corner. Define a "change" in a $2\times 2$ cell to be when a counter moves from the bottom left to the top right or vice versa. Claim 1. In the base configuration, if we change a $2\times 2$ cell, this will result in all other $2\times 2$ cells that are to the top and to the right of the current cell to change. Proof. Fairly obvious, it will result in a chain reaction. $\blacksquare$ We will proceed with strong induction. The base cases when $n=1, m=1$ and $n=1, m=2$ and $n=2, m=1$ and $n=2, m=2$ are pretty obvious, so I won't go into much detail. Now assume that we want to prove that it works for some $2(m+1)\times 2n$. From our strong induction, we have already proven it for all grids $2a\times 2b$ such that $1\le a\le m$ and $1\le b\le n$. So we just want to add a $2\times 2n$ row from the previous configuration. Now we will do some casework. Consider the newly added $2\times 2n$ row. We split this new row into $2\times 2$ chunks and consider the position of the counter in each of these chunks. Notice that there are $n+1$ cases to consider. Case 1. All the counters are in the bottom left corner. Well then this reduces to the $2m\times 2n$ case because it doesn't affect the grid above it. Thus the answer is $\binom{m+n}{n}$. Case 2. 1 counter is in the top right corner. Notice that this counter has to be the right-most counter since if we changed any other $2\times 2$ cell, then all the cells to the right of its current position would also be changed by Claim 1. Since this counter is the right-most, and every $2\times 2$ cell above it also changed, notice that this reduces to the $2m\times 2(n-1)$ case. Thus the answer is $\binom{m+n-1}{m}$. Case 3. 2 counters are in the top right corner. Notice that like Case 2, these two counters must be the right-most two cells. Then this case reduces ot the $2m\times 2(n-2)$ case. Thus the answer is $\binom{m+n-2}{m}$. And we will continue doing this until we reach the $n+1$'th case where all the counters are in the top right corner. There is only 1 way to place the other counters, so our answer is $1=\binom{m}{m}$. Now summing, we have from the Hockey Stick Identity \[ \binom{m+n}{m}+\binom{m+n-1}{m}+\binom{m+n-2}{m}+\dots+\binom{m}{m}=\binom{m+n+1}{m+1} \]as desired. $\blacksquare$

AIME 1992/12 Divide the grid up into $mn$ 2x2 squares. We assume that the white squares are the top left and bottom right ones. Now we color a 2x2 square blue if the bottom right square has a counter, and red if the top left square has a counter. Claim: Given a blue square, all the squares in the quadrant defined by extending the sides of the square down and to the right are also blue. It is easy to see a blue square forces everything in its row (on its right) and column (below it) to be blue. But then each square in the right part of its row forces each of its columns to be blue, coloring the whole quadrant blue. But take a grid walk from the top right of the $m\cdot n$ grid of 2x2 squares to the bottom left. Everything below the path traced out is colored blue and everything above is colored red. These are in fact all the valid ways to color by the ``forcing rule" that the blue squares follow, so our answer is the number of grid walks in a $m\cdot n$ grid, or $\dbinom{m+n}{n}$.

Define a block to be a $2\times 2$ on a checkerboard. Divide the grid into $mn$ blocks. Note that there must be only $1$ counter placed per block as there are $mn$ blocks and $mn$ counters to be placed. Now, color a block green if the bottom right square has a counter. The key realization is that a green block forces everything to the right of it in its row and below on its column to be green. Thus, the problem is equivalent to the number of grid paths on the checkerboard of blocks, giving $\binom{m+n}{m}$ as the final answer.

Combo is so nice sometimes, but also so hard ;( We claim the answer is $\binom{m+n}{n}$. We split the grid into $mn$ $2\times2$ blocks. Let the top left block be $(0,0)$ and the bottom right block be $(m,n)$. Note that each of these blocks must have $1$ token each. If one of the blocks don't have a token, then there exists a block with $2$ tokens in it, which isn't possible. We say that a block is red if the top left corner has a token, and a block blue if the bottom right corner has a token. Claim 1 If a block $(a,b)$ is red, then the rectangle with vertices $(0,0)$, $(a,0)$, $(0,b)$ and $(a,b)$ must also be red for each block in it. Proof Consider the block directly vertical to $(a,b)$, $(a,b-1)$. The bottom right corner of $(a,b-1)$ cannot have a token because it is diagonally adjacent to the token on $(a,b)$. Thus, $(a,b-1)$ is also red. By symmetry, the same can be said for $(a-1,b)$. Repeat this process until the whole rectangle is red. By symmetry, if a block $(a,b)$ is blue, then the rectangle with vertices $(a,b)$, $(a,m)$, $(m,b)$ and $(m,n)$ must also be blue. Thus, for each coloring, there is also a red section on top left and blue section on the bottom right. Consider the border of the red and blue sections. Each coloring can only have one border because the border determines the whole chessboard. This shows that there is a bijection between the coloring of the grid and gridwalking because the border can only go up and right. The number of paths from $(m,0)$ to $(0,n)$ is simply $\boxed{\binom{m+n}{n}}$, which thus concludes the proof.

First note that since this is a $2m \times 2n$ board, the sides will be even - we will not encounter any issues with the number of white and black squares and the long white diagonal will span the board. The diagonally adjacent restriction motivates us to realize that each square has a range around it. This suggests dividing the board into $mn\;2 \times 2$ squares, since this operation contains all the counters. In fact, this works since there are exactly $mn$ counters and thus each $2 \times 2$ square will contain exactly $1$ counter. Here is where we use the long diagonal property - placing a square at a specific corner fixes all other squares. For an example, we use the standard chessboard configuration - the long white diagonal starts at the bottom left corner and ends at the top right corner. Placing a counter at the top right corner of the bottom left square, an adjacent corner may not be on the bottom left corner of the adjacent top right square, so by the parity argument that each square contains $2$ black and $2$ white squares, it must also be on the top right corner. Then every square in the same row and column as the first square must have an identical configuration. However, this clearly forms a bijection with the number of ways to draw a up and right path from the bottom left square to the top right square, so our answer is $\boxed{\binom{m+n}{n}=\binom{m+n}{m}}$.

Here is a sketch. Divide the board into $(2m)\times(2n)$ grid into $2\times 2$ squares. Now note that a $2\times 2$ square can have at max $1$ counter. So there can be at max. $mn$ counters in the board, and as we are given that the board has exactly this many counters, we get that there is exactly $1$ counter in each $2\times 2$ square. Now the following orientation of the counter forces all the counters above or to its right (might not be immediately to the right or above) to be of the same orientation. [asy][asy] size(3cm); real d = 0.1; path rect(int a, int b, int x, int y) { return (a+d,b+d)--(x-d,b+d)--(x-d,y-d)--(a+d,y-d)--cycle; } draw((0, 0)--(0, 2)--(2, 2)--(2, 0)--(0, 0)); draw((0, 1)--(2, 1)); draw((1, 0)--(1, 2)); fill(rect(0, 1, 1, 2), black); fill(rect(1, 0, 2, 1), black); filldraw(circle((1.5,1.5),0.4),cyan,linewidth(0.5)); [/asy][/asy] Now $P(m,n)$ denote the number of ways to place counters on a $(2m)\times(2n)$ grid. Now we perform a case bash on the orientation of the bottom-most $2\times 2$ squares. We do this by picking the leftmost $2\times 2$ square (of the bottom-most $2\times 2$ squares row) which has the following orientation of the counter on it as mentioned above. From this we get the following recursion.\[P(m,n)=P(m,n-1)+P(m-1,n-1)+\cdots+P(0,n-1).\] Now I claim that $P(m,n)=\binom{m+n}{m}$ which suffices by performing strong induction and we are done.

Divide the board into 2x2 grids. Each grid must have 1 counter, and if you place a counter in the bottom left where white squares are bottom left and top right, it forces all grids below and to the left of it to have them placed in the same respective spot in their grid. This is a bijection with making a path from bottom left to upper right, so there are m+n choose n ways.

We will refer to the four corners of a $2\times 2$ grid by UL, UR, DL, and DR. WLOG, color the bottom left corner of the grid black. Now, we tile the grid with $2\times 2$ grids, and we must have each $2\times 2$ grid containing exactly one counter, because since there exactly $mn$ $2\times 2$ grids and $mn$ counters, if one of those grids doesn't contain a counter, some other one must contain $2$ counters, which we don't want. Now, consider the bottom left $2\times 2$ grid inside our main grid. If a counter is placed on DR, then all the other $2\times 2$ grids along the bottom edge of the main grid must also have their counter placed on DR. Similarly, if the counter is placed on UL, then all the other $2\times 2$ grids along the left edge of the main grid must also have their counter placed on UL. Now, once those are placed, if the counter was placed on DR then the bottom $2\times 2n$ row doesn't matter anymore, and we can continue placing counters on the upper $(2m-2)\times n$ grid because there is no chance that a counter from the bottom row will be adjacent to a counter from the upper $(2m-2)\times 2n$ grid. Then, if we let $f(m,n)$ be the number of ways to place the counters on a $2m\times 2n$ grid, in the case of DR, there are $f(m-1,n)$ ways to tile the grid. Similarly, for the UL case, there are $f(m,n-1)$ ways to tile the grid. Hence, we get the equation $f(m,n)=f(m,n-1)+f(m-1,n)$. Now, it's not hard to inductively show that $f(m,1) = m+1$ and $f(1,n) = n+1$. We will now use strong induction to show that \[f(m,n)=\binom{m+n}{n} \text{ for all positive integers } m,n.\]First, we have already mentioned the base $f(m,1)$ and $f(1,n)$. For the inductive step, assume that $f(x,y)=\binom{x+y}{x}$ for all $x\leq a$, $y\leq b$. Then, using the Hockey Stick Identity, \begin{align*} f(a+1,b) &= f(a,b)+f(a+1,b-1)\\ &= f(a,b) + f(a, b-1) + f(a+1, b-2)\\ &= f(a,b) + f(a,b-1) + f(a, b-2) + f(a+1, b-3)\\ &= f(a, b) + f(a, b-1) + \cdots + f(a, 2) + f(a+1, 1)\\ &= \binom{a+b}{a}+\binom{a+b-1}{a} + \cdots + \binom{a+2}{a} + a+2\\ &= \binom{a+b}{a}+\binom{a+b-1}{a} + \cdots + \binom{a+2}{a} + \binom{a+1}{a} + \binom{a}{a}\\ &= \binom{a+b+1}{a+1} \end{align*}Then, by repeatedly applying Pascal's Identity, we get that $f(a+1,y)=\binom{a+y+1}{a+1}$ for all $y\leq b$, which completes our strong induction, so we're done.

WLOG assume the bottom right cell is white. Partition the grid into $2 \times 2$ squares. There are at most $1$ counter in each of these squares. Denote a square as $\textit{red}$ if the counter is in the bottom and $\textit{blue}$ otherwise. Notice that if a certain square is red, every square to the right or below it must also be red. Thus, we can biject to drawing a path from the bottom left corner to the top right corner of the grid and coloring every square below the path red. This works because of the forcing nature of the red squares. The answer is hence \[\boxed{\binom{m+n}{m}.}\]

Assume our checkerboard has a white square at the top left/bottom right. Divide the checkboard into an $m \times n$ grid of $2 \times 2$ squares. Note that each of these squares should contain exactly 1 counter by Pigeonhole. Notice that the moment we put a counter on the bottom right of a $2 \times 2$ square, we fix each counter on the $2 \times 2$ grids below, to the right, and to the bottom-right of this square. A similar situation occurs when we place a counter of the top left. Thus our grid is separated into two areas - one at the top left with counters on the top left squares, and one at the bottom right with counters on bottom left squares. The boundary between these two squares is a path between the top right and bottom left corners. Thus our total number of colorings forms a bijection with the numbers of such paths with is $\boxed{\binom{m+n}{n}}$.

Lets partition the 2m x 2n grid into 2x2 squares. We can see that we could put at most 1 counter in each of these 2x2 squares. There are mn 2x2 squares and we need to put mn counters $\Rightarrow$ it follows that we have to put exactly 1 counter in each 2x2 square. Lets assume the top left corner of the grid is black. If we put a counter in the top-right square of the 2x2 square, we must then put counters in the top-right square of every 2x2 square in the entire row. If we put a counter in the bottom-left square, we must then put counters in the bottom-left square of every 2x2 square in the entire column. So with each move we fix either a row or a column. After fixing the row or column, we can choose any other white square in any other 2x2 square to put a counter in $\Rightarrow$ at any point, we can choose to fix a whole row of 2x2 squares, or fix an whole column of 2x2 squares. The 2m x 2n grid will be complete only if we fix all n rows, or all m columns. This reduces the problem to a problem where we have to go from a point with coordinates (0,0) to a point with coordinates (m,n) in a rectangular grid, such that (0,0) is the bottom-left corner of the grid and (m,n) is the top-right corner $\Rightarrow$ we have to move m columns in right direction and n rows up in some order $\Rightarrow$ by stars and bars we can do this in ${m+n \choose m}$ ways $\Rightarrow$ the answer is ${m+n \choose m}$.

Partition the grid into an $m \times n$ grid of $2 \times 2$ blocks. Then it follows that each $block$ must contain exactly one counter. WLOG the top right corner of the grid is black. Then color a block red if its counter is placed in its bottom right, and blue if it's in the upper left. If any given block is red then all blocks in its column below it must be colored red as well. If a given block is blue then all blocks in its row to it's left must be blue, similarly. Then from this we get that all possible configurations are uniquely determined by creating a path from the upper right corner to the bottom left corner, since the directions of the path determine the color of each block on the path. Clearly this also determines the rest of the grid, so our answer is $\binom{m+n}{n}$.

Tile the grid with $mn$ $2 \times 2$ squares. Clearly since each square can have at most $1$ counter, and there are $mn$ counters, each square has exactly $1$ counter. Now, let $f(m, n)$ be the answer for $m, n.$ Suppose that $m ,n \geq 2$ and WLOG, assume that the top-left square was black. Clearly if the top-left $2 \times 2$ square had its counter on its upper-right white square, then the $2 \times 2$ square to its right must have its counter at the same position, etc. We can apply the same logic to the other case to get $$f(m, n) = f(m-1,n) + f(m, n-1)$$for $m, n \geq 2.$ Now, we calculate $f(1, k) = f(k, 1)$ for positive integers $k \geq 2.$ Using similar logic as above will yield us $$f(k, 1) = f(k-1, 1)+1$$for $k \geq 2.$ Thus, since $f(1, 1) = 2,$ we have that $f(k, 1)=f(1, k) = k+1.$ Now, observe that $f(m, n)$ is essentially counting the number of paths from one square to the upper-right square in an $m \times n$ grid of squares. Therefore, we have $f(m, n) = \binom{m+n}{n},$ and this can easily be shown to work.

Funnily enough I did the EGMO domino problem before this making it an instasolve. Split the grid into $2 \times 2$ grids. Obviously each grid cannot have two counters, so we need exactly one counter in each grid. Each counter can be in the upper tile or lower tile, label each grid $U$ or $D$ depending on the case. If a $D$ grid exists, the grids right below and to the right of it must also be $D$. Therefore the number of possible arangements is analogous to a path seperating the $U$ or $D$, or equivalently a position in a game of Chomp. Now $\boxed{\binom{m+n}{m} = \binom{m+n}{n}}$ is immediate