# The cake-cutting problem, n-player version

Acolyte
Posers and Puzzles 29 Jan '05 19:37
1. Acolyte
29 Jan '05 19:37
At a party, you have the following:
n guests
a table
a cake
a knife
a very small flag tied to a cocktail stick.

You must devise a way of dividing the cake equally among your guests (you're not having any cake). The trouble is, they don't trust you to divide the cake up equally, so if you exercise any discretion in enforcing the rules you set for the guests or try to cut the cake yourself, they'll accuse you of favoritism. The guests can be expected to try to maximise their share of the cake subject to your rules, and to do so in a rational manner. Initally, the cake is on the table, you and the n guests are currently standing in a circle around the cake, and the flag and knife are lying on the table next to the cake.

To make things clearer, we'll impose some restrictions on the players' behaviour. Players make a series of moves, one after another, until everyone has a piece of cake, and you set the rules as to which moves they are allowed to make under what circumstances. The moves are:

- making a radial cut in the cake
- sticking the flag in the cake or taking it out
- picking up the knife/handing it to another player (you can have rules which specify which player)
- taking a single piece of cake (which has already been cut away from the rest of the cake) and leaving the game.

Anyone have any ideas? I think I can come up with a system under these conditions.
2. 29 Jan '05 21:412 edits
this isn't my forte, but i think i have some usefull ideas:

first: name the guests. I dont just mean g1, g2,g3...gn, I mean that at any given time, the guest with the knife is gk, the guest with the flage if gf. you could even do the guest who had the knife last gk1 and these numbers could go back as far as you like. (thus you would probably have guests with more than one kname.) this would be useful in determining who's action comes next.

if you are selective in who you name, then you could use such clauses a &quot;any named guest&quot; or its negative.

you could make a rule giving a named or otherwise specified player the choice or limited choice of who would get the next action.

you could allow guests to make restrictions on the actions of other guests.

are any of these in contradiction with rules or otherwise out of bounds?
3. Acolyte