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?

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


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.

For dividing a cake to $n$ people, there is an algorithm that guarantees that:


*

*Each of the $n$ people gets a piece that he considers at least as good as each of the other pieces (i.e., the division is envy free);

*All pieces are connected (actually, all pieces are rectangles).


This algorithm was invented by Forest Simmons and published by Francis Su at 1999.
The only problem with this algorithm is that its runtime is not bounded, i.e., it might take forever (As proved by Stromquist at 2008, no bounded algorithm can find an envy-free division when we want the pieces to be connected).
But, you can stop at any time and get a division that is approximately envy free.
