Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
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
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 tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
 
 
Thread Tools Display Modes
  #1 (permalink)  
Old April 6th, 2010, 08:39 PM
Registered User
 
Join Date: Apr 2010
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Question 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.
  #2 (permalink)  
Old June 20th, 2010, 02:49 PM
Registered User
 
Join Date: Jun 2010
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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
  #3 (permalink)  
Old July 25th, 2010, 08:14 PM
Registered User
 
Join Date: Jul 2010
Posts: 2
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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).
  #4 (permalink)  
Old July 26th, 2010, 04:56 AM
Registered User
 
Join Date: Jul 2010
Posts: 2
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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.
  #5 (permalink)  
Old August 9th, 2011, 01:50 AM
Registered User
 
Join Date: Aug 2011
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default

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


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

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 06:48 PM



All times are GMT -4. The time now is 02:20 AM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.