Trolls and Tolls

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?

An excellent question! Let’s work out the problem with variables first, and see if there is an underlying formula waiting to be discovered.

I start out with c0c_0 cakes (I don’t know what this number is yet) and I want to end up at Grandma’s house with 2 cakes, or cf=2c_f=2.

I cross the first bridge, and the troll takes half my cakes but gives me one back. After I cross the bridge, I still want to have cf=2c_f=2 cakes. If I translate these sentences into math I get

c02+1=cf\frac{c_0}{2}+1=c_f

I cross the second bridge and the troll takes half my cakes again but gives me one back. I am bringing c02+1\frac{c_0}{2}+1 with me to the second bridge, because that’s what I have left over from the first bridge. And, as before, I still want to have cf=2c_f=2 cakes after crossing the second bridge. In math I write this as

c02+12+1=cf\frac{\frac{c_0}{2}+1}{2}+1=c_f

In other words, I take the formula from the first bridge and stick it into the numerator of the first term of the equation for the second bridge. I simplify to get

c04+32=cf\frac{c_0}{4}+\frac{3}{2}=c_f

Now the third bridge. Same rigamarole as before so my equation becomes

c04+322+1=c08+74=cf\frac{\frac{c_0}{4}+\frac{3}{2}}{2} + 1 = \frac{c_0}{8}+\frac{7}{4} = c_f

And the fourth bridge

c08+742+1=c016+158=cf\frac{\frac{c_0}{8}+\frac{7}{4}}{2} + 1 = \frac{c_0}{16}+\frac{15}{8} = c_f

And the fifth bridge

c016+1582+1=c032+3116=cf\frac{\frac{c_0}{16}+\frac{15}{8}}{2} + 1 = \frac{c_0}{32}+\frac{31}{16} = c_f

Now I’ve done this enough to where I can see a pattern. At bridge five, the first fraction is c032\frac{c_0}{32}. I’ve crossed five bridges at this point. The numerator has stayed the same but the denominator has been multiplied by 2 each time. So, I can re-write the first term more generally as

c02b=c025=c032\frac{c_0}{2^b} = \frac{c_0}{2^5} = \frac{c_0}{32}

where bb is the number of bridges I have crossed.

The second term is 3116\frac{31}{16}. If I look at the pattern I see that this fraction increases according to

2b−12b−1=25−124=3116\frac{2^b-1}{2^{b-1}} = \frac{2^5-1}{2^4} = \frac{31}{16}

where bb is the number of bridges I have crossed.

Now, I can re-write my equation like this:

c02b+2b−12b−1=cf\frac{c_0}{2^b} + \frac{2^b-1}{2^{b-1}} = c_f

I can plug an any bridge number (1, 2, 3, and so on) and get any of the equations above. For example, for bridge 4 I get

c024+24−123=cf\frac{c_0}{2^4} + \frac{2^4-1}{2^{3}} = c_f

which equals

c016+158=cf\frac{c_0}{16} + \frac{15}{8} = c_f

which is what I got the first time. So, the equation works! Now all I have to do is re-arrange it to solve for c0c_0 and then I can figure out how many cakes I need to start with for any number of bridges–not just 7! The equation is

c0=2b(cf−2b−12b−1)c_0=2^b\left(c_f - \frac{2^b-1}{2^{b-1}}\right)

Voila. Now I can calculate how many cakes I need to start with (c0c_0) in order to end up with 2 cakes (cf=2c_f=2) after crossing 7 bridges (b=7b=7). And, since I left cfc_f in the equation, I also don’t have to limit myself to ending up with just 2 cakes. I could figure out how many cakes I need to start with if I cross 7 bridges and want to end up with 3 cakes, for example. All I need to do is make cf=3c_f=3.

A special thanks to my daughter and Mr. Jones at OIS for providing the inspiration for this post.