Cake Cutting (1 Viewer)

[GoldyOrNugget]

Jeremy convinces Marie to play the following game on two identical rectangular cakes. Jeremy will cut the first cake into two pieces, perhaps evenly, perhaps not. After seeing the cut, Marie will decide whether she will choose first or allow Jeremy to do so. If she goes first, she will take the larger piece. If she goes second, she can assume that Jeremy will take the larger piece. Next, Jeremy will cut the second cake into two pieces (remember that one of the pieces can be vanishingly small if he so chooses). If Marie had chosen first for the first cake, then Jeremy gets to take the larger piece of the second cake. If Marie had chosen second for the first cake, then she gets to take the larger piece of the second cake.

Assuming each child will strive to get the most total cake possible, what is an optimal strategy for Jeremy?

 

[Sy123]

Are we assuming Marie is a great logician?

My attempt is:

Case 1:

Jeremy should cut the cake into two equal pieces at first, then the next bit depends on whether Marie chooses first:

- If she chooses first, cut the second cake into 1 infinitely small piece so Jeremy keeps the large full cake. Jeremy gets 1.5 cake by the end.

- If she chooses second, then cut the second cake into 2 equal pieces, both kids get the same amount by the end.

Case 2:

Jeremy should cut the cake into 2 uneven pieces. The ratio between large piece to small piece we will denote as k

- If Marie chooses first, she gets the larger piece, then Jeremy should cut the next cake into a ratio of m, such that m > k
- If Marie chooses second, she gets the smaller piece, then Jeremy should cut the next cake into a ratio of m, such that m < k

Case 3:

Jeremy cuts the cake such that there is only infinitely small piece (using their supernatural abilities).

- If Marie chooses first, then Jeremy must cut the second piece into infinitely small as well, in the end, Jeremy gets 1 cake and so does Marie.
- If Marie chooses second, then Jeremy can cut the second piece into infinitely small as well, in the end, Jeremy gets 1 cake and so does Marie.


===========

Hence, Case 2 is the best option, because assuming that Marie is a great logician, she won't fall for the disadvantage in Case 1.

 

[RealiseNothing]

Your 2nd point in case 3 isn't optimum, but it does not change anything anyway

 

[RealiseNothing]

Also i think i might have the exact ratio he should cut it in, will post when i get home with an explanation.

 

[Sy123]

Your 2nd point in case 3 isn't optimum, but it does not change anything anyway

Ah yes, well then it would be the same effect as Case 1 part 1 but in reverse.
If Jeremy cuts it into an infinitely small piece, Marie is forced to choose first.

I will see if I can figure out an exact optimum ratio.

 

[Demento1]

Hmm, this question seems awfully familiar. I reckon I can post an answer by the night if no one's got it and if I'm free.

 

[GoldyOrNugget]

Yeah I'm expecting an exact ratio. This question's probably been floating around in various forms for a while, but I got it from one of the final exams for the algorithms course at UNSW.

 

[oh well]

Yeah I'm expecting an exact ratio. This question's probably been floating around in various forms for a while, but I got it from one of the final exams for the algorithms course at UNSW.

you wanna do adv maths at UNSW?

 

[GoldyOrNugget]

I wanted to combine adv. maths and computer science at UNSW, but they don't offer that. I'll settle for B.Sc (CompSci) / B.Sc (Mathematics), but I'll try to mess around with the degree program so that I end up doing roughly the same coursework as the adv. maths students.

 

[RealiseNothing]

Ok so basically the logic I had was that we had to find what ratio to cut the cake into such that Marie's decision on whether or not she goes 1st or 2nd is irrelevant, that is, Jeremy has complete control.

This occurs when Marie will receive the same amount of cake no matter if she chooses to go 1st or 2nd, and hence her decision is meaningless.

Now Jeremy must cut the cake into unequal pieces, but how unequal? Let's consider Marie's decisions:

Suppose Jeremy cuts the first cake into a ratio j:1 where j>1. If Marie chooses to go first, she takes the larger piece. However, now Jeremy will optimally cut the second cake infinitely small and take basically the whole cake. So by choosing first Marie will only receive her portion of the first cake, which we shall denote as "n" amount of cake.

Suppose now that Marie decides to choose 2nd. Of the first cake, Marie will receive the smaller piece, which is the whole cake minus "n". Let the amount of the whole cake be A. Therefore she receives "A-n" amount of cake from the first cake. Optimally Jeremy will now cut the second cake in half so that on choosing 2nd, he will get half the cake. Hence Marie ends up with:

amount of cake.

Now we want to make it such that:



Now since because we made it the larger piece, we can cancel out a half on both sides to simplify the case. So we let:



Substituting this in gives:



Which gives:







Hence we want to choose "k" such that it is a quarter of the whole cake. Substituting this back into our definition to find "n":







Hence we want to choose "n", which is the larger piece of the first cut, such that it is three quarters of the whole cake.

Therefore Jeremy wants to cut the first cake into a ratio of 3:1.

If Marie chooses to go first, Jeremy will cut the second cake into an infinitely small piece.

If Marie chooses to go second, Jeremy will cut the second cake in half.

Both leaving Jeremy with five quarters of a cake - the most he can possibly have.

 

[Alexis Texas]

kekekeke stealing this for when i'm a teacher y o l o

 

[GoldyOrNugget]

Good job, 3/4 is correct. My method involved taking the maximum of min(A,B) where A and B were two linear functions, and this maximum existed at x=3/4. I lost the rest of the working though

 

[Absolutezero]

I completely guessed and got it right. The best way to do math.

 

[Trebla]

Gotta love game theory...