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\times 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)=\left\{f(i)|i\in S\right\}$. 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

${\sum }_{i\in [\mathrm{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\ge m$ and $m\ge \frac{1+\sqrt{1+16n}}{2}$. If there is no $2$ columns with the same number of $0$’s and $1$’s, then let $f([\mathrm{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}(\left\{a,b\right\})$ and the other pick columns $f^{-1}(\left\{c,d\right\})$. Note if $a+b=c+d$, and we know that $a,b$ and $c,d$ are distinct, and $\left\{a,b\right\}\ne \left\{c,d\right\}$, then $a,b,c,d$ must be all distinct. $a+b$ can take $2n-1$ different values, between $1$ and $2n-1$. There are $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ pairwise sums. This shows there must be at least $2$ pairs that both have the same difference by pigeonhole principle when $\left(\genfrac{}{}{0ex}{}{m}{2}\right)\ge 2n$, which is true when $m\ge \frac{1+\sqrt{5+16n}}{2}$. To translate this,

  • If $n+1=m$, then this is always true when $n\ge 3$.
  • If $n=m$, then this is always true when $n\ge 5$.

• $n\le 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([\mathrm{1..2}])=\left\{0,2\right\}$ 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([\mathrm{1..4}])=\left\{a_1,a_2,a_3,a_4\right\}$ 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$