Associated Topics || Dr. Math Home || Search Dr. Math

### 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!

All you have to do is figure out a sensible interpretation of what it
means to give someone a negative number of mangoes. (Maybe you give
him a bill, payable in mangoes? Maybe you take the mangoes away from
him?)

That was an interesting question! Thanks for asking it.

-Dr. Ian
http://mathforum.org/dr.math/
```
Associated Topics:
High School Puzzles
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/