A palace has seven gates. At every gate is a guard who takes half the number of apples you have got and returns one back to you. What should be the number of apples that you need to carry initially so that you are left with exactly two apples after you pass all the seven gates?
Answers
Step-by-step explanation:
Mangoes at the Gates
Date: 04/06/2001 at 23:27:35
From: John Dickerson
Subject: A question
What kind of math problem is the following? I heard it on CarTalk, an
NPR show on the radio. You could go there to see the details, but they
do not explain how they got their answer(s).
Briefly: You want to pick some mangoes from a tree that is surrounded
by seven walls with seven guards, one at each gated wall. To get to
the tree you tell each guard that you will give him half of all the
mangos you have but that guard must give you back one mango. The
question is, what is the minimum number of mangos you must pick to
satisfy these conditions and have at least one mango left when you
exit the seventh gate?
When I set up the problem I had a seven-tiered complex fraction equal
to one, and my final answer was negative two. Where did I go wrong?
I like your site very much.
John Dickerson
Date: 04/09/2001 at 07:09:18
From: Doctor Ian
Subject: Re: A question
Hi John,
If you have two mangoes at the end, then you have at least one mango,
right?
Let's say you leave the tree with two mangoes. You get to the
innermost guard. You give him half the mangoes - which is to say, one
mango - and he gives one back to you. So now you have two mangoes
again.
You can repeat this as often as you need to, whether the number of
fences is 7 or 700. So my answer would be; you need to leave the tree
with two mangoes.
If you want to work backward, let's say you end up with N mangoes.
Then you must have shown up at the 7th gate with 2N-2 mangoes.
(For example, if you showed up with eight mangoes, you would give the
guard four, and get back one, leaving you with five. So to end up with
five mangoes, you need to show up with 2(5)-2 = 8 mangoes.)
At the sixth gate, you'd need 2(2N-2)-2 mangoes.
(That is, to end up with five mangoes, you would have to show up at
the sixth gate with 2(2(5)-2)-2 = 2(10-2)-2 = 2(8)-2 = 14 mangoes. You
give seven to the guard and get one back, leaving eight, which we
already know is the number you need for the seventh gate.)
At the fifth gate, you'd need 2(2(2N-2)-2)-2 mangoes, and so on:
Gate Mangoes
---- -------
7 2N-2
6 2(2N-2)-2
5 2(2(2N-2)-2)-2
4 2(2(2(2N-2)-2)-2)-2
3 2(2(2(2(2N-2)-2)-2)-2)-2
2 2(2(2(2(2(2N-2)-2)-2)-2)-2)-2
1 2(2(2(2(2(2(2N-2)-2)-2)-2)-2)-2)-2
Now, notice that this doesn't work at all for N = 1, since 2(1)-2 = 0.
So the smallest number of mangoes that you can possibly end up with is
two.
So what is 2(2(2(2(2(2(2N-2)-2)-2)-2)-2)-2)-2 for N = 2?
2(2(2(2(2(2(2*2-2)-2)-2)-2)-2)-2)-2
= 2(2(2(2(2(2(4-2)-2)-2)-2)-2)-2)-2
= 2(2(2(2(2(2(2)-2)-2)-2)-2)-2)-2
= 2(2(2(2(2(4-2)-2)-2)-2)-2)-2
= 2(2(2(2(2(2)-2)-2)-2)-2)-2
= 2(2(2(2(4-2)-2)-2)-2)-2
= 2(2(2(2(2)-2)-2)-2)-2
= 2(2(2(4-2)-2)-2)-2
= 2(2(2(2)-2)-2)-2
= 2(2(4-2)-2)-2
= 2(2(2)-2)-2
= 2(4-2)-2
= 2(2)-2
= 4 - 2
= 2
What about for other numbers?
2(2(2(2(2(2(2N-2)-2)-2)-2)-2)-2)-2
= 2(2(2(2(2(4N-4-2)-2)-2)-2)-2)-2
= 2(2(2(2(8N-8-4-2)-2)-2)-2)-2
= 2(2(2(16N-16-8-4-2)-2)-2)-2
= 2(2(32N-32-16-8-4-2)-2)-2
= 2(64N-64-32-16-8-4-2)-2
= 128N-128-64-32-16-8-4-2
= (2^7)N - (2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 + 2^7)
= (2^7)N - (2^8 - 2)
So for N = 5,
= (2^7)(5) - (2^8 - 2)
= 640 - 254
= 386
Let's check that:
1st gate: From 386, give 193 to the guard, get one back: 194
2nd gate: From 194, give 97 to the guard, get one back: 98
3rd gate: From 98, give 49 to the guard, get one back: 50
4th gate: From 50, give 25 to the guard, get one back: 26
5th gate: From 26, give 13 to the guard, get one back: 14
6th gate: From 14, give 7 to the guard, get one back: 8
7th gate: From 8, give 4 to the guard, get one back: 5
So it appears to work. Now we can ask; how many mangoes would he have
to pick to end up with 3 instead of 2?
(2^7)(3) - 254 = 130
So to end up with one extra mango, he'd have to leave the tree with
128 extra mangoes! Talk about your marginal tax rates...
Note that we can generalize this to any number of gates. If the number
of gates is G, then to end up with N mangoes, you have to pick:
(2^G)N - (2^(G+1) - 2)
mangoes. Note that 2 will remain the best choice,
(2^G)(2) - (2^(G+1) - 2) = 2^(G+1) - (2^(G+1) - 2)
= 2^(G+1) - 2^(G+1) + 2
= 2
regardless of the number of gates.
Note also that for N = 1, we get:
(2^G)(1) - (2^(G+1) - 2) = 2^G - (2*2^G - 2)
= 2^G - 2*2^G + 2
= 2^G(1 - 2) + 2
= 2 - 2^G
This is only positive when G = 0, which tells us that you can only end
up with one mango if there are no gates.
Or maybe not... let's say there are three gates, and you want to end
up with one mango. Then you need to pick:
(2^3)(1) - (2^(3+1) - 2) = 8 - (16 - 2)
= 8 - 14
= -6
So let's say you walk up to the first gate with -6 mangoes. You give
half (-3) to the guard, and he gives you one back, so you now have -2
mangoes. You go to the 2nd gate with -2 mangoes. You give half (-1) to
the guard, and he gives you one back, so you now have no mangoes. You
go to the 3rd gate with no mangoes. You give half (0) to the guard,
and he gives you one back, so you now have one mango!