85
$\begingroup$

A somewhat well-known puzzle is described as such:

You have a pile of 3,000 bananas. You wish to transport them to a place 1,000 miles away on the back of a camel; however, the camel can only carry a maximum of 1,000 bananas, and will eat one banana every mile it travels (and will not go anywhere if it does not have any bananas). However, you can load and unload as many bananas as you want anywhere. What is the most bananas you can bring over to your destination?

Obviously you can't just load up 1,000 bananas and go, because the camel will have eaten them all by the time you get there.

I'd never figured out the answer by myself before. Does anybody have any insights into how to solve this problem and other problems like it?

$\endgroup$
12
  • 3
    $\begingroup$ The camel can only carry 1,000 bananas at once. $\endgroup$
    – user88
    May 19, 2014 at 2:29
  • 11
    $\begingroup$ You can't add 1 banana when you're a mile away from the pile. $\endgroup$
    – user88
    May 19, 2014 at 2:33
  • 2
    $\begingroup$ Does it have to be the same camel the entire time? $\endgroup$
    – igelkott
    May 19, 2014 at 10:59
  • 3
    $\begingroup$ Usually the camel eats the banana at the end of a mile, but you can even assume the camel eats bananas continuously. $\endgroup$
    – user88
    Nov 26, 2014 at 16:21
  • 3
    $\begingroup$ Cross-site duplicate. To be fair, I bet there's a lot of crossover with Math. $\endgroup$ Jun 29, 2015 at 21:52

16 Answers 16

46
$\begingroup$

Solution for $n$ bananas, where $n$ is the number of bananas you own, and $c$ is the number of bananas the camel can carry:

- For bananas $0 \rightarrow c$ the cost to move a banana is $1$ banana per mile.
- For bananas $c+1 \rightarrow 2c$, the cost to move a banana is $3$ bananas per mile.
- For bananas $2c+1 \rightarrow 3c$, the cost to move a banana is $5$ bananas per mile.
- etc.

This is because, if the camel moves the bananas 1 mile at a time, he needs to make two trips for each load beyond his current capacity.

Define $t = \lfloor\frac{n}{c}\rfloor$ Therefore, the total number of miles the camel can reach is:

$$\left(\sum_{k=1}^{t} \frac{c}{2k - 1}\right) + \frac{(n \bmod c)}{2t+1}$$

In particular, plugging in the given $n = 3000$ and $c = 1000$, we have that the camel can travel

$$1000 + 333 + 200 = 1533 \text{ miles}$$

To figure out how many bananas remain for a given distance,

Subtract the extra miles and multiply back at the rate given above.

For the first $1000$ miles, this number is just the distance beyond the total capacity:

$1533 - 1000 = 533$, or 533 bananas.

$\endgroup$
5
  • $\begingroup$ If we reformulate the question as How many bananas do we need at the start if we must get X bananas to the finish line, will the answer converge to the rocket fuel equation for increasing X and distance? Not sure if it will, but the same principle is at work here I think. Increasing the amount X by a bit will cause the original amount of bananas to increase significantly... $\endgroup$ Nov 27, 2014 at 11:37
  • 6
    $\begingroup$ Divide the total answer by 1.609 to convert km to mi. :-) $\endgroup$
    – jvriesem
    Nov 6, 2016 at 17:01
  • 2
    $\begingroup$ None of the answers here give a proof for optimality. That is really disturbing. $\endgroup$ Mar 19, 2020 at 18:41
  • 1
    $\begingroup$ @SiddharthJoshi: Here is the optimality proof on another StackExchange site: math.stackexchange.com/a/96012/92861 $\endgroup$
    – justhalf
    Jun 14, 2020 at 3:52
  • 4
    $\begingroup$ @user1429080 Camels and bananas aren't exactly rocket science. $\endgroup$
    – Florian F
    Jun 29, 2020 at 21:14
41
+100
$\begingroup$

First of all, the brute-force approach does not work. If the Camel starts by picking up the 1000 bananas and try to reach point B, then he will eat up all the 1000 bananas on the way and there will be no bananas left for him to return to point A.

So we have to take an approach that the Camel drops the bananas in between and then returns to point A to pick up bananas again.

