Camels and Bananas

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

uzurpatorul
Posts: 12
Joined: Sun May 31, 2009 7:20 pm UTC

Camels and Bananas

Postby uzurpatorul » Sun May 31, 2009 7:35 pm UTC

You have 3,000 bananas and a camel which can carry at most 1,000 bananas at a time. The camel eats a banana before moving a unit. You want to transport the bananas 1,000 units. What is the maximum number of uneaten bananas that you can move 1,000 units?
Last edited by uzurpatorul on Sun May 31, 2009 11:11 pm UTC, edited 1 time in total.

silvermace
Posts: 77
Joined: Mon Apr 20, 2009 7:56 pm UTC

Re: Camels and Banans

Postby silvermace » Sun May 31, 2009 9:27 pm UTC

can you drop the bananas like half way? and go back for the rest? like take 1000, walk 2 units, drop, go back for another 1000 ect?

EricSeverson
Posts: 13
Joined: Sun May 31, 2009 9:27 pm UTC

Re: Camels and Banans

Postby EricSeverson » Sun May 31, 2009 9:37 pm UTC

assuming that you can drop the bananas and come back like silvermace said, i think i have solved it:
Spoiler:
833 bananas
At first what you have to do is take three trips for every one unit you move. So for every one unit the bananas travel, you lose 3 bananas.
As long as you have over 2000 bananas to move, you must keep taking three trips because you can only move 1000 at a time.
This keeps going until you have moved 334 units, and then have 3000 - 3*334 = 1998 bananas left.
From here on you only have to take two trips for each unit moved, so you lose 2 bananas for each unit.
This keeps going until you have moved 334 + 499 = 833 units, when you will have 1998 - 2*499 = 1000 bananas left.
Now you are only taking one trip per unit traveled, and you have 1000 - 833 = 167 units left to travel.
The camel will eat 167 more bananas, leaving you with a total of 1000 - 167 = 833 bananas left.

uzurpatorul
Posts: 12
Joined: Sun May 31, 2009 7:20 pm UTC

Re: Camels and Bananas

Postby uzurpatorul » Sun May 31, 2009 11:10 pm UTC

You can create "refueling" station along the path, like take 1000 bananas, move 250 unites, leave 500 bananas and go back for more

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: Camels and Banans

Postby GreedyAlgorithm » Mon Jun 01, 2009 3:21 am UTC

EricSeverson wrote:assuming that you can drop the bananas and come back like silvermace said, i think i have solved it:
Spoiler:
833 bananas
At first what you have to do is take three trips for every one unit you move. So for every one unit the bananas travel, you lose 3 bananas.
As long as you have over 2000 bananas to move, you must keep taking three trips because you can only move 1000 at a time.
This keeps going until you have moved 334 units, and then have 3000 - 3*334 = 1998 bananas left.
From here on you only have to take two trips for each unit moved, so you lose 2 bananas for each unit.
This keeps going until you have moved 334 + 499 = 833 units, when you will have 1998 - 2*499 = 1000 bananas left.
Now you are only taking one trip per unit traveled, and you have 1000 - 833 = 167 units left to travel.
The camel will eat 167 more bananas, leaving you with a total of 1000 - 167 = 833 bananas left.

You have forgotten the fact that the camel does not move backwards for free.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Poohblah
Posts: 53
Joined: Thu Feb 26, 2009 3:54 am UTC

Re: Camels and Bananas

Postby Poohblah » Mon Jun 01, 2009 4:37 am UTC

Spoiler:
my first thought is to take 1,000 bananas 500 units, since any farther than that and the camel couldn't go back. Then the camel goes back and gets 1,000 more bananas. This would be repeated 3 times and the camel would be out of fuel. So that doesn't work; the camel never gets past halfway.

How about the other extreme? the camel walks 1 unit and drops off 998 bananas, then goes back and gets 1000 more. Then there would be 2994 bananas at the 1 unit mark. This means that the cost of transporting the bananas is 6 bananas per unit until the number of bananas is less than 2,000 at the 167 unit mark, when there are 1998 bananas left. Then the cost of transporting bananas is 4 bananas per unit for the next 250 units, when there are 998 bananas left at the 417 unit mark. Then the cost to transport bananas is 1 banana per unit, and the camel can transport the rest of the bananas to the end and there will be 415 left.

