Sushi sharing problem
The problem was first brought up by Sam McCauley when I was still in Stony Brook.
Two germophobic friends are sharing sushi. There are two kind of sushi, $0$ and $1$. The sushi are lied out on a $n×m$ matrix. There are $a$ sushi of type $0$ and $b$ sushi of type $1$, both are even numbers and $a+b=nm$. One can pick up a sushi with a chopstick by picking it up horizontally, or vertically. It will touch the adjacent sushis horizontally or vertically, respectively.
Each person want to eat exactly $a/2$ sushi of type $0$ and $b/2$ sushi of type $1$, and no one want to eat a sushi touched by someone else. Is this always possible? Yes it is!
First, it’s easy to see each person can pick up a entire row or column, and collapse the remaining matrix. All the remaining sushi in the matrix are clean. We will assume each person pick up a entire row/column.
We prove this by induction. Let $f(i)$ be the number of $1$’s in the $i$th column, and $f(S)={f(i)∣i∈S}$. As long as both friends pick up the same number of each sushi before collapse the matrix, we can go to a smaller case.
Before the case by case analysis, we note of two conditions:
 Even sum condition

$∑_{i∈[1..m]}f(i)=b$, it must be even.
 Even side condition

Because $nm$ is even, either $n$ or $m$ is even.
$n>m$, rotate the matrix.
$n+1<m$, by pigeonhole principle, $f(i)=f(j)$ for some $i$ and $j$. One person pick $i$th column and the other pick the $j$th column.
$n+1≥m$ and $m≥21+1+16n $. If there is no $2$ columns with the same number of $0$’s and $1$’s, then let $f([1..m])=S$ to be a set of $m$ elements. Now, consider we pick 4 distinct elements $a,b,c,d$ from $S$ and if $a+b=c+d$, then we can let one person pick columns $f_{−1}({a,b})$ and the other pick columns $f_{−1}({c,d})$. Note if $a+b=c+d$, and we know that $a,b$ and $c,d$ are distinct, and ${a,b}={c,d}$, then $a,b,c,d$ must be all distinct. $a+b$ can take $2n−1$ different values, between $1$ and $2n−1$. There are $(2m )$ pairwise sums. This shows there must be at least $2$ pairs that both have the same difference by pigeonhole principle when $(2m )≥2n$, which is true when $m≥21+5+16n $. To translate this,
 If $n+1=m$, then this is always true when $n≥3$.
 If $n=m$, then this is always true when $n≥5$.
$n≤2$ and $n+1=m$. Since both $0+1$ and $0+1+2$ is odd, we must have two columns have the same value.
$n=m=2$. If there is no $2$ columns with the same number of $0$’s and $1$’s, then $f([1..2])={0,2}$ in order to satisfy the even condition. But each row would have the same number of different kind of sushi. Let each friend take a row.
$n=m=3$. This is not possible with even side condition.
$n=m=4$. This is the last case. If no $2$ columns have same number of $0$’s and $1$’s, then $f([1..4])={a_{1},a_{2},a_{3},a_{4}}$ where $a_{1}<a_{2}<a_{3}<a_{4}$ and has to equal to one of the following due to the even sum condition. In all cases, $a_{1}+a_{4}=a_{2}+a_{3}$.
 $0,1,2,3$
 $0,1,3,4$
 $1,2,3,4$