Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/