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, 00 and 11. The sushi are lied out on a n×mn\times m matrix. There are aa sushi of type 00 and bb sushi of type 11, both are even numbers and a+b=nma+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/2a/2 sushi of type 00 and b/2b/2 sushi of type 11, 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)f(i) be the number of 11’s in the iith column, and f(S)={f(i)iS}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

i[1..m]f(i)=b\sum_{i\in [1..m]} f(i)=b, it must be even.

Even side condition

Because nmnm is even, either nn or mm is even.

  • n>mn>m, rotate the matrix.

  • n+1<mn+1<m, by pigeonhole principle, f(i)=f(j)f(i)=f(j) for some ii and jj. One person pick iith column and the other pick the jjth column.

  • n+1mn+1\geq m and m1+1+16n2m\geq \frac{1 + \sqrt{1+16n}}{2}. If there is no 22 columns with the same number of 00’s and 11’s, then let f([1..m])=Sf([1..m])=S to be a set of mm elements. Now, consider we pick 4 distinct elements a,b,c,da,b,c,d from SS and if a+b=c+da+b=c+d, then we can let one person pick columns f1({a,b})f^{-1}(\set{a,b}) and the other pick columns f1({c,d})f^{-1}(\set{c,d}). Note if a+b=c+da+b=c+d, and we know that a,ba,b and c,dc,d are distinct, and {a,b}{c,d}\set{a,b}\neq \set{c,d}, then a,b,c,da,b,c,d must be all distinct. a+ba+b can take 2n12n-1 different values, between 11 and 2n12n-1. There are (m2){m \choose 2} pairwise sums. This shows there must be at least 22 pairs that both have the same difference by pigeonhole principle when (m2)2n{m\choose 2}\geq 2n, which is true when m1+5+16n2m\geq \frac{1 + \sqrt{5+16n}}{2}. To translate this,

    • If n+1=mn+1=m, then this is always true when n3n\geq 3.
    • If n=mn=m, then this is always true when n5n\geq 5.
  • n2n\leq 2 and n+1=mn+1=m. Since both 0+10+1 and 0+1+20+1+2 is odd, we must have two columns have the same value.

  • n=m=2n=m=2. If there is no 22 columns with the same number of 00’s and 11’s, then f([1..2])={0,2}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=3n=m=3. This is not possible with even side condition.

  • n=m=4n=m=4. This is the last case. If no 22 columns have same number of 00’s and 11’s, then f([1..4])={a1,a2,a3,a4}f([1..4])=\set{a_1,a_2,a_3,a_4} where a1<a2<a3<a4a_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, a1+a4=a2+a3a_1+a_4=a_2+a_3.

    • 0,1,2,30,1,2,3
    • 0,1,3,40,1,3,4
    • 1,2,3,41,2,3,4
Posted by Chao Xu on .
Tags: puzzle.