Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

You are on your way to visit your Grandma, who lives at the end of the valley. It's her birthday, and you want to give her the cakes you've made.

Between your house and her house, you have to cross 7 bridges, and as it goes in the land of make believe, there is a troll under every bridge! Each troll, quite rightly, insists that you pay a troll toll. Before you can cross their bridge, you have to give them half of the cakes you are carrying, but as they are kind trolls, they each give you back a single cake.

How many cakes do you have to leave home with to make sure that you arrive at Grandma's with exactly 2 cakes?

EDIT : If you go to your grandma's with a half eaten cake, she's gonna be pissed. The trolls can't give you half a cake back. It is unhygienic and disgusting.

share|improve this question
1  
Can you pay toll with less than whole cakes? For example, if you leave the house with one cake will you pay half a cake toll to the first troll? –  Nit Jun 8 at 23:34
    
@Nit and will he then give you one cake back, so you end up with 1.5 cakes? –  WChargin Jun 9 at 0:56
2  
@Nit Then you could go back home, put half a cake in the fridge, and repeat. Infinite cakes! Trolling the trolls? –  WChargin Jun 9 at 15:46
3  
@Nit: not that I think the question really needs the hair-splitting, but it says that the transaction occurs before you can cross the bridge, not before you do cross it. So I don't think it's entirely clear whether you can walk up to the first bridge with 0 cakes, give the troll 0 cakes, receive one cake in return, then run away, put the cake down (cakes you are not "carrying" are tax-exempt), repeat, pick up both cakes and proceed ;-) –  user1501 Jun 9 at 18:47
1  
I mistook the ?? icon of this site for PP and read this question assuming it was about P atents and the villains were patent trolls. –  aitchnyu Jun 10 at 7:11

9 Answers 9

up vote 30 down vote accepted

If you leave home with 2 cakes, you will never pay the troll toll. You give him half of your cakes (one) and he gives one cake back to you.

So the answer is 2.


The exact solution :

Assume we have $x$ cakes,

  • after the 1st bridge, we have $\frac{x}{2}+1 = \frac{x+2}{2}$ cakes
  • after the 2nd bridge, we have $\dfrac{\frac{x+2}{2}+2}{2} = \dfrac{x+2+4}{4}$ cakes
  • after the 3rd bridge, we have $\dfrac{\frac{x+2+4}{4}+2}{2} = \dfrac{x+2+4+8}{8}$ cakes
  • ...
  • after the nth bridge, we have $\frac{x+2+4+\dots+2^n}{2^n}$ cakes
  • So, after the last bridge ($n=7$), we have $\frac{x+2+4+8+16+32+64+128}{128} = \frac{x+254}{128}$ cakes

According to the puzzle, we have 2 cakes at the end,

$$ \frac{x+254}{128} = 2 \\ \implies \boxed{x = 2} $$

The answer is 2.

share|improve this answer
3  
This proves that you CAN have 2 cakes when you leave home. But this doesn't prove that you HAVE to have 2 cakes when you leave home. –  klm123 Jun 8 at 10:41
    
@klm123 - you can now see the solution if you want. –  Alireza Fallah Jun 8 at 11:40
    
you still have a hole in your prove (usual induction doesn't prove anything), but I guess it doesn't matter, this is for author to decide. Sorry for my nicety. –  klm123 Jun 8 at 11:52
    
if you start with less then two cakes, you'll never get two cakes. that really doesn't need proving –  greg m Jun 8 at 16:53
1  
You can generalize this to any number of trolls/cakes pretty easily by noting that $2 + 4 + \dots + 2^n = 2^{n+1}-2$ –  BlueRaja - Danny Pflughoeft Jun 9 at 21:46

The above answers are correct in a sense, but unfortunately incomplete. There are three scenarios:

1) The trolls round down. That is, if you had 3 cakes, they take floor(1.5) = 1 cake from you. In this case, you may leave home with, at minimum, zero (0) cakes.

Why? Consider each troll as below (the item number is the troll toll number):

  1. Takes 1/2 of your cakes (which is 0), and gives you 1. Now you have 1 cake.
  2. Takes 1/2 of your cakes (which is floor(0.5) = 0), and gives you 1. Now you have 2 cakes.
  3. (and all other trolls following) Takes 1/2 of your cakes (which is 1), and gives you 1. Now you have 2 cakes.

Thus, you may start with a minimum of 0 cakes, and end up with 2 at the end of the route. Similarly, one may prove that you may leave home with a maximum of 255 cakes and still arrive at Grandma's with exactly 2.

2) The trolls round up. This is a nearly identical process, so I will neglect the explanation. In this case, you must leave home with a minimum of 2 cakes and a maximum of 255 cakes.

2) The trolls don't round, and deal with floating point numbers: I don't really want to think about this case... :) I believe that a starting value of 2 is minimal, but do not have time to prove so.

share|improve this answer
3  
If the trolls take fractional cakes, it's not hard to show that leaving home with 2 cakes is the only solution. (Just start from the known number of cakes at the end and work backwards; without rounding, there's a one-to-one correspondence between the number of cakes carried before and after each t(r)oll.) –  Ilmari Karonen Jun 9 at 8:02
9  
I really like the idea of the trolls going "Aww, you don't have any cake? Here, have one of mine!" –  Bobson Jun 9 at 14:45
    
