MedVision ad

Cake Cutting (1 Viewer)

GoldyOrNugget

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
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

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013
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

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Your 2nd point in case 3 isn't optimum, but it does not change anything anyway
 

RealiseNothing

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
Also i think i might have the exact ratio he should cut it in, will post when i get home with an explanation.
 

Sy123

This too shall pass
Joined
Nov 6, 2011
Messages
3,730
Gender
Male
HSC
2013
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

Philosopher.
Joined
Dec 23, 2011
Messages
866
Location
Sydney
Gender
Male
HSC
2014
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

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
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

Banned
Joined
Oct 26, 2012
Messages
171
Gender
Undisclosed
HSC
N/A
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

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
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

what is that?It is Cowpea
Joined
Jul 10, 2011
Messages
4,591
Location
Sydney
Gender
Male
HSC
2013
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.
 
Last edited:

GoldyOrNugget

Señor Member
Joined
Jul 14, 2012
Messages
583
Gender
Male
HSC
2012
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

real human bean
Joined
Nov 17, 2007
Messages
15,077
Gender
Male
HSC
N/A
I completely guessed and got it right. The best way to do math.
 

Trebla

Administrator
Administrator
Joined
Feb 16, 2005
Messages
8,391
Gender
Male
HSC
2006
Gotta love game theory...
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top