If we assume that the camel can move and consume fractions of bananas instead of only whole units, then the number is slightly higher.


edit: I think I got it wrong the first time around :) .
Last edited by Poohblah on Mon Jun 01, 2009 5:02 am UTC, edited 2 times in total.

EricSeverson
Posts: 13
Joined: Sun May 31, 2009 9:27 pm UTC

Re: Camels and Bananas

Postby EricSeverson » Mon Jun 01, 2009 4:57 am UTC

Greedy you are right. I thought the camel just ate a banana as a result of carrying it, but its more like the bananas are the fuel that makes the camel move.
Anyhow, I still use the same method and I got to what should be the correct answer.
Spoiler:
415 bananas. Pooblah you didn't consider that as you lose more bananas you will not have to make as many return trips.
So at first when you are taking three trips, it takes you 6 bananas for every unit you move because you are going there and back 3 times.
Then after 167 units, you have 3000 - 167*6 = 1998 bananas left, so from then on you take two trips, losing 4 bananas per unit traveled.
After 250 more units traveled, you have 1998 - 250*4 = 998 bananas left. You have 1000 - 167 - 250 = 583 more units to travel, but since the camel can now carry all the remaining bananas at once, it will only eat 583 more bananas, leaving you with 998 - 583 = 415 bananas left.
Last edited by EricSeverson on Mon Jun 01, 2009 4:59 am UTC, edited 1 time in total.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Camels and Bananas

Postby lordatog » Mon Jun 01, 2009 4:58 am UTC

I
Spoiler:
t seems to me that it is most efficient to leave a cache of n bananas at unit marker n, for as large an n as possible. So, here's my first go.

Pick up 1000 bananas.
Go forward 333 units, drop off 334 bananas, go back 333 units.
Pick up 1000 bananas.
Go forward 333 units, pick up 333 bananas, go forward 111 units, drop 445 bananas, go back 444 units.
Pick up 1000 bananas.
Go forward 444 units, pick up 444 bananas, go forward 556 units. You arrive with 444 uneaten bananas (and two abandoned along the way).

Is this optimal? I doubt it. It's better than nothing, though.

Poohblah
Posts: 53
Joined: Thu Feb 26, 2009 3:54 am UTC

Re: Camels and Bananas

Postby Poohblah » Mon Jun 01, 2009 5:01 am UTC

EricSeverson wrote:
Spoiler:
415 bananas. Pooblah you didn't consider that as you lose more bananas you will not have to make as many return trips.


I just realized that after I posted. fixed and now I have the same answer as you :)

Seems that lordatog has a better answer though.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Camels and Bananas

Postby jestingrabbit » Mon Jun 01, 2009 5:17 am UTC

I'm pretty sure that we've done something very like this before, but my searching isn't up to scratch today. Anyway,

Spoiler:
Take 1000 bananas, go forward 200 units, drop 600, go back to base.

Take 1000 bananas, go forward 200 units, pick up 200 bananas, go forward a further 333 1/3 units, drop 333 1/3 bananas, go back 333 1/3, pick up 200, go back to base.

Take 1000, go forward 200, pick up 200, go forward 333 1/3, pick up 333 1/3, and continue till you hit the end. You'll have 533 1/3 bananas at the end.


Note that I've assumed the existence of fractional bananas.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

aduubian
Posts: 25
Joined: Thu Apr 16, 2009 10:32 pm UTC

Re: Camels and Bananas

Postby aduubian » Mon Jun 01, 2009 3:00 pm UTC

EricSeverson wrote:it takes you 6 bananas for every unit you move because you are going there and back 3 times.

no. It takes you five bananas for every unit because you are going forward three times, but only back twice. If you go back a third time, you end up where you started and you would have to go forward again (requiring an additional banana, to make 7) but you don't need to do that because you already moved all of the bananas one unit.
once you have less than 2000 bananas it will only take 3 to move them all (up, back, up)
you must always make an odd number of moves or you will end up back where you started.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Camels and Bananas

Postby Cosmologicon » Tue Jun 02, 2009 3:28 am UTC

