Tough Riddle Competition - With prize

[micromass]

The game with the coins is called nim. It has a very deep and interesting theory: https://en.wikipedia.org/wiki/Nim A very neat introduction to this and other games can be found here: http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf

 

[jack action]

I'm late in the game as I don't come in this section often, but I don't feel a good answer has been given for #6:

Dividing a cake fairly between two people is easy: let one person cut the cake in two pieces, let the other choose one of the pieces. How would you divide a cake fairly between three people?

• Person 1 cuts the cake into 3 pieces (each of the 3 pieces should satisfy him/her equally);
• Person 2 chooses 2 pieces (each of the 2 pieces should satisfy him/her equally);
• Case 1: Person 3 chooses 1 piece from person 2;
• Case 2: Person 3 chooses the piece from person 1, then person 1 chooses 1 piece from person 2.

This will ensure that everyone can choose what he/she consider a satisfying piece of the cake between the 3 available pieces, size-wise and/or quality-wise.

The «winning» solutions aren't satisfying, especially if we consider that 2 persons could conspire against the other one:

Let one person cut the cake in three pieces, the other two pick first, and the one who cut gets the remaining piece. The only way for the cutter to maximize his piece to 1/3 of the cake, is to cut it fairly, since any other cut than three 1/3 pieces will always leave him with a smaller piece.

This is not necessarily fair because the third person can only choose between 2 choices (whatever the second person did not choose). So person 1 could decide to make a very large piece and 2 small ones, agree with person 2 to pick the large one and person 3 is stuck with a choice between 2 small pieces such that the others share the large piece and one small piece together.

One cut what he thinks is a 1/3, if the other two are happy, it's his part and the problem is reduced to two people. If one of them is not happy he cuts a piece of the "1/3" of the first person to make it what he, the second person, thinks is a 1/3, if the third person is happy the second takes the piece and the problem is reduced to two people. If the third person is not happy cuts a what he thinks is a third and the problem is reduced to two people.

Although this may work size-wise, it is kind of messy if the second and third persons both cut a piece of the first "1/3". How do we decide who gets to keep the two small pieces to «complete» their share? To fairly do it, I guess one of the remaining person would have to cut each of the 3 remaining pieces in 2 parts and the other one would choose 1 part from each piece. We now have 7 pieces in total. Really messy.

 

[mfb]

especially if we consider that 2 persons could conspire against the other one:

That is still possible in your approach: if 1 makes one piece very good, 3 can pick it, and 2 cannot get it.

 

[jack action]

That is still possible in your approach: if 1 makes one piece very good, 3 can pick it, and 2 cannot get it.

You're right. Then I guess someone will have to eat a multi-piece share!