Mangoes at the GatesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/