So, assuming fractional bananas can be consumed, the farthest the camel can travel, starting with 3000 bananas, is:
Spoiler:
1533 1/3 units
Approximately (to the nearest 1000 is fine) how many bananas does the camel need to start with in order to travel 4000 units? The camel doesn't need to have any bananas left over.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Camels and Bananas

Postby skeptical scientist » Tue Jun 02, 2009 4:04 am UTC

Spoiler:
Starting with n*1000 bananas, the camel can travel exactly 1000 units times 1+1/3+1/5+1/7+1/9+...+1/(2n-1). This sum is approximately ln(2n)/2, so in order to travel 4000 units, the camel must consume approximately 1.5 million bananas*.

*This is a nice back of the envelope calculation, but to get it to the nearest 1000, I'd need to use a better estimator for the sum.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

EricSeverson
Posts: 13
Joined: Sun May 31, 2009 9:27 pm UTC

Re: Camels and Bananas

Postby EricSeverson » Tue Jun 02, 2009 5:54 am UTC

aduubian pointed out yet another flaw with the numbers i was crunching...
Spoiler:
but the good thing is that now that i've realized thats its taking 5, 3, then 1 banana per unit I end up getting to 533 1/3 bananas using my method, the same thing that jestingrabbit got
so it doesn't matter if you strategically place large groups of bananas at certain spots or if you just go back and forth to bring the whole stack one unit at a time (like I did).
either way you get to the same answer, 533 1/3, so i'm pretty sure that this is the best possible answer

or if we do not consider that you can use fractional bananas, you will only end up with 532 bananas.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5963
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Camels and Bananas

Postby jestingrabbit » Tue Jun 02, 2009 6:42 am UTC

Okay, question that I do not know the answer to.

Same situation: the destert is 1000 units of distance to cross, there is one camel and it takes 1 banana to travel one unit of distance (I assume that the camel is skating on the skins of the bananas as I'm pretty sure they don't eat them (banana=jungle, camel=desert)), furthermore it takes the camel 1 day to travel 1000 units of distance, and the side that the camel starts on has an infinite supply of bananas.

What is the best way to transport bananas across the desert? Here, best is measured as bananas that are left on the far side of the desert per day.

So, for instance, the solution that we have now is such that it takes 2 7/15 days to travel the distance, and 533 1/3 bananas are delivered, so it has a rate of 8000/37 bananas per day when it arrives on the far side of the desert. But it can't get back, so its rate of bananas delivered per day slowly drops to 0 ie this sucks for the long term banana trade.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

GreedyAlgorithm
Posts: 286
Joined: Tue Aug 22, 2006 10:35 pm UTC
Contact:

Re: Camels and Bananas

Postby GreedyAlgorithm » Tue Jun 02, 2009 8:53 am UTC

Spoiler:
A 4-camel in a 4-desert can get 2 bananas to the other side and come back, leaving an empty desert, as follows:
A(2/4): 4 bananas distance 1, drop 2 off, return. This deposits 2 bananas at distance 1.
B(6/4): A, then bring 4 for 1 unit, grab a new banana, go another unit, drop off 2, return 1, get a banana, return home. This deposits 2 bananas at distance 2 and consumes 2 at distance 1.
C(16/4): A, B, A, then bring 4 out to distance 3 while refueling 1 banana at a time, drop off 2, come back. Deposit 2 at 3, consume 2 at 1 and 2.
D(44/4): A,B,A,C,A,B,A, woot! deposit 2 bananas in the usual fashion at distance 4, eat all the bananas in the middle of the desert on the way back.

That's 11 days for 2 bananas, or 2/11 bananas per day, sustainable. And it scales directly to a 1000-camel in a 1000-desert.
GENERATION 1-i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: Camels and Bananas

Postby Yat » Tue Jun 02, 2009 10:44 am UTC

I was too lazy to verify your day count or to look for the differences between your method and mine, but I get a better ratio.
Spoiler:
First, you take 15/4 days to bring 8 load of 4 bananas at distance 1. The camel is then at distance 1 with 17 bananas. Leave one there, and now take 7/4 days to bring 4 loads of 4 bananas at distance 2. That leaves us at distance 2 with 9 bananas. Leave one there, take 3/4 days to bring 2 loads of 2 bananas at distance 3, leave one there. Now just take one load to distance 4, this takes 1/4 day. You can leave 2 bananas there, and get back to distance 3 with the last banana, where you will find the one you left there earlier, etc... that makes 1 day to come back to the starting point while eating the bananas which were left on the way.