<---p1---><--------p2-----><-----p3---->
A---------------------------------------->B
-----> ------> -------->
<----- <------
-----> ------>
<-----
----->

Since there are 3000 bananas and the Camel can only carry 1000 bananas, he will have to make 3 trips to carry them all to any point in between.

When bananas are reduced to 2000 then the Camel can shift them to another point in 2 trips and when the number of bananas left are <= 1000, then he should not return and only move forward.

In the first part, P1, to shift the bananas by 1Km, the Camel will have to

  1. Move forward with 1000 bananas – Will eat up 1 banana in the way forward
  2. Leave 998 banana after 1 km and return with 1 banana – will eat up 1 banana in the way back
  3. Pick up the next 1000 bananas and move forward – Will eat up 1 banana in the way forward
  4. Leave 998 banana after 1 km and return with 1 banana - will eat up 1 banana in the way back
  5. Will carry the last 1000 bananas from point a and move forward – will eat up 1 banana

Note: After point 5 the Camel does not need to return to point A again.

So to shift 3000 bananas by 1km, the Camel will eat up 5 bananas.

After moving to 200 km the Camel would have eaten up 1000 bananas and is now left with 2000 bananas.

Hence the length of part P1 is 200 Km.

Now in the Part P2, the Camel needs to do the following to shift the Bananas by 1km.

  1. Move forward with 1000 bananas - Will eat up 1 banana in the way forward
  2. Leave 998 banana after 1 km and return with 1 banana - will eat up this 1 banana in the way back
  3. Pick up the next 1000 bananas and move forward - Will eat up 1 banana in the way forward

Note: After point 3 the Camel does not need to return to the starting point of P2.

So to shift 2000 bananas by 1km, the Camel will eat up 3 bananas.

After moving to 333 km the camel would have eaten up 1000 bananas and is now left with the last 1000 bananas.

Because it is a multiple of 3, after 333 times there is 1001 bananas left. Therefore, the camel must take 1000 bananas and then take 1 back with him to pick up the last banana, leaving him with 999 bananas. This would leave the camel at 334 km + 200 km, so the merchant only needs to travel 466 km, eating 1 banana for every km.

999 bananas - 466 bananas for each remaining km equals 533 bananas left at point B. Therefore, the merchant has 533 bananas to sell at point B.

$\endgroup$
5
  • 8
    $\begingroup$ I like the shift from miles to Km. $\endgroup$
    – Shade
    May 28, 2014 at 0:21
  • 6
    $\begingroup$ I believe you have the correct answer, but you should be careful about ignoring the decimal part of 333.33. In this case the cost of carrying the bananas that extra km from 333 to 334 (costing 3 bananas) is higher than abandoning a single banana at 333 and moving forward (costing two bananas) with the final 1000. $\endgroup$
    – Jason
    May 28, 2014 at 4:53
  • 1
    $\begingroup$ Agree with Jason, the result is correct, but the reasoning in ignoring .33 is not entirely correct. It should have been what Jason said, you abandon one banana after 333km. $\endgroup$
    – justhalf
    Jul 3, 2014 at 5:26
  • $\begingroup$ But how did you figure out that the first drop point is 200 Kms away ? $\endgroup$ Jan 26, 2021 at 4:29
  • 1
    $\begingroup$ 1000 Km / 5 banana per km = 200 km $\endgroup$
    – matt2000
    May 7, 2021 at 17:11
19
$\begingroup$

While the amount of bananas is larger than 2000, the camel will have to make 5 trips to shift them. At a cost of 1 banana per mile, this will cost 5 bananas per mile in total.
While the amount of bananas is larger than 1000, it takes 3 trips to shift them, so a total cost of 3 bananas per mile.
For the final stretch, it just takes a single banana per mile.

  1. 3000 - 2000 bananas (numbers given for first mile)
    1. Move 1000 bananas, feed 1, 2999 left.
    2. Go back, feed 1, 2998 left.
    3. Move 1000 bananas, feed 1, 2997 left.
    4. Go back, feed 1, 2996 left.
    5. Move 998 bananas, feed 1, 2995 left.
  2. 2000 - 1000 bananas (numbers given for first mile)
    1. Move 1000 bananas, feed 1, 1999 left.
    2. Go back, feed 1, 1998 left.
    3. Move 999 bananas, feed 1, 1997 left.
  3. 1000 bananas (numbers given for first mile)
    1. Move 1000 bananas, feed 1, 999 left.

