Going to Grandma's house

[Guest]

You're on your way to your Grandma's house, who lives on the other side of the village. It's her birthday, and you made some cakes for her.

On the way, you have to cross seven bridges, and as it goes in, there is a troll under every bridge! Each troll insists that you pay him. Before you can cross their bridges, you have to give them half of the cakes you are carrying, but as they are generous trolls, they each give you back one whole cake.

How many cakes do you have to start your trip with to make sure that you arrive at your Grandma's house with exactly 2 cakes?

[Guest]

2 cakes.

1st bridge: half of your 2 cakes is one, and then troll gives you back one cake you left with 2.

2nd bridge: half of your 2 cakes is one, and then troll gives you back one cake you left with 2.

3rd, 4th, 5th, 6th, 7th you left with 2 cakes.

????

[Guest]

Nice!

[Guest]

Nice!

Dunno if anyone is actually interested in the proper way (at least the way I used) to solve this.

I've been doing recursion in my algorithms course so I gave that a try:

The formula is: Xn = X(n-1)/2 + 1

The second to last Xn formula would look something like this:

2 = X(n-1)/2+1

2 - 1 = X(n-1)/2

1 * 2 = X(n-1)

2 = X(n-1)

Since you'll always input the same number into the same formula, you know it will never change.

Edited March 4, 2008 by Dave Lugg

[Guest]

These trolls are pretty stupid. They ought to ask how many cakes you have before they offer the take half, return one deal. I mean, what if you only had one cake? Then the trolls would totally be getting screwed.

[Guest]

2 each time you gie them a cake they give it back.

[Guest]

I once heard a different version of this.

2 cakes, They get one which is half and give it back to you.

[Guest]

I know the question states that you need to arrive with exactly 2 cakes. But, theoretically, you could leave your house with nothing (no cakes) and arrive at grandma's with 1.984375 cakes (she wouldn't know the difference...)

[Guest]

I know the question states that you need to arrive with exactly 2 cakes. But, theoretically, you could leave your house with nothing (no cakes) and arrive at grandma's with 1.984375 cakes (she wouldn't know the difference...)

Leaving with nothing is economically the better choice but using the same theory you could also leave with 1 cake and arrive with 1.991875 cakes or 3 and arrive with 2.0078125.

Close enough that grandma would never know it wasn't two, but like you said, it's not exactly 2 and they'd be pretty messed up cakes from all the dividing they'd have to go through.

[Guest]

If you wanted to scam the trolls, you could leave your house with less than two cakes and a knife to cut the cake; the first encounter would go something like this:

You: "Mr. troll, I have but one cake."

Troll: "OK, you give half. But me nice troll, so I give you a cake me took from last sap. He had eleventy-three. Was over-prepared. Maybe a boyscout. Maybe just got cake-making merit badge."

You then have 1.5 cakes. Next Bridge:

Troll: "ME LIKE CAKE!!"

You: "I only have 1 and a half cakes, Mr. Troll!"

Troll: "Okey-Dokey. I take....ummmm...three-quarters cake. Then me give you one, because troll mamas don't raise greedy troll rug rats."

You then have 1.75 cakes. Regardless of how many cakes with which you leave, you approach two cakes asymptotically, so that the only way to arrive with two cakes is to have that many when you start.

[Guest]

If you leave the house with 130 cakes you end up with 3, the first troll gets 64 and the last troll gets 1!

[Guest]

I heard a different variant in which the problem was to find the number of cakes taken initially given that, you end up having the same number of cakes.

[Guest]

OK, I went straight to "formula mode", without trying to find a simple solution. But here's my generic answer, applicable to any number of bridges, and any number of leftover cakes. (I think)

B=bridges

C1=initial cakes

C2=leftover cakes

(1/2^B)*C1 + (2^B - 1)/(2^(B-1)) = C2

With B=7, and C2=2... C1=2

With B=7, and C2=3... C1=130

[Guest]

It's very interesting that there isn't a larger solution to this problem. The only way to arrive with 2 cakes is to start out with 2 cakes.

I wonder if there is a way for the trolls to take so that for every single number of cakes you will always arrive with a different amount than you started, given that they first take away a fraction of your cakes and give back a whole number.

In other words:

(x/y)+z != x where x is any real number

Edited July 1, 2008 by pw0nzd