# Paying the Troll toll

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.

• 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? – Etheryte Jun 8 '14 at 23:34
• @Nit and will he then give you one cake back, so you end up with 1.5 cakes? – wchargin Jun 9 '14 at 0:56
• @Nit Then you could go back home, put half a cake in the fridge, and repeat. Infinite cakes! Trolling the trolls? – wchargin Jun 9 '14 at 15:46
• @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 '14 at 18:47
• 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. – Zibbobz Oct 8 '14 at 19:06

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.

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:

• 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 '14 at 10:41
• @klm123 - you can now see the solution if you want. – Alireza Fallah Jun 8 '14 at 11:40
• if you start with less then two cakes, you'll never get two cakes. that really doesn't need proving – greg m Jun 8 '14 at 16:53
• 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 '14 at 21:46
• 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. – Peter LeFanu Lumsdaine Oct 25 '14 at 22:53

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.

• 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 '14 at 8:02
• I really like the idea of the trolls going "Aww, you don't have any cake? Here, have one of mine!" – Bobson Jun 9 '14 at 14:45
• 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 '14 at 14:35
• 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. – Florian F Oct 2 '14 at 11:55
• 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. – Joe Z. Oct 16 '14 at 14:03

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

• How is this answer different from already posted ones? – kaine Jun 9 '14 at 19:30
• @kaine: Presentation. And no solving is needed to obtain the answer. – user1502 Jun 9 '14 at 20:32
• @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 '14 at 20:35
• 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 '14 at 20:44
• (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 '14 at 20:50

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.

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.

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.

• Calculation is clearer if you say: x/2+1=2, so x=(2-1)*2, so x=2. – TFuto Jun 8 '14 at 20:15

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

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

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

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.

• This doesn't offer more than what the existing answers do... – Assafi Cohen-Arazi Nov 5 '17 at 5:02

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!

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

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


You don't need any cake.

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.

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.