|
|
I picked up a book of puzzles written for programmers recently, and I've just started going through them. I figured I'd post each one as I get to it, and see who all can solve them. They don't necessarily require programming to solve them, but they can use programming if you'd like. First: A baker bakes two cakes to give to his two children, Jack and Jane. The two children decide to play a game to determine who gets how much cake. The game goes that Jack will cut each cake into two not necessarily equal pieces. After cutting the first cake, Jane gets to decide if she wants to choose her piece from that cake first or second. If she chooses first, she will choose the larger piece. Jack then cuts the second cake. If Jane chose first for the first cake, then he gets first choice, otherwise, she gets first choice. Assuming each child wants to maximize the amount of cake that they get, how should Jack cut the cakes in order to receive the most himself? (Hint: Think of the cakes mathematically. Each cake is 1c. A cut produces f and 1-f. f + 1-f = c).
Last Edit: Jun 19, 2009 20:53:24 GMT by Eric
|
|
|
|
|
Should we assume they can't think ahead?  Also, this is worded... poorly. "not necessarily equal pieces." Does that mean number or size? I could cut c1 into 12 pieces of different sizes or 12 pieces of the same size. Anyways, I'm gonna assume "different sizes" for this, otherwise the question is too easy. Jack wants to make one very large piece and 5 or 6 small pieces of cake one. The second part doesn't matter. Jane will logically think to go first, choosing the bigger piece. Now they just alternate. Let's say the results look like this (in parts of cake): Jane = 4/6 + 1/12 + 1/12 = 5/6 Jack = 1/12 + 1/12 = 1/6 Now for the last cake, Jack chooses first. Jack should cut the cake into an infinitely big piece and an infinitely small piece, thus Jack automatically gets a huge piece, putting him at 7/6 and Jane remains at 5/6. Jack wins.
|
|
|
|
|
|
|
Damn it, sorry. I had two pieces, then I put in not necessarily equal, and somehow took out the two. Anyways, each cake is cut into two pieces.
|
|
|
|
|
First cake should be cut in half - and then he should cut the 2nd one - to over half - he chooses the biggest half - done! 
|
|
|
|
|
First cake should be cut in half - and then he should cut the 2nd one - to over half - he chooses the biggest half - done! If he cuts the first in half, she will choose to let him choose first, meaning she gets to choose first on the second one. Sorry, but wrong. I'll give you guys a hint. If she chooses first on the first cake, then he essentially gets the entire second cake. If she chooses second on the first cake, then he'll do his best to cut the second in half. The way he cuts the first should make it so that he gets the same amount in either case.
Last Edit: Jun 20, 2009 15:34:29 GMT by Eric
|
|
|
|
|
Ok. Then it's just a slight mod on what I said. He'll cut the first into 3/4 and 1/4 (just for an example). Here's how the scenarios play out: Jane FirstShe picks 3/4 piece. HE gets 1/4 piece. He then cuts the last cake into 1/1 and 1/inf (so infinitely complete and infinitely small. He then picks the 1/1 piece and has 5/4 of a cake while she has 3/4. Jack FirstHe picks the 3/4 piece. She gets the 1/4 piece. He then cuts the last cake in half and they both pick and he gets 5/4 and she gets 3/4, again.
|
|
|
|
|
|
|
Ok. Then it's just a slight mod on what I said. He'll cut the first into 3/4 and 1/4 (just for an example). Here's how the scenarios play out: Jane FirstShe picks 3/4 piece. HE gets 1/4 piece. He then cuts the last cake into 1/1 and 1/inf (so infinitely complete and infinitely small. He then picks the 1/1 piece and has 5/4 of a cake while she has 3/4. Jack FirstHe picks the 3/4 piece. She gets the 1/4 piece. He then cuts the last cake in half and they both pick and he gets 5/4 and she gets 3/4, again. Correct! So here's the part two: There are now three cakes. Again Jack will cut, Jane will choose. She gets to choose first twice, he gets to choose first once. How should he cut the cakes (each one once) so that he gets the most?
|
|
|
|
|
Question: Does it go jane, jack, jane or is the order variable? (I don't think it effects my answer, but I figured I'd check. )
Last Edit: Jun 20, 2009 21:05:49 GMT by Chris
|
|
|
|
|
|
|
Question: Does it go jane, jack, jane or is the order variable? (I don't think it effects my answer, but I figured I'd check. ) Order is up to Jane (she decides if she is first after seeing the cut).
Last Edit: Jun 20, 2009 21:10:13 GMT by Eric
|
|
|
|
|
Jack cuts the first one as 2/3 and 1/3. Now let's branch the scenarios. - Jane lets Jack pick... Jack takes the 2/3. Rest of the cakes are cut as 1/2 and thus they both get the same amount while he still has 1/3 more overall. - Jane picks first... Jane picks the 2/3 and Jack has 1/3. Now we have another set of scenarios. Jack should cut 11/15 and 4/15. --- If Jane picks first, she now has 21/15 and then Jack has 9/15. Jack can then cut remaining as basically 1/1 and 0/1 and thus he has about 24/15 and she has about 21/15. --- If Jane lets jack pick, he will have 16/15 and she will have 14/15. If jack cuts them perfectly evenly at 1/2, he then wins either way.
|
|
|
|
|
|
|
|
Wrong. Jack can have a guaranteed amount more than the minimum you posted, but it's less than the max you posted.
You got the point that if he chooses first, then the rest become one half. So here's a hint: if she chooses first then the situation is essentially a repeat of the one with two cakes. Either way he should get the same amount of cake.
|
|
|
|
|
He still gets more than his sister... that's all that matters. But I see where you're going. It's a recursion, almost.
|
|
|
|
|
|
|
So, Eric, any more to post?
|
|
|
|
|
|
|
So, Eric, any more to post? Yeah I haven't been doing them myself though, lol.
|
|
|
|