That's 7.5 days for 2 bananas.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3035
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Camels and Bananas

Postby Qaanol » Tue Jun 02, 2009 3:10 pm UTC

EricSeverson wrote:aduubian pointed out yet another flaw with the numbers i was crunching...
Spoiler:
but the good thing is that now that i've realized thats its taking 5, 3, then 1 banana per unit I end up getting to 533 1/3 bananas using my method, the same thing that jestingrabbit got
so it doesn't matter if you strategically place large groups of bananas at certain spots or if you just go back and forth to bring the whole stack one unit at a time (like I did).
either way you get to the same answer, 533 1/3, so i'm pretty sure that this is the best possible answer

or if we do not consider that you can use fractional bananas, you will only end up with 532 bananas.

I confirm this reasoning is optimal. However, if fractional bananas are not allowed, I have a method that gets one more banana moved 1000 places than you claim to. Basically, it's leap-frog.

Spoiler:
Start with 3000 on square zero. Asterisk is camel location: (3000*, 0, 0, ...)
Pick up 1000, go forward to square one, drop 998, go back to square zero. (2000*, 998, 0, ...)
Pick up 1000, go foward to square one, pick up one banana, go forward to square two. (1000, 997, 999*, 0, ...)
Drop 998, go back to square one, pick up one, go back to square zero. (1000*, 996, 998, 0, ...)
Pick up 1000, go forward to square one, pick up one, go forward to square two, pick up one, go forward to square three. (0, 995, 997, 999*, 0, ...)
Drop 998, go back to square two, pick one up, go back to square one. (0, 995*, 996, 998, 0, ...)
Pick up 995, go forward, pick up six, go forward, pick up one, go forward. (0, 0, 990, 997, 999*, 0, ...)
Drop 998, go back, pick up one, go back. (0, 0, 990*, 996, 998, 0, ...)

Clearly we're in a repeating leapfrog system, with 5 bananas consumed to advance one square. When we're in square k, the situation looks like (..., 0, 1000 - k/5*, 996, 998, 0, ...). This will continue until k = 199, when the situation will be (..., 0, 5*, 996, 998, 0, ...). Then,

Pick up 5, go forward, pick up 996, go forward, pick up 1, go forward. (..., 0, 0, 0, 997, 999*, 0, ...) The 200th square is underlined.
Drop 998, go back, pick up 997. (..., 0, 997*, 998, 0, ...)
Go forward, pick up four, go forward. (..., 0, 994, 999*, 0, ...)
Drop 998, go back. (..., 0, 994*, 998, 0, ...)

This is also clearly a repeating leapfrog, where the number of bananas in the left square decreases by 3 each time the system moves one square to the right. Indeed, we see that square 200+m will have [imath]1000-3m[/im] bananas, and the square after it will have 998. This continues until we reach square 532, where m = 332, so we have (..., 4*, 998, 0, ...). Then,

Pick up 4, go forward, pick up 997, go forward. (..., 0, 1, 999*, 0, ...) The 533rd square is underlined.
Go forward. (..., 0, 1, 0, 998*, 0, ...)

Clearly we are now just walking. When we are in square 533 + p we will have 1000 - p bananas. So when we reach square 1000, where p = 467, we will have 533 bananas. Since we started at square zero, this is a total distance traveled of 1000 units. There is one banana left in the desert.

Answer: 533
wee free kings

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Camels and Bananas

Postby skeptical scientist » Tue Jun 02, 2009 4:27 pm UTC

GreedyAlgorithm wrote:
Spoiler:
A 4-camel in a 4-desert can get 2 bananas to the other side and come back, leaving an empty desert, as follows:
A(2/4): 4 bananas distance 1, drop 2 off, return. This deposits 2 bananas at distance 1.
B(6/4): A, then bring 4 for 1 unit, grab a new banana, go another unit, drop off 2, return 1, get a banana, return home. This deposits 2 bananas at distance 2 and consumes 2 at distance 1.
C(16/4): A, B, A, then bring 4 out to distance 3 while refueling 1 banana at a time, drop off 2, come back. Deposit 2 at 3, consume 2 at 1 and 2.
D(44/4): A,B,A,C,A,B,A, woot! deposit 2 bananas in the usual fashion at distance 4, eat all the bananas in the middle of the desert on the way back.

