127
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 3
    $\begingroup$ 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? $\endgroup$
    – Etheryte
    Jun 8, 2014 at 23:34
  • 4
    $\begingroup$ @Nit and will he then give you one cake back, so you end up with 1.5 cakes? $\endgroup$
    – wchargin
    Jun 9, 2014 at 0:56
  • 24
    $\begingroup$ @Nit Then you could go back home, put half a cake in the fridge, and repeat. Infinite cakes! Trolling the trolls? $\endgroup$
    – wchargin
    Jun 9, 2014 at 15:46
  • 6
    $\begingroup$ @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 ;-) $\endgroup$
    – user1501
    Jun 9, 2014 at 18:47
  • 24
    $\begingroup$ What this puzzle fails to point out is that you will be trapped beyond Grandma's house forever if you let her eat your cake. Thus proving you can't have your cake and eat it too. $\endgroup$
    – Zibbobz
    Oct 8, 2014 at 19:06

12 Answers 12

Reset to default
96
$\begingroup$

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,

because:

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

So:

The answer is 2.

Improve this answer
$\endgroup$
8
  • 12
    $\begingroup$ 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. $\endgroup$
    – klm123
    Jun 8, 2014 at 10:41
  • $\begingroup$ @klm123 - you can now see the solution if you want. $\endgroup$
    – Alireza Fallah
    Jun 8, 2014 at 11:40
  • 1
    $\begingroup$ if you start with less then two cakes, you'll never get two cakes. that really doesn't need proving $\endgroup$
    – greg m
    Jun 8, 2014 at 16:53
  • 3
    $\begingroup$ You can generalize this to any number of trolls/cakes pretty easily by noting that $2 + 4 + \dots + 2^n = 2^{n+1}-2$ $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Jun 9, 2014 at 21:46
  • 1
    $\begingroup$ It’s easy enough to prove that you need at least two cakes: if $x < 2$, then $x/2 + 1 < 2$. So, by induction, if you start out with less than two cakes, then after any number of trolls, you still have strictly less than two cakes. $\endgroup$
    – Peter LeFanu Lumsdaine
    Oct 25, 2014 at 22:53
59
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
8
  • 8
    $\begingroup$ 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.) $\endgroup$
    – Ilmari Karonen
    Jun 9, 2014 at 8:02
  • 39
    $\begingroup$ I really like the idea of the trolls going "Aww, you don't have any cake? Here, have one of mine!" $\endgroup$
    – Bobson
    Jun 9, 2014 at 14:45
  • 17
    $\begingroup$ 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. $\endgroup$
    – Florian F
    Sep 25, 2014 at 14:35
  • 5
    $\begingroup$ Well, I thought of 125 notes saying "IOU 1 cake". And if you want to do a reality check you'll have just as much trouble finding trolls on bridges than to represent negative cakes. $\endgroup$
    – Florian F
    Oct 2, 2014 at 11:55
  • 3
    $\begingroup$ Well hold on now, if the trolls round their tolls down, you'll end up with 3 cakes if you start with any more than 2. $\endgroup$
    – user88
    Oct 16, 2014 at 14:03
21
$\begingroup$