@IlmariKaronen True--I can see that a bit better after a good night's rest. –  anorton Jun 9 at 16:27
3  
If the troll rounds down, you can start with a debt of 125 cakes. The first troll takes half of your -125 cakes, -62.5, rounded down (up in negative): -63, you keep -145 - -63 = -62, you receive one, you have -61. With 7 bridges, it will go: -125 -> -61 -> -29 -> -13 -> -5 -> -1 -> 1 -> 2. –  Florian F Sep 25 at 14:35
    
@FlorianF: That is actually cool. I just wonder how can we represent "debt of 125 cakes" into reality. Should we bring a debt contract stating that we have a debt of 125 cakes? –  justhalf 2 days ago

(presses the rewind button on reality)

You leave grandma's house with two cakes. Each time you cross a bridge, you give the troll one cake, and then he gives you back a number of cakes equal to how many you have left.

It's easy to see that every time you leave a bridge, and thus when you return home, you still have two cakes.

share|improve this answer
    
How is this answer different from already posted ones? –  kaine Jun 9 at 19:30
    
@kaine: Presentation. And no solving is needed to obtain the answer. –  Hurkyl Jun 9 at 20:32
1  
@Hyrkyl no solving is needed for the first part of the accepted answer. It just goes into more detail to prove itself. –  kaine Jun 9 at 20:35
2  
I'm not harassing and I'm not the one who downvoted you. Just was hoping to understand what was being contributed by what I saw as a duplicate answer. I won't ask anymore. –  kaine Jun 9 at 20:44
1  
(oh and you showed up in my review becasue it was your first post and I explictly did not want to downvote) –  kaine Jun 9 at 20:50

It depends how you define half of cakes, for example for 3 cakes. Assuming round up:

3 cakes -> half is 2 -> leaves 1 -> +1 back -> you have 2 cakes
4 cakes -> half is 2 -> leaves 2 -> +1 back -> you have 3 cakes
5 -> 3
6 -> 4
7 -> 4
8 -> 5
.. and so on

Theoretically every number between 2 and N should work, figuring out the highest possible number N is left as homework exercise. ;)

Hint, for every number x, the highest one leading directly to it is 2x-1.

share|improve this answer

Answer is 2.

Prove is the following:

If you have 2 cakes after last troll and X cakes after previous troll then 2=(X/2+1) and X = 2.

The same we conclude that number of cakes after each troll wasn't changed.

That means you left with 2 cakes.

share|improve this answer
    
Calculation is clearer if you say: x/2+1=2, so x=(2-1)*2, so x=2. –  TFuto Jun 8 at 20:15
    
@TFuto, thanks) –  klm123 Jun 8 at 20:24

This problem is really too easy, since a moment's reflection (or reading any of the previous answers) shows that travellers with 2 cakes can cross any bridge keeping all their cakes. To make it more interesting, one may generalise to what would be needed at departure if one wants to have 3 cakes (or any other number$~n$) at arrival. I'll assume cakes cannot be subdivided, and that although kind, these are real world trolls that won't let you pass taking any less than half of your cakes (before returning one), so that (like for parking meters) if you ain't got exact change for what you want, you must pay a bit more.

The only point I want to make is that this kind of problems becomes very easy working backwards. If you need$~n$ cakes after passing a bridge, one of those will be returned from the troll, and to have the remaining $n-1$ after paying the troll, you need to have had at least $2(n-1)$ before the bridge. So to cross $k$ bridges and have$~n$ you need to iterate $k$ times the operation $f: n\mapsto2(n-1)$ with starting value$~n$. For instance to cross 7 bridges and have 3 cakes left you need to start out with at least $f(f(f(f(f(f(f(3)))))))=130$ cakes.

There is a nice formula for the result once you realise that $f(2+m)=2+2m$ for all non negative integers $m$, but that is not my main point.

share|improve this answer

It depends on how forgiving your grandma is when you present her with fractional cakes. If she accepts 1.99 cakes as being the same as 2 cakes, then you can start with 1 cake (because [1+254]/128>1.99). If she accepts 1.98 cakes as being the same as 2 cakes, you can start with 0 cakes (because [0+254]/128>1.98).

share|improve this answer
1  
No doubts that 1.99 is not "exactly 2 cakes". –  klm123 Jun 9 at 9:03
1  
but it is interesting that if there were an infinite number of trolls, this would work. –  kaine Jun 9 at 12:47
1  
@kaine but then you'd never be able to get to grandma's house. :P –  Quincunx Jun 12 at 17:33
1  
Only if your name is Zeno. –  Florian F Sep 25 at 14:38

Any solution that is longer than three lines, not including any smug prefaces about other solutions, is overdoing things.

Start from the back: You want to reach grandma with two cakes, so you were left with one before the last troll gave you one. Thus, you reached that troll with two cakes. Thus, we find that reaching a troll with two cakes does the trick. And we extrapolate.

If we were to answer the question of finding every solution, on the other hand...

share|improve this answer

The minimum number of cakes is 2 No matter how many bridges there are.

with 2 cakes you have to give one of them away and will get another as a reward. then you can cross further bridges infinitely.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.