Navigation Paths Between Two Points

Consider a rectangular grid of 4×3 with lower left corner named as A and upper right corner named B. Suppose that starting point is A and you can move one step up(U) or one step right(R) only. This is continued until B is reached. 

How many different paths from A to B possible ? 

Here is calculation of total number of paths. 

Combinations of Naviagation Paths

What is the question?

If the right move is represented as R and up move as U then, RRRUU is the one path to reach at B.

UURRR is one more path between points A and B.

URRRU is another way to reach at B.

Further, one can reach at B via RURRU.

So number of such paths are possible.

However, if all paths above are observed, we can conclude that total 5 moves are needed to reach from point A to B. Out of those 5, 3 have to be RIGHT and 2 have to be UP. 

That is, any combination having 3R and 2U in 5 moves will give a valid path to reach at B.

Now, number of ways 3R can be placed in 5 moves can be calculated as - 

C(5,3) = 5!/(5-3)! * 2! = 10.

To sum up, there are 10 paths available between points A and B.
 

The Camel and Banana Puzzle

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the most bananas you can bring over to your destination?

As many as 'these' numbers of bananas can be saved!

The Camel and Banana Puzzle : Solution

What was the puzzle? 

 Let A be the starting point and B be the destination in this transportation. If the camel is taken with 1000 bananas at start, to reach the point B which is 1000 km away from A, it needs 1000 bananas. So there will be no bananas left to return back to point A.

That's why we need to break down the journey into 3 parts.

Part 1 :

For every 1 km the camel needs to -

1. Move ahead 1 km with 1000 bananas but eat 1 banana in a way.

2. Leave 998 bananas at the point and take 1 banana to return back to previous point.

3. Pick up another 1000 bananas and move forward while eating 1 banana.

4. Drop 998 bananas at the same point. Return back to previous point by consuming 1 banana.

5. Pick left over 1000 bananas and move 1km forward while consuming 1 banana to same point where 998 + 998 bananas are dropped. Now, the camel doesn't need to  return back to previous point. So, 998 + 998 + 999 are carried to the point.

That is for every 1km, the camel needs 5 bananas.

After 200 km from point A, the camel eats of 200x5 = 1000 bananas and at this point the part 1 ends.

-------------------------------------------------------------------------------------------------
 
PART 2 :

1. Move ahead 1 km with 1000 bananas but eat 1 banana in a way.

2. Leave 998 bananas at the point and take 1 banana to return back to previous point.

3. Pick up another 1000 bananas and move forward to the point where 998 bananas left while eating 1 banana.

Now, the camel needs only 3 bananas per km.

So for next 333 km, the camel eats up 333x3 = 999 bananas.

-------------------------------------------------------------------------------------------------
 
PART 3 :

So far, the camel has travelled 200 + 333 = 533 km from point A and needs to cover 1000 - 533 = 467 km more to reach at B.

Number of bananas left are 3000 - 1000 - 999 = 1001.

Now, instead of wasting another 3 bananas for next 1 km here, better drop 1 banana at the point P2 and move ahead to B with 1000 bananas. This time the camel doesn't need to go back at previous points & can move ahead straightaway.

For the remaining distance of 467 km, the camel eats up another 467 bananas and in the end 1000 - 467 = 533 bananas will be left.

-------------------------------------------------------------------------------------------------

Sara's Desert Trek

Sara needs to trek from an oasis to a destination 10 miles away across a barren desert. 

The facts:

• Crossing one mile of desert requires using 1 gallon of water.
• Sara can only carry 6 gallons of water at a time.
• Sara can drop a water cache (of any amount of water from the supply she is carrying at that moment) at any of the nine stops along the route, and then pick up any part of the cache on a later trip.

What's the minimum number of times Sara must leave the oasis in order to cross the entire 10 mile span of desert?

This is how she optimizes her journey! 

Sara's Planning in Desert Trek

What was the challenge in journey?

1. First Sara collects 12 gallons of water at milepost 1 after having 3 trips from source. She uses 2 gallons (out of 6) for forward & backward journey from source to milepost & dropping 4 gallons in cache at milepost 1.

2.She collect 6 gallons more water at the start of 4th trip from source & drops 5 gallons at milepost 1. Now, she doesn't need to return back to source and 17 gallons of water available at milepost 1.

3.In next 2 rounds, she moves 8 gallons of water from milepost 1 to milepost 2 (1 for forward + 4 for drop + 1 for backward journey in each round). 

4.Now only 5 gallons left at milepost 2. She uses 1 gallon for journey from milepost 1 to milepost 2 and drop remaining 4 gallons at milepost 2. Now, 12 gallons of water is available at milepost 2.

3.Next, using 2 gallons (out of 6 which is maximum she can carry) she moves from milepost 2 to milepost 4 and drop 2 gallons at milepost 4 & comes back at milepost 2 using remaining 2. 

4. Again, on arriving back at milepost 2, she has left with 6 gallons of water at milepost 2 out of which she uses 2 to reach milepost 4 where 2 gallons of water still available there already collected in previous round. Now, she doesn't need to return back from
milepost 4.

5. She uses the remaining 6 gallons of water to reach at the milepost 10.

To conclude, Sara has to leave Oasis only 4 times as describe in steps 1 and 2 if she want to cross the entire 10 mile span of desert.