That's 11 days for 2 bananas, or 2/11 bananas per day, sustainable. And it scales directly to a 1000-camel in a 1000-desert.

You are miscounting. B already includes A, so to do C, you need only do B, then A, then go to distance 3, for a total of 6+2+6=14 units of distance traveled. When you do D, you need only do C, then B, then A, then go to distance 4, for a total of 14+6+2+8=30 units of distance traveled, taking 7.5 days, which is exactly the same as yat's.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Yat
Posts: 120
Joined: Tue Feb 03, 2009 2:05 pm UTC

Re: Camels and Bananas

Postby Yat » Tue Jun 02, 2009 5:15 pm UTC

Yes I suspected both solutions were the same, only in a different order.

Now, for 1000, if I apply the same method...

Spoiler:
First, the camel brings 1000999 bananas cargos at kilometer 1, using each time one banana to go and one to come back, except the last time where it does not come back. That leaves it after 1000998 days at kilometer 1, with 998*1000999+1 bananas.

Then it leaves one banana behind and brings 998*1000998 cargos at kilometer 2, and finds itself after another 998*1000997days at kilometer 2 with 9982*1000998+1 bananas.

Time for generalisation, for now it founds itself at kilometer n with 998n*10001000-n+1 bananas, leaves one behind, which allow it to bring 998n*10001000-(n+1) cargos at kilometer n+1, where it finds himself with a total of 998n+1*10001000-(n+1)+1 bananas. Recursion works.

We can conclude it will finally arrive at kilometer 999 with 998999*1000+1 bananas, will leave one behond for later, and bring 998999 cargos of bananas to its destination. When it is there with 9981000+1 bananas, it takes one back and returns to its starting point, taking on its way the bananas it has left at every kilometer.

So, we have 10001000 leaving the starting point, 9981000 getting to the destination, the rest being eaten in the way. The duration of this travel is (10001000-9981000)/1000.
The global speed of the process, in bananas per day is 1000*9981000/(10001000-9981000)

Ok, now I don't know how to calculate this, but as I also solved the thing with non integer bananas quantity, this should be close to e-2/(1-e-2)

AvalonXQ
Posts: 747
Joined: Mon Feb 18, 2008 5:45 pm UTC

Re: Camels and Bananas

Postby AvalonXQ » Tue Jun 02, 2009 5:34 pm UTC

Yat wrote:Time for generalisation, for now it founds itself at kilometer n with 998n*10001000-n+1 bananas, leaves one behind, which allow it to bring 998n*10001000-(n+1) cargos at kilometer n+1, where it finds himself with a total of 998n+1*10001000-(n+1)+1 bananas. Recursion: it works, bitches!


Fix'd.

User avatar
Moonbeam
Posts: 278
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

Re: Camels and Bananas

Postby Moonbeam » Tue Jun 02, 2009 8:54 pm UTC

For the original question (assuming whole numbers of bananas only):

Spoiler:
It doesn't matter if you transport the bananas one unit at a time, or more, but the first crucial point is at 200 units, so:
pick up 1000 bananas, travel 200 units, drop 600 bananas and return to start.
Pick up another 1000 bananas, travel 200 units, drop 600 bananas and return to start.
Pick up remaining 1000 bananas and travel 200 units.

You are now at the 200 unit mark with 2000 bananas.

Next, pick up 1000 bananas and travel 333 units (NOT 334), drop 334 bananas and return to 200 unit mark.
Pick up remaining 1000 bananas and travel 333 units.

You are now at the 533 unit mark with 1001 bananas.

Pick up 1000 bananas leaving 1 banana behind and travel the remaining 467 units - ending up at the 1000 unit mark with 1000 - 467= 533 bananas.

