p2p.wrox.com Forums (http://p2p.wrox.com/)
-   BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9 (http://p2p.wrox.com/book-puzzles-programmers-pros-book-isbn-978-0-470-12168-9-327/)
-   -   Sweet tooth Warm Up (http://p2p.wrox.com/book-puzzles-programmers-pros-book-isbn-978-0-470-12168-9/78879-sweet-tooth-warm-up.html)

 jsuit April 6th, 2010 08:39 PM

Sweet tooth Warm Up

Here's the problem with a chunk of the solution from pg 4:

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 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 first for the first cake, then Jeremy gets the larger piece of the second cake. If Marie had chosen second for the first cake, then she gets the larger piece of the second cake.

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

Hint: Assume that Jeremy divides the first cake into fractions f and 1-f where f is at least 1/2. Then explore the consequences if Marie chooses to take the piece of fraction f or if she goes second, so gets the piece having fraction 1-f.

Solution:

If M takes the fraction f piece, then Jeremy will take the entire second cake. So, Marie will get exactly f and Jeremy will get (1-f) +1. If Marie takes the smaller piece of the first cake (fraction 1-f), Jeremy will do best if he divides the second cake in half. This gives Marie (1-f) = 1/2. Jeremy follows this reasoning, so realizes that the best he can do is to make f = (1-f) +1/2. That is 2f = 1.5 or f = 3/4.

+++++++++++++++++++++++++
My question:
It says "Jeremy follows this reasoning, so realizes that the bes he can do is to make f = (1-f) + 1/2." I understood everything up till this part. More specifically, what I don't understand is how acknowledging that either Marie gets f and John gets (1-f) +1 OR Marie gets (1-f) +1/2 and John gets f + 1/2 leads John to realize that the best he can do is f = (1-f) + 1/2. Why is f = (1- f) + 1/2 the BEST he can do?

 abhadoriya June 20th, 2010 02:49 PM

why is f=(1- f) + 1/2 the BEST he can do?

There are two strategies for Marie:
1. Max she can get 'f' (i.e. she goes first and Jeremy gives nothing to her in next cut)
2. Max she can get: (1- f) + 1/2

Jeremy can force her to make the obvious choice if she gets the same thing in both the strategies which is
f = (1- f) + 1/2 [:D]

HTH

 Nirvahna July 25th, 2010 08:14 PM

Poorly Explained Solution

The solution for this problem is very poorly explained. You need to apply geometry and a game theory mindset to get this problem.

What you need to do here is draw graphs of the 4 equations you have here. The y-axis would be the total each could possibly have (max is 2) and the x-axis would be the value f could possibly have (max is 1).

M1 = f
J2 = 2-f
M2 = 3/2 - f
J1 = f + 1/2

M1 = Marie if she went first, J2 = Jeremy if he went second
M2 = Marie if she went second, J1 = Jeremy if he went first

Understand the graphs. Marie wants more than Jeremy and Jeremy wants more than Marie. Both want to maximize their respective shares as well. Look at the ranges in the graphs where this makes sense. You'll need to get the intersection points of the 4 lines with each other and understand the semantics of the ranges.

You'll find 3 values for f = 1/4, 3/4 and 1. Plug in these values into the 4 equations. Each f value for the 4 equations constitutes a set. Realize that the only control that Jeremy has here is the the fraction f he cuts the first cake in. And the only control that Marie has here is whether or not to go first.

Looking at each set of values, apply the logic that Jeremy wants to maximize his share so determine which f value he would want to play, and that Marie also wants to maximize her share so determine in which cases she would want to play first and which second.

You will soon see that the only scenario is the f=3/4 case. And in this case, it also so happens that Marie would get 3/4 total share no matter if she goes first or second (and that Jeremy would get 1 1/4).

 Nirvahna July 26th, 2010 04:56 AM

7 cakes follow-up question

Does anyone understand the solution for the 7-cake follow-up question? I can't understand that inductive logic. By manually calculating the shares, I do see that Jeremy has a very slight advantage in the end. Out of 7 cakes, his share should be 3 + 33/64. So that's an advantage of 1/64, which agrees with the author's calculation.

 sreraku August 9th, 2011 01:50 AM

Quote:
 Originally Posted by abhadoriya (Post 259398) There are two strategies for Marie: 1. Max she can get 'f' (i.e. she goes first and Jeremy gives nothing to her in next cut) 2. Max she can get: (1- f) + 1/2 Jeremy can force her to make the obvious choice if she gets the same thing in both the strategies which is f = (1- f) + 1/2 [:D] HTH
I have the same question. Even after looking at above I still dont understand how f is equal to (1-f) + 1/2!!!! Is it that you are trying to equate two strategies? If yes I dont understand how they can be equal?

 All times are GMT -4. The time now is 10:13 PM.