So at 5 bananas/mile you're down to 2000 bananas after 200 miles. Your total mileage then improves to 3 bananas/mile for the next 333 miles. After that, you're on the home stretch and move at 1 banana/mile for the remaining 467 miles (after which you'll have 533 bananas left).

A few things to note:

  • It is not necessary to move in one mile increments. For the first stretch, you can load up with 1000 bananas, move 200 miles, unload 600, and use 200 for your return trip. You do the same thing again, and after the last trip, you can unload 800, or rather, load 200 to be at a full 1000 again.
  • After completing the 333 mile stretch, you're 467 miles away from your destination, with exactly 1001 bananas. There are now two solutions:
    1. Eat a banana (or leave it to rot) to have a nice, integer solution.
    2. Use it to move for a total of 333⅓ miles. If the camel needs to be fed after walking a full mile, you will now make it to your destination with ⅓ of a mile to spare, which should save you a banana, leaving you with 534 bananas.
      Congratulations, you're now banana king!
$\endgroup$
5
  • 6
    $\begingroup$ You are the banana king! $\endgroup$
    – JeffE
    May 28, 2014 at 4:13
  • 6
    $\begingroup$ You won't feed a starving camel at the end of a long trip? Shame on you! $\endgroup$
    – Neil
    Jul 4, 2014 at 13:04
  • 8
    $\begingroup$ He's not starving, he still has 1/3 banana left in him! Also, check the map for where camels live and where bananas grow. Pretty much non-overlapping. It's fictional! They are lying to us! It's a conspiracy! $\endgroup$
    – SQB
    Jul 4, 2014 at 13:21
  • 9
    $\begingroup$ @Neil He just got fed 2466.66 bananas, I'm sure he'll manage. $\endgroup$
    – Damien H
    Nov 27, 2014 at 4:19
  • $\begingroup$ "When bananas are reduced to 2000 then the Camel can shift them to another point in 2 trips." But what is the proof that for optimality, the camel should drop 2000 at the first point ? Maybe the first drop point is even further and the camel drops a total of 1600 bananas there. $\endgroup$ Jan 26, 2021 at 3:06
16
$\begingroup$

First leg of the journey:

  • Load 1000,
  • Drop 4 bananas every mile for 200 miles, feeding the camel from own supply.
  • The route is primed for 4 passes of the camel:
    • return
    • take another 1000 bananas
    • return
    • take remaining 1000 bananas.

Second leg, starting with mile 200:

  • load 1000
  • drop 1 banana a mile away, then 2 bananas every next mile for another 333 miles, for 534 miles total.
  • return
  • pick 1000 bananas
  • on the first mile eat a banana from own supply, then continue using the ones left.
  • arrive at 534th mile with 999 bananas.

Third leg of the journey:

  • Feed the camel the last banana on the ground, then starting with 535th mile, keep using bananas from your supply of 999.
  • use up 465 bananas from own supply for the remaining 465 miles.

You're left with 999-465 = 534 bananas.

$\endgroup$
1
  • 2
    $\begingroup$ The first practical solution, which doesn't require 2000 times loading and unloading the camel! - good creative answer! $\endgroup$
    – Falco
    Jun 11, 2015 at 13:18
3
$\begingroup$
  1. Load up 1000 bananas. Go forward 200 miles. Drop down 600 bananas. Go backward 200 miles to start point.
  2. Load up 1000 bananas. Go forward 200 miles, here pick up 200 bananas. Go forward 333.5 miles. Drop down 333 bananas. Go backward 333.5 miles, here pick up 200 bananas. Go backward 200 miles to start point.
  3. Load up last 1000 bananas. Go forward 200 miles, here pick up last 200 bananas. Go forward 333.5 miles here pick up last 333 bananas. Go forward 466.5 miles to finish, and here drop down last 533 bananas.

You will made 7 loads, 3 unloads and 2 come backs.

$\endgroup$
3
$\begingroup$

$533.(3)$

Let's do it as follows: Last span will be $x$ miles, and final answer is $1000-x$ bananas delivered. Next to last span will be $y$ miles, we would do best if each ride starts with 1000, i.e. $2000 -3y = 1000$ should hold to get to 1000 left for the last span. Hence $y = \frac{1000}{3}$.

Now to get to 2000 from 3000 we will need 3 trips on path of length $z$, doing it optimally (starting with 1000 each trip), gets us to $3000-5z = 2000$, i.e. $z = \frac{1000}{5} = 200$.

That leaves us with $1000-x = y + z = 333.(3) +200 = 533.(3)$

$\endgroup$
2
$\begingroup$

Short and Concise solution,

The concept here is carrying 1000 bananas at once for a Km then move backward to carry remaining one in a bundle of 1000 or less. Once remaining is empty then repeat the same with next state and so on.......


Step1: 3000-(3n(for move)+2n(back move))=2000 , gives n = 200


Step2: 2000-(2n(for move)+n(back move))=1000 , gives n = 333.33

Finally,

Now you have 1000 bananas left and you have already covered 533.33 steps.


Step3: So, Number of Bananas left after covering remaining steps are= 1000-(1000-533.33) = 533.33(Answer)

$\endgroup$
2
$\begingroup$

Its pretty sure that, If the camel takes all the 1000 bananas at once to the end point,he would be left with 0 bananas at the end. So, there needs to some Intermediate Points that are in between O km and 1000 km.

So, to prove my point, Let us assume 4 points.

let's called point A------>Beginning Point point B------> End Point point Q------>First Intermediate Point point W------>Second Intermediate Point

3000 2000 1001 533
<------5X----------> <----3Y-----> <------------Z---------------------> A--------------------Q-------------W------------------------------------B

If we take 1000 bananas at once to 1km,then there will be 3 trips forward, and 2 trips backward, so , there will be a total of 5 trips.

A<----------5x---->Q so, When we take 1000 bananas, we are only left with 600 bananas and similarly for the other one, but for the last one, there will be only 1 forward trip and so, its a total of 5 trips. Let's prove that with a simple equation,

3000-5X=2000 X=200 So, Point Q is 200km away from the begining.

Now, we are only left with 2000 bananas, and taking it to W, As we are only left with 2000 bananas, we can make a maximum of 2 trips forward, and 1 trip backward.

Q<-----3Y------>W It can be understood as we have only 2000 bananas left, and the camel can take 1000 bananas a time.

Let's find the distance with the Equation, 2000-3Y=1000 So, Y=333. But as the Camel is eating 1 banana per km,so, it can't be in fraction, thus, Y=333 As we reduced the term, so, will increase 1 banana,i.e, 1000+1=1001.

Again,there will only be 1 last trip, with the remaining distance, 1000-200-333=467. So, Remaining Distance=467. And 1000-467=533

Thus, total Bananas reached at destination=533.

Answer->533

$\endgroup$
2
  • 2
    $\begingroup$ Hi, welcome to PSE. This answer is essentially the same as the older ones, why did you post it? $\endgroup$
    – melfnt
    Jul 11, 2020 at 14:35
  • $\begingroup$ Before posting mine,I just read the earlier ones, and felt the solution would have been explained in a better way, and this is the reason why I did. $\endgroup$ Jan 22, 2021 at 17:39
1
$\begingroup$

This is the best answer that does not require stopping every mile. Take

1000 bananas

go

333 1/3 miles

and drop off

666 2/3 bananas.

Go back and repeat 2 more times. Now you are on mile

333 1/3 with 2000 bananas. Take 1000 bananas and go forward 500 miles. Drop off 500 bananas.

Go back and repeat. Now you are on mile

833 1/3 with 1000 bananas. Go forward another 167 2/3 miles to reach the market with 833 1/3 bananas.

$\endgroup$
3
  • 2
    $\begingroup$ The puzzle omits a fact -- the camel is happy to go get more bananas if it has no bananas on its back. $\endgroup$
    – Martin
    Sep 7, 2016 at 4:49
  • 3
    $\begingroup$ It says right in the question statement that the camel will not go anywhere if it doesn't have any bananas. $\endgroup$
    – user88
    Sep 7, 2016 at 4:51
  • $\begingroup$ If the camel eats 333 1/3 bananas and you drop 666 2/3 there, then the camel will die on the way back. (PS: maybe happily, but still...) $\endgroup$
    – Florian F
    Jun 29, 2020 at 21:21
1
$\begingroup$

Here is my solution, where camel arrives with 500 bananas:

  1. Load 1000 bananas, travel 250 miles (point A), unload 500 bananas, use 250 remaining to go back.
  2. Load 1000 bananas, travel 250 miles to point A, load 250 bananas (so camel has 1000 bananas again, with 250 remaining at point A), travel 250 miles more (point B), unload 500 bananas, travel 250 miles to point A, load 250 there, travel back to the starting point.
  3. Load 1000 bananas, go 500 miles to point B, load 500 bananas there, arrive to the destination with 500 bananas.

Now, since the right answer is 534, the question is: where did I lose 34 bananas?

$\endgroup$
4
  • 2
    $\begingroup$ This is simply a suboptimal solution. Just because you have a solution doesn't mean that it's the best. $\endgroup$
    – boboquack
    Mar 13, 2017 at 8:24
  • $\begingroup$ I was wondering what is so suboptimal in my solution. I think it's the fact that my camel travels less loaded on average. $\endgroup$
    – beetoom
    Mar 14, 2017 at 7:37
  • $\begingroup$ Probably. In any case, look at the bridge and torch problem - where the obvious solution isn't the best. $\endgroup$
    – boboquack
    Mar 14, 2017 at 7:44
  • 1
    $\begingroup$ You're walking 250 miles on a section where you have to pass 5 times. You should shorten this to arrive at the optimal solution. But don't shorten this section too much, because then you haven't spent 1000 bananas, which means you have more than 2000 left, which means you'll have to walk another section five times as well. $\endgroup$
    – florisla
    Nov 22, 2017 at 10:54
1
$\begingroup$

The traditional text of the problem is that the camel will eat 1 banana per mile if there is banana to eat. In this case...

Assume the camel eats 1 banana at the end of 1 mile (later we will adjust that).

Start with 1000 bananas in a (big) basket.
For each mile, the camel eats 1 banana, and you drop one on the road. After 500 miles, the basket has no banana and there are 500 bananas along the road (one at each mile). With the 500th banana return to A. Fill the basket with another 1000 bananas. Feed the camel with 1 banana per mile. After 500 miles the trunk has 500 bananas, and 500 bananas remains along the road. Continue for additional 250 miles while feeding the camel 1 banana per mile and dropping 1 banana per mile on the road. At mile 750 the basket has zero bananas and 750 bananas are along the road. Return to A with the last banana left in the basket. At A, fill again the the basket with 1000 bananas. Now, feed the camel at each mile with the 750 bananas left along the road. The camel will go through 750 miles while the basked contains 1000 bananas. For the final 250 miles, feed the camel with 250 bananas and you reach B with 750 bananas in the basket. Ideally you reach B with 750 bananas.
Now back with the initial assumption (that the camel eats at the end of the mile) and change to the assumption that the camel eats 1 banana at the beginning of the mile (pay first!). In this case, you can give 1 banana to the camel and even so fill the basket with 1000 bananas, but you are left with 1999 bananas at A. Follow the same reasoning as before. Back again at A, where you have 1999 bananas, fill the basket with 1000 bananas, and feed the camel with 1 banana, leaving 998 bananas at A. Then, finally, back to A again (where there are 998 bananas), fill the basket with 997 and give one to the camel. Since in the last journey you start with 977 (instead of 1000) you reach B with 747 bananas (instead of 750). You have 747 bananas at B.

$\endgroup$
2
  • 1
    $\begingroup$ Hello and welcome to PSE. Please hide your answers in a spoiler. $\endgroup$
    – rhsquared
    Apr 11, 2018 at 6:22
  • 2
    $\begingroup$ Why do you think you can travel the 500 (or 750) miles back to A with a single banana? $\endgroup$
    – Rubio
    Apr 11, 2018 at 23:17
1
$\begingroup$

to move 3000 bananas by 1 km, camel consumes 5 bananas which with five trips. so not when number of bananas are less than or equal to 2000 the trips required is 3. so to consume 1000 bananas 5x = 1000 move 3000 bananas for x=200 miles ( 5 trips). we are left with 2000 bananas.

now we have 2000 bananas and we can move bananas in 3 trips

3x =1000 move 2000 bananas for x=333 miles. we are left with 1000 bananas again.

now total distance traveled is 533 miles and left with 467 miles. we are left with 1000 bananas. camel can take these bananas in 1 trip. so 1000-467=533

$\endgroup$
0
$\begingroup$
  1. Load up camel with 1000 bananas. Travel 500 miles, leaving 500 bananas. Dump them there.

  2. Do same trip again and leave 500 bananas at 500 mile mark.

  3. Do same trip again and pick up one of the 500 banana piles when you hit the 500 mile mark. Now you are at 1000 again.

  4. at 750 mile mark, drop your (now 750) bananas

  5. Go back to mile 500, pick up your 500 bananas

  6. Go to mile 750, and now you have 250 left

  7. Pick up your 750 that you previously left

  8. Now you have 1000 at mile 750

  9. Walk the remaining 250 miles, leaving 750

  10. Eat one for yourself and market the remaining 749 bananas.

749! Woo Hoo!

***Edit: I was basing mine off 538's recent Riddler, which says that the camel can travel w/o bananas as long as he doesn't sniff any bananas. So, whoops!

http://fivethirtyeight.com/features/how-many-bananas-does-it-take-to-lead-a-camel-to-market/

$\endgroup$
2
  • 3
    $\begingroup$ The camel will not go anywhere if it doesn't have any bananas. $\endgroup$
    – Sconibulus
    Sep 8, 2016 at 14:15
  • 2
    $\begingroup$ Agreed with @Sconibulus. You haven't taken into account that the camel will need to eat bananas on each return journey too. $\endgroup$ Sep 8, 2016 at 14:30
-1
$\begingroup$

I have a solution that has a better result than 534. I'm not sure it is the best solution.

1. The camel carries 1000 bananas for 250 miles. Thus, he will leave 750 bananas after each trip at the 250th miles. After 3 trips, there are 2,250 bananas at the 250th miles.
2. The camel carries 1000 bananas each trip for 2 trips for 500 miles. At the 750th mile, we have 1000 bananas.
3. As we have 250 miles left, the camel then makes a final trip, carrying 1000 bananas. He will consume 250 bananas, leaving 750 bananas at B.

$\endgroup$
1
  • 6
    $\begingroup$ The camel also eats bananas when it walks back. It'll refuse to walk from the pile if you leave all 750 bananas there. $\endgroup$
    – user88
    Sep 5, 2016 at 4:42
-1
$\begingroup$
  1. Load 1000 bananas, go 400 miles, leave 200 bananas, and return.
  2. Repeat #1. Now you have 400 bananas 600 miles from market.
  3. Load the last 1000 bananas and stop to pick up 400 bananas. Now you have 600 miles to go with 1000 bananas. You have 400 bananas to sell, unless you want to give your camel a treat.

or

  1. Load 1000 bananas, go1 mile leave 998 bananas, and return.
  2. Repeat #1. Now you have 1996 bananas 999 miles from market.
  3. Load the last 1000 bananas and stop at mile 1. Now you have 999 miles to go and 2995 bananas.

1 mile cost you 5 bananas or set up as a ratio - miles:bananas or 1:5.

Subtract 1000 bananas off the top because that's the most your camel can carry on the last load. Use the 2000 bananas to make a ratio equivalent to 1:5 or 1/5 = x/2000 x = 400 miles.

So if you repeat steps 1 - 3 till you only have 1000 bananas left, you will have covered 400 miles. Now you have 600 miles to go with 1000 bananas. You have 400 bananas to sell, unless you want to give your camel a treat.

$\endgroup$
1
  • 2
    $\begingroup$ Better solutions have already been provided. Please read existing answers before posting your own, $\endgroup$ Jun 14, 2020 at 0:52
-3
$\begingroup$

Answer : 833 Banana

First Camel transport 334km *3times At 334 km left 1998 banana Then transport 1998 Banana 499 km * 2times (999 banana) At the end 833km (334+499) only 167km left and 1000 banana remain And finally transport 1000 Banana 167km At destination 833 banana remain

$\endgroup$
1
  • $\begingroup$ The camel eats bananas on the way back as well $\endgroup$
    – bobble
    Dec 23, 2022 at 17:55