Splitting a sandwich and not feeling deceived

This is a problem that has haunted me for more than a decade. Not all the time – but from time to time, and always on windy or rainy days, it suddenly reappears in my mind, stares at me for half an hour to an hour, and then just grins at me, and whispers whole day: “You will never solve me…”

Please save me from this torturer.

Here it is:

Let’s say there are two people and a sandwich. They want to share the sandwich, but they don’t trust each other. However, they found the way how both of them will have a lunch without feeling deceived: One of them will cut the sandwich in two halves, and another will choose which half will be his. Fair, right?

Split sandwich

The problem is:

Is there such mechanism for three people and a sandwich?


EDIT: This was roller-coaster for me. Now, it turns out that there are at least two books devoted exclusively on this problem and its variations:

Fair Division

Cake Cutting Algorithms

Books on fair division


Yesterday, I was in a coffee shop in a small company. We ordered coffee and some chocolate cakes. As I was cutting my cake for my first bite, I felt sweat on my forehead. I thought, ‘What if some of my buddies just interrupt me and say: Stop! You are not cutting the cake in a fair manner!’ My hands started shaking in fear of that. But, no, nothing happened, fortunately.

Answer

For more than two, the moving knife is a nice solution. Somebody takes a knife and moves it slowly across the sandwich. Any player may say “cut”. At that moment, the sandwich is cut and the piece given to the one who said “cut”. As he has said that is an acceptable piece, he believes he has at least $\frac 1n$ of the sandwich. The rest have asserted (by not saying “cut”) that is it at most $\frac 1n$ of the sandwich, so the average available is now at least their share. Recurse.

Attribution
Source : Link , Question Author : VividD , Answer Author : Ross Millikan

Leave a Comment