Saturday, March 03, 2007
Camel Banana Math Problem
I haven’t played with my wii lately (o_O), so I didn’t take pictures of the 4 mii’s yet, so I’ll post those pictures later when I get them. Anyway:
(Blogger is being an ass, to the point where I may just stop using it. Anyway, now I replaced all LESS THAN symbols with the words, because blogger sucks ass. I think I've spent more time formatting this post than writing it.)
Recently, Vinh got this puzzle to do at school, and I remember doing it 4 or 5 years ago. I remember getting a quite optimal answer, and as far as I know, it’s still optimal – but I remember now, that I got the answer through trial and error. So right now I’d like to discuss the problem and make a few theorems or whatever, so that the answer doesn’t feel so trial-and-errory, and instead, more based on some needed theorems.
For those that don’t remember the problem, or haven’t done it, here’s the problem (and if you don’t want to read any spoilers, like solution and whatever, skip the rest of this post until you’ve had enough):
You have a banana factory/plantation, and you have to move bananas to a destination 1000 km away. You have a camel, that can hold at most 1000 bananas, and for every km it travels, it has to eat 1 banana. Your factory has 3000 bananas. What is the most number of bananas you can bring to your destination?
So for example, if you start by taking 1000 bananas, and you travel all 1000 km, you’ll end up at your destination with 0 bananas. If you start with 1000 bananas, travel 333 km, drop off 334 bananas, and then go back 333 km, you’ll be back at the start, but with 334 bananas at km333. Then you take another 1000, walk up to 333, refill to 1000 (so you leave 1 banana behind), and then you can walk the rest of the way and end up at the village with 333 bananas.
Of course, that’s not optimal, since you’ve left 1000 bananas at the plant. So… keep trying! Anyway, if you don’t want to look at spoilers, don’t read the rest of the post. It’s a pretty good puzzle. Anyway, after theorizing, I want to know how the solution changes if we had 4000 bananas instead of 3000, or some other variable different. So here we go!
First, a few definitions:
“are carrying” : this is how many bananas your camel has.
“have at point X”: At point X, this is how many bananas are on the ground.
“goal / destination / village”: All interchangeable for destination.
“Phase”: Phase 1 is when you take 1000 bananas at the beginning, have 2000 left at the factory. Phase 2 is the next step, and Phase 3 is when you take the last 1000 bananas.
Theorem 1: If you are carrying 1000 bananas at point X, you’ll carry X bananas to the destination.
Okay, I’m omitting some details, like, this is your last 1000 bananas, and you’re going straight to the goal from here (so, Phase3). But for example, if you are holding 1000 bananas at pt400, you’ll make it to the end with 400 bananas – since you’ll eat 600 bananas on the way, and you’ll have 400.
Theorem 2: If you have (not carrying, have) X bananas at point X, you’ll carry X bananas to the destination.
That is, if you have 400 bananas at pt400, you will leave the base with 1000, eat 400, refill 400, and then by theorem 1, you’ll carry X (or 400) to the destination.
Theorem 3: If you are carrying 1000 bananas at point Y (Y less than X), then you only need to have X-Y bananas at point X, to carry X bananas to destination.
Usually, you’ll need 600 bananas at point 600 to carry 600 to the goal. However, if you are carrying 1000 bananas at pt200, you’ll only need 400 bananas at pt 600, to get 600 bananas to the goal. Thus,
Corollary 1: If you have Y bananas at point Y (Y less than X), then you need to have X-Y bananas at point X.
That’s obvious.
I don’t want to make a point that there can be infinite points, not just Y and X – you can have 3, or 4, or 1000 points.
Hmm… this puzzle could be very complicated… I think to get a good goal, and to get all the theorems we need, we have to work backwards. So first I have to describe something that happened in my solution.
On my final run, I did use Y and X, Y less than X. So I had Y bananas at Y, and X-Y bananas at X, or X-Y+1 or so, but at least X-Y. Does that say anything about phase 2?
On Phase 2, you want to maximize X, because X is the number of bananas you’ll have at the end. Wait… does that mean
Corollary 2: X-Y = 333.
?? I think it does. That means you’ll have 1000 bananas at Y, then you maximize X, so that X-Y = 333, and you’ll have 334 bananas at X. Hmm, this might have just gotten a bit simpler. Anyway, check…
ACK! I was about to write a theorem, but then I got confused, so I checked my solution, and I think a few of my theorems are wrong! My solution is based on… another theorem which I have yet to invent. Wow, did you enjoy reading all that? My theorems maybe wrong… like, they work, but my solution doesn’t totally follow them all. Anyway, if you were curious and you read this far, and all of a sudden you don’t want my solution, don’t read on! Anyway…
The Starting Point Theorem: If you are carrying 1000 bananas, and you have 1000 or more bananas at point Y, you can carry out two (or possibly three) phases starting from Y.
Confusing? Perhaps. At point 0 (at the factory), you have 3000 bananas, so you can carry 1000, and “have” 2000 leftover, so obviously you can carry out all 3 phases. After phase 1, you’ll carry 1000 and have 1000, so you can carry out 2 remaining phases.
ACK! What the hell? I just thought of something, redid my solution, and… there are 2 ways to come up with the same solution? ARGHH!!!
Okay, I have a solution based on my first 3 theorems and their corollaries, and I have another solution based on the Starting Point Theorem. Why was my first solution so convoluted? Unless I made a mistake with my easy solution… lemme check…
WHOA. My 2nd solution is so much easier and makes so much sense. So forget the Starting Point Theorem for now (called the SP Theorem), and I make up theorem 4:
Theorem 4: At the end of phase 1, point Y needs 3Y bananas.
Remember, in Phase 2, you want to maximize X, which means you need 1000 bananas at point Y. Between now and the end of the game, how many times do you pass point Y? You pass it 3 times. First, when you go to maximize X, you pass it once, so you want Y bananas to refill to 1000; when you’re done maximizing X, you’ll have 0 bananas at point Y, so you need Y bananas to go home; and then on your final phase, you want to refill to 1000 at point Y, so you need Y bananas, by some Corollary 1, I think.
Corollary 3: To do theorem 4, you need 5Y bananas.
3Y bananas to put down, Y bananas to get there, Y bananas to get back. And you don’t want to be wasteful, so:
5Y = 1000.
Y = 200.
X- Y = 333 by corollary 2.
X = 333 + 200.
X = 533.
Wow, I just solved the camel/banana puzzle. Now who wants to hear my first solution?? Sure you do. As I said, it follows the SP Theorem. You can guess from the SP theorem that you’ll end up with two phases at one part; and if you only have 2000 bananas, the most you can get to the destination is 333. So oddly enough, I came up with:
Start with 3000. Take 1000, move to 100, drop 800, and go home.
Take another 1000, refill at 100; so there are 700 bananas left at 100;
Go up to 200, drop 800, go back to 100. There are 700 bananas left there, and I’m carrying 0, so I take all 700, go back to pt200; I’m carrying 600, so I drop 400, and I eat 200 on my way home. Now I have 800+400 bananas at point 200, so I have 1200 bananas.
I take the last 1000 bananas, refill at point 200; So I am carrying 1000 bananas, and I have 1000 bananas left at point 2, so I can just use SP theorem, or I’ll write it out:
I travel 333 km to 533, drop 334 bananas, go back, grab the 1000 from pt 200, and by Theorem 3, I get to the destination with 533 bananas.
How did I come up with that? I don’t know!
Comments:
Post a Comment
I haven’t played with my wii lately (o_O), so I didn’t take pictures of the 4 mii’s yet, so I’ll post those pictures later when I get them. Anyway: (Blogger is being an ass, to the point where I may just stop using it. Anyway, now I replaced all LESS THAN symbols with the words, because blogger sucks ass. I think I've spent more time formatting this post than writing it.) Recently, Vinh got this puzzle to do at school, and I remember doing it 4 or 5 years ago. I remember getting a quite optimal answer, and as far as I know, it’s still optimal – but I remember now, that I got the answer through trial and error. So right now I’d like to discuss the problem and make a few theorems or whatever, so that the answer doesn’t feel so trial-and-errory, and instead, more based on some needed theorems. For those that don’t remember the problem, or haven’t done it, here’s the problem (and if you don’t want to read any spoilers, like solution and whatever, skip the rest of this post until you’ve had enough): You have a banana factory/plantation, and you have to move bananas to a destination 1000 km away. You have a camel, that can hold at most 1000 bananas, and for every km it travels, it has to eat 1 banana. Your factory has 3000 bananas. What is the most number of bananas you can bring to your destination? So for example, if you start by taking 1000 bananas, and you travel all 1000 km, you’ll end up at your destination with 0 bananas. If you start with 1000 bananas, travel 333 km, drop off 334 bananas, and then go back 333 km, you’ll be back at the start, but with 334 bananas at km333. Then you take another 1000, walk up to 333, refill to 1000 (so you leave 1 banana behind), and then you can walk the rest of the way and end up at the village with 333 bananas. Of course, that’s not optimal, since you’ve left 1000 bananas at the plant. So… keep trying! Anyway, if you don’t want to look at spoilers, don’t read the rest of the post. It’s a pretty good puzzle. Anyway, after theorizing, I want to know how the solution changes if we had 4000 bananas instead of 3000, or some other variable different. So here we go! First, a few definitions: “are carrying” : this is how many bananas your camel has. “have at point X”: At point X, this is how many bananas are on the ground. “goal / destination / village”: All interchangeable for destination. “Phase”: Phase 1 is when you take 1000 bananas at the beginning, have 2000 left at the factory. Phase 2 is the next step, and Phase 3 is when you take the last 1000 bananas. Theorem 1: If you are carrying 1000 bananas at point X, you’ll carry X bananas to the destination. Okay, I’m omitting some details, like, this is your last 1000 bananas, and you’re going straight to the goal from here (so, Phase3). But for example, if you are holding 1000 bananas at pt400, you’ll make it to the end with 400 bananas – since you’ll eat 600 bananas on the way, and you’ll have 400. Theorem 2: If you have (not carrying, have) X bananas at point X, you’ll carry X bananas to the destination. That is, if you have 400 bananas at pt400, you will leave the base with 1000, eat 400, refill 400, and then by theorem 1, you’ll carry X (or 400) to the destination. Theorem 3: If you are carrying 1000 bananas at point Y (Y less than X), then you only need to have X-Y bananas at point X, to carry X bananas to destination. Usually, you’ll need 600 bananas at point 600 to carry 600 to the goal. However, if you are carrying 1000 bananas at pt200, you’ll only need 400 bananas at pt 600, to get 600 bananas to the goal. Thus, Corollary 1: If you have Y bananas at point Y (Y less than X), then you need to have X-Y bananas at point X. That’s obvious. I don’t want to make a point that there can be infinite points, not just Y and X – you can have 3, or 4, or 1000 points. Hmm… this puzzle could be very complicated… I think to get a good goal, and to get all the theorems we need, we have to work backwards. So first I have to describe something that happened in my solution. On my final run, I did use Y and X, Y less than X. So I had Y bananas at Y, and X-Y bananas at X, or X-Y+1 or so, but at least X-Y. Does that say anything about phase 2? On Phase 2, you want to maximize X, because X is the number of bananas you’ll have at the end. Wait… does that mean Corollary 2: X-Y = 333. ?? I think it does. That means you’ll have 1000 bananas at Y, then you maximize X, so that X-Y = 333, and you’ll have 334 bananas at X. Hmm, this might have just gotten a bit simpler. Anyway, check… ACK! I was about to write a theorem, but then I got confused, so I checked my solution, and I think a few of my theorems are wrong! My solution is based on… another theorem which I have yet to invent. Wow, did you enjoy reading all that? My theorems maybe wrong… like, they work, but my solution doesn’t totally follow them all. Anyway, if you were curious and you read this far, and all of a sudden you don’t want my solution, don’t read on! Anyway… The Starting Point Theorem: If you are carrying 1000 bananas, and you have 1000 or more bananas at point Y, you can carry out two (or possibly three) phases starting from Y. Confusing? Perhaps. At point 0 (at the factory), you have 3000 bananas, so you can carry 1000, and “have” 2000 leftover, so obviously you can carry out all 3 phases. After phase 1, you’ll carry 1000 and have 1000, so you can carry out 2 remaining phases. ACK! What the hell? I just thought of something, redid my solution, and… there are 2 ways to come up with the same solution? ARGHH!!! Okay, I have a solution based on my first 3 theorems and their corollaries, and I have another solution based on the Starting Point Theorem. Why was my first solution so convoluted? Unless I made a mistake with my easy solution… lemme check… WHOA. My 2nd solution is so much easier and makes so much sense. So forget the Starting Point Theorem for now (called the SP Theorem), and I make up theorem 4: Theorem 4: At the end of phase 1, point Y needs 3Y bananas. Remember, in Phase 2, you want to maximize X, which means you need 1000 bananas at point Y. Between now and the end of the game, how many times do you pass point Y? You pass it 3 times. First, when you go to maximize X, you pass it once, so you want Y bananas to refill to 1000; when you’re done maximizing X, you’ll have 0 bananas at point Y, so you need Y bananas to go home; and then on your final phase, you want to refill to 1000 at point Y, so you need Y bananas, by some Corollary 1, I think. Corollary 3: To do theorem 4, you need 5Y bananas. 3Y bananas to put down, Y bananas to get there, Y bananas to get back. And you don’t want to be wasteful, so: 5Y = 1000. Y = 200. X- Y = 333 by corollary 2. X = 333 + 200. X = 533. Wow, I just solved the camel/banana puzzle. Now who wants to hear my first solution?? Sure you do. As I said, it follows the SP Theorem. You can guess from the SP theorem that you’ll end up with two phases at one part; and if you only have 2000 bananas, the most you can get to the destination is 333. So oddly enough, I came up with: Start with 3000. Take 1000, move to 100, drop 800, and go home. Take another 1000, refill at 100; so there are 700 bananas left at 100; Go up to 200, drop 800, go back to 100. There are 700 bananas left there, and I’m carrying 0, so I take all 700, go back to pt200; I’m carrying 600, so I drop 400, and I eat 200 on my way home. Now I have 800+400 bananas at point 200, so I have 1200 bananas. I take the last 1000 bananas, refill at point 200; So I am carrying 1000 bananas, and I have 1000 bananas left at point 2, so I can just use SP theorem, or I’ll write it out: I travel 333 km to 533, drop 334 bananas, go back, grab the 1000 from pt 200, and by Theorem 3, I get to the destination with 533 bananas. How did I come up with that? I don’t know! |