People are losing 1 banana by moving that extra unit to 534 - but it costs 3 bananas to save 1 banana, effectively losing you 2 bananas. My solution has to leave 1 banana behind - making mine more efficient by 1 banana (same as Qaanol's solution).



If fractions are allowed, then I think that Jestingrabbit's solution is optimal :shock: .

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Re: Camels and Bananas

Postby Strilanc » Wed Jun 03, 2009 12:09 pm UTC

Spoiler:
The important thing to notice is that there is no efficiency gained by using 1 refueling station at 250 instead of 250 stations from 1 to 250. In either case you must enter each cell twice per thousand bananas, except for the last thousand which only requires on pass.

Therefore the number of bananas goes down by 5 per unit traveled, until you have at most 2000 bananas at which point it goes down by 3 per unit traveled until you have at most 1000 bananas at which point it goes down by 1 per unit traveled. There is a bit of a special case if you end up with 1 (mod 1000) bananas, because it's not worth your while to go back for that last trip.

c = banana capacity = 1000
b(d) = banana count at distance d
b(0) = 3000
db(n) = -2 * floor(b(n-1) / c) + (b(n-1) mod c == 1 ? -1 : 1)
b(n) = b(n-1) + db(n) + (b(n-1) mod c == 1 ? -1 : 0)

What we think of as the 'checkpoints' end up being the discontinuities in db(n).

So db(0) = 5, it takes 200 steps before db changes; db(200) = 3, then it takes 333 steps until db(n) changes to 1; db(533) = 1, then there are 467 steps until the finish line, leaving us with 533 bananas.
Don't pay attention to this signature, it's contradictory.

Avin
Posts: 91
Joined: Sun Nov 25, 2007 3:08 am UTC

Re: Camels and Bananas

Postby Avin » Thu Jun 04, 2009 8:49 pm UTC

Moonbeam wrote:For the original question (assuming whole numbers of bananas only):

Spoiler:
It doesn't matter if you transport the bananas one unit at a time, or more, but the first crucial point is at 200 units, so:
pick up 1000 bananas, travel 200 units, drop 600 bananas and return to start.
Pick up another 1000 bananas, travel 200 units, drop 600 bananas and return to start.
Pick up remaining 1000 bananas and travel 200 units.

You are now at the 200 unit mark with 2000 bananas.

Next, pick up 1000 bananas and travel 333 units (NOT 334), drop 334 bananas and return to 200 unit mark.
Pick up remaining 1000 bananas and travel 333 units.

You are now at the 533 unit mark with 1001 bananas.

Pick up 1000 bananas leaving 1 banana behind and travel the remaining 467 units - ending up at the 1000 unit mark with 1000 - 467= 533 bananas.

People are losing 1 banana by moving that extra unit to 534 - but it costs 3 bananas to save 1 banana, effectively losing you 2 bananas. My solution has to leave 1 banana behind - making mine more efficient by 1 banana (same as Qaanol's solution).



If fractions are allowed, then I think that Jestingrabbit's solution is optimal :shock: .


I think you can do it with one more banana, if we assume units and bananas are discrete.

Spoiler:
Given that the camel eats a banana IN ORDER to move one unit, when you are at the 533 unit mark, then the camel loads up 1000 bananas and eats the 1001st banana in order to move a unit.

Then you are at the 534 unit mark with 1000 bananas.


Oh, and for the 4000 unit question,

skeptical scientist wrote:
Spoiler:
Starting with n*1000 bananas, the camel can travel exactly 1000 units times 1+1/3+1/5+1/7+1/9+...+1/(2n-1). This sum is approximately ln(2n)/2, so in order to travel 4000 units, the camel must consume approximately 1.5 million bananas*.

*This is a nice back of the envelope calculation, but to get it to the nearest 1000, I'd need to use a better estimator for the sum.


Spoiler:
Your approximation is way off, because it looks like it wouldn't even be 480k bananas:

http://www48.wolframalpha.com/input/?i=sum+from+n%3D1+to+480+of+(1%2F(2n-1))

Trevortni
Posts: 7
Joined: Thu Jun 04, 2009 8:27 pm UTC

Re: Camels and Bananas

Postby Trevortni » Thu Jun 04, 2009 10:57 pm UTC

OK, this is going to take shape as I type it, because I haven't worked out the math yet, and working it out while typing will probably be easiest.

Spoiler:
What if, instead of forcing the camel to eat the camels out of his load, we leave bananas at every mile mark? (I don't want to call the distance a "unit" because then I get confused as to whether I'm talking about bananas or distance).

Then we have:
  • Load 1000
    Walk 200 miles, eating 1 banana and leaving 4 bananas at every mile marker.
    No bananas to drop off.
    Walk back, consuming 1 banana at each mile marker (3 remaining).
  • Load 1000
    Walk 200 miles, consuming 1 banana at each mile marker (2 remaining).
    Walk 333 miles, consuming 1 banana and leaving 2 bananas at every mile marker.
    Drop off 1 banana (Woo-hoo!).
    Walk all the way back, consuming 1 banana at each mile marker (1 remaining, both sections).
  • Load 1000
    Walk 533 miles, consuming 1 banana from each mile marker (and clearing out the caches).
    Eat the 1 extra banana yourself; why should your camel get their yummy goodness all to himself?
    Walk 467 miles, consuming 1 banana from the pack at every mile.
  • Deliver 533 bananas.

Okay, so I didn't get any better than the existing optimal solution (not that I was expecting to), but could there be any benefit or further optimizations using this or a derivative approach? The task of daily deliveries especially comes to mind in posing this suggestion.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Camels and Bananas

Postby skeptical scientist » Fri Jun 05, 2009 1:44 am UTC

Avin wrote:
skeptical scientist wrote:
Spoiler:
Starting with n*1000 bananas, the camel can travel exactly 1000 units times 1+1/3+1/5+1/7+1/9+...+1/(2n-1). This sum is approximately ln(2n)/2, so in order to travel 4000 units, the camel must consume approximately 1.5 million bananas*.

*This is a nice back of the envelope calculation, but to get it to the nearest 1000, I'd need to use a better estimator for the sum.


Spoiler:
Your approximation is way off, because it looks like it wouldn't even be 480k bananas:

http://www48.wolframalpha.com/input/?i=sum+from+n%3D1+to+480+of+(1%2F(2n-1))

That's a good point. The euler constant is pretty big relative to 4, as is ln(2), so both make significant contributions here. A better estimate could be gotten from 1+1/3+1/5+1/7+1/9+...+1/(2n-1)=H2n-1-Hn-1/2≈γ+ln 2n-(γ+ln n)/2≈γ/2+ln 2+(ln n)/2. Solving for n, we get n≈e8-γ-2ln 2≈418.4, so we need about 419,000 bananas.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Re: Camels and Bananas

Postby Strilanc » Fri Jun 05, 2009 5:47 pm UTC

You can do 4000 with
Spoiler:
421236 bananas

VB6: (note: \ is truncation integer division)

Code: Select all

Private Function MoveDistance(ByVal d As Long, Optional ByVal c As Long = 1000)
    Dim b As Long
    Dim db As Long
    While d > 0
        db = 2 * ((b + db) \ c) + 1 'un-eaten
        b = b + db
        d = d - 1
    Wend
    MoveDistance = b
End Function
Private Function MoveBananas(ByVal d As Long, ByVal b As Long, Optional ByVal c As Long = 1000) As Long
    While d > 0
        Dim db As Long
        db = 2 * ((b - 2) \ c) + 1 'eaten
        If b Mod c = 1 And db <> 1 Then
            db = db + 1 'left behind
        End If
        b = b - db
        d = d - 1
    Wend
    MoveBananas = b
End Function
Don't pay attention to this signature, it's contradictory.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3035
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Camels and Bananas

Postby Qaanol » Fri Jun 05, 2009 7:45 pm UTC

Avin wrote:I think you can do it with one more banana, if we assume units and bananas are discrete.

Spoiler:
Given that the camel eats a banana IN ORDER to move one unit, when you are at the 533 unit mark, then the camel loads up 1000 bananas and eats the 1001st banana in order to move a unit.

Then you are at the 534 unit mark with 1000 bananas.

Yes, and if we make the assumption that the camel can eat multiple bananas ahead of time, storing the energy as camels are wont to do, we can easily get a thousand bananas across the desert in one go.
wee free kings


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests