# 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 ith column, and f(S)=\set{f(i)|i\in 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
\sum_{i\in [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 ith column and the other pick the jth column.

- n+1\geq m and m\geq \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([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}(\set{a,b}) and the other pick columns f^{-1}(\set{c,d}). Note if a+b=c+d, and we know that a,b and c,d are distinct, and \set{a,b}\neq \set{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 {m \choose 2} pairwise sums. This shows there must be at least 2 pairs that both have the same difference by pigeonhole principle when {m\choose 2}\geq 2n, which is true when m\geq \frac{1 + \sqrt{5+16n}}{2}. To translate this,
- If n+1=m, then this is always true when n\geq 3.
- If n=m, then this is always true when n\geq 5.

n\leq 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])=\set{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])=\set{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