# 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)=\{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 $$i$$th column and the other pick the $$j$$th 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}(\{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\}\neq \{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])=\{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$$
Posted by Chao Xu on 2014-03-26.
Tags: .