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 $c_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 $c_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 $c_f=2$ cakes. If I translate these sentences into math I get
$$\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 $\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 $c_f=2$ cakes after crossing the second bridge. In math I write this as
$$\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
$$\frac{c_0}{4}+\frac{3}{2}=c_f$$
Now the third bridge. Same rigamarole as before so my equation becomes
$$\frac{\frac{c_0}{4}+\frac{3}{2}}{2} + 1 = \frac{c_0}{8}+\frac{7}{4} = c_f$$
And the fourth bridge
$$\frac{\frac{c_0}{8}+\frac{7}{4}}{2} + 1 = \frac{c_0}{16}+\frac{15}{8} = c_f$$
And the fifth bridge
$$\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 $\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
$$\frac{c_0}{2^b} = \frac{c_0}{2^5} = \frac{c_0}{32}$$
where $b$ is the number of bridges I have crossed.
The second term is $\frac{31}{16}$. If I look at the pattern I see that this fraction increases according to
$$\frac{2^b-1}{2^{b-1}} = \frac{2^5-1}{2^4} = \frac{31}{16}$$
where $b$ is the number of bridges I have crossed.
Now, I can re-write my equation like this:
$$\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
$$\frac{c_0}{2^4} + \frac{2^4-1}{2^{3}} = c_f$$
which equals
$$\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 $c_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
$$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 ($c_0$) in order to end up with 2 cakes ($c_f=2$) after crossing 7 bridges ($b=7$). And, since I left $c_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 $c_f=3$.
A special thanks to my daughter and Mr. Jones at OIS for providing the inspiration for this post.
