Paying the Troll toll

Question

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.

Answer 1

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 1^st bridge, we have $\frac{x}{2}+1 = \frac{x+2}{2}$ cakes
- after the 2^nd bridge, we have $\dfrac{\frac{x+2}{2}+2}{2} = \dfrac{x+2+4}{4}$ cakes
- after the 3^rd bridge, we have $\dfrac{\frac{x+2+4}{4}+2}{2} = \dfrac{x+2+4+8}{8}$ cakes - ...
- after the n^th 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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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!

Answer 10

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.

Answer 11

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

Answer 12

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.