(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.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ How is this answer different from already posted ones? $\endgroup$
    – kaine
    Jun 9, 2014 at 19:30
  • 4
    $\begingroup$ @kaine: Presentation. And no solving is needed to obtain the answer. $\endgroup$
    – user1502
    Jun 9, 2014 at 20:32
  • 3
    $\begingroup$ @Hyrkyl no solving is needed for the first part of the accepted answer. It just goes into more detail to prove itself. $\endgroup$
    – kaine
    Jun 9, 2014 at 20:35
  • 4
    $\begingroup$ 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. $\endgroup$
    – kaine
    Jun 9, 2014 at 20:44
  • 2
    $\begingroup$ (oh and you showed up in my review becasue it was your first post and I explictly did not want to downvote) $\endgroup$
    – kaine
    Jun 9, 2014 at 20:50
11
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Calculation is clearer if you say: x/2+1=2, so x=(2-1)*2, so x=2. $\endgroup$
    – TFuto
    Jun 8, 2014 at 20:15
5
$\begingroup$

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...

Improve this answer
$\endgroup$
3
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ No doubts that 1.99 is not "exactly 2 cakes". $\endgroup$
    – klm123
    Jun 9, 2014 at 9:03
  • 5
    $\begingroup$ but it is interesting that if there were an infinite number of trolls, this would work. $\endgroup$
    – kaine
    Jun 9, 2014 at 12:47
  • 3
    $\begingroup$ @kaine but then you'd never be able to get to grandma's house. :P $\endgroup$
    – Justin
    Jun 12, 2014 at 17:33
  • 5
    $\begingroup$ Only if your name is Zeno. $\endgroup$
    – Florian F
    Sep 25, 2014 at 14:38
2
$\begingroup$

The minimum number of cakes is

2, no matter how many bridges there are.

because 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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ This doesn't offer more than what the existing answers do... $\endgroup$
    – Assafi Cohen-Arazi
    Nov 5, 2017 at 5:02
2
$\begingroup$

This is the better answer! No partial cakes involved.

Start from your house with 130 cakes. As you proceed to each bridge, you need to give the troll half your cakes to cross. After crossing the bridge, the nice troll gives you 1 cake back. 1st bridge: 130/2=65+1=66 2nd bridge: 66/2=33+1=34 3rd bridge: 34/2=17+1=18 4th bridge: 18/2=9+1=10 5th bridge: 10/2=5+1=6 6th bridge: 6/2=3+1=4 7th bridge: 4/2=2+1=3 After you leave the 7th bridge and the troll gave you 1 cake back, you will have 3 cakes remaining.....
By this time you are famished from the long journey and can't resist, so you choose to eat one of the cakes before you get to Grandma's.
This will leave you with 2 cakes when you arrive at Grandma's house as planned.

The moral of the story is: You had your cake, and got to eat it too! In the end everyone is happy!
If you left your house with 2 cakes, Grandma would have gotten hers but all the Trolls would be really pissed off!

Improve this answer
$\endgroup$
1
$\begingroup$

I took some time to implement this in python and ruby, just for fun. Yes, this is a brute force approach.

Python 3

#!/usr/bin/env python3

def how_many_cakes(bridges, cakes_for_grandma, troll_toll, troll_cake_return):
    cakes = 1
    x = 0
    while x != cakes_for_grandma:
        x = cakes
        for bridge in range(bridges):
            x = troll_toll_return(x, troll_toll, troll_cake_return)
        cakes += 1
        if x >= cakes_for_grandma:
            return x


def troll_toll_return(cakes_carried, troll_toll, troll_cake_return):
    toll = cakes_carried * troll_toll
    total_cake_return = toll + troll_cake_return
    return total_cake_return


two_cakes_for_grandma = how_many_cakes(7, 2, 0.5, 1)
print(f"You need to leave your house with {two_cakes_for_grandma}")

ruby

#!/usr/bin/env ruby

def how_many_cakes(bridges, cakes_for_grandma, troll_toll, troll_cake_return)
  cakes = 1
  x = 0
  while x != cakes_for_grandma do
    x = cakes
    for bridge in 1..bridges do
      x = x * troll_toll
      x = x + troll_cake_return
    end
    cakes += 1
    if x >= cakes_for_grandma then
        return x
    end
  end
end

two_cakes_for_grandma = how_many_cakes(7, 2, 0.5, 1)
puts "You need to leave your house with " + two_cakes_for_grandma.to_s
Improve this answer
$\endgroup$
1
$\begingroup$

The number of cakes you need is

No cake at all.

Because

When you cross a bridge, you give half of no cake and you get one free cake. Eat it.
When you cross the last bridge don't eat the cake but deposit it in front of Grandma's house.
Cross the last bridge again, get a free cake, eat it.
Cross the last bridge a third time, get a free cake, bring it to Grandma.
Tadaa! You have 2 cakes for Grandma.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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