Wrox Programmer Forums Sweet tooth Warm Up
 |
BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9
 This is the forum to discuss the Wrox book Puzzles for Programmers and Pros by Dennis Shasha; ISBN: 9780470121689 Read more about Puzzles for Programmers and Pros or buy the book from your favorite retailer Download the code for Puzzles for Programmers and Pros
 Welcome to the p2p.wrox.com Forums. You are currently viewing the BOOK: Puzzles for Programmers and Pros BOOK ISBN: 978-0-470-12168-9 section of the Wrox Programmer to Programmer discussions. This is a community of software programmers and website developers including Wrox book authors and readers. New member registration was closed in 2019. New posts were shut off and the site was archived into this static format as of October 1, 2020. If you require technical support for a Wrox book please contact http://hub.wiley.com

April 6th, 2010, 08:39 PM
 jsuit Registered User Join Date: Apr 2010 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts
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?

Last edited by jsuit; April 6th, 2010 at 11:01 PM..

June 20th, 2010, 02:49 PM
 abhadoriya Registered User Join Date: Jun 2010 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts
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

HTH

July 25th, 2010, 08:14 PM
 Nirvahna Registered User Join Date: Jul 2010 Posts: 2 Thanks: 0 Thanked 0 Times in 0 Posts
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).

July 26th, 2010, 04:56 AM
 Nirvahna Registered User Join Date: Jul 2010 Posts: 2 Thanks: 0 Thanked 0 Times in 0 Posts
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.

August 9th, 2011, 01:50 AM
 sreraku Registered User Join Date: Aug 2011 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts

Quote:
 Originally Posted by abhadoriya 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 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Too much time in forum ... bitter/sweet brettyboo BOOK: Beginning ASP.NET 2.0 BOOK VB ISBN: 978-0-7645-8850-1; C# ISBN: 978-0-470-04258-8 0 January 10th, 2007 07:48 PM