The Art Gallery Guardian

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.

Posted by Chao Xu on 2014-03-26.
Tags: .