Problem 4 (Ali Baba Problem)

Ali Baba (from the Arabian Nights) is going to his cave where he keeps his gold and platinum. He wants to fill his sack, but his sack holds at most 200 pounds of gold or 40 pounds of platinum. The maximum combined weight of gold and platinum he can carry in his sack is 100 pounds. He wants to use the gold and platinum to buy camels. For every pound of gold, he can purchase 20 camels, and for every pound of platinum, he can purchase 60 camels. How many pounds of gold and platinum should Ali Baba put in the sack to obtain the most number of camels ?

Solution
Let g denote the pounds of gold Ali Baba puts in his sack, and p the pounds of platinum. Since his sack can hold at most 200 pounds of gold, we know that g is less than or equal to 200, and since his sack can hold at most 40 pounds of platinum, we have that g is less than or equal to 40. And since the total amount of gold and platinum Ali Baba can put his sack is 100 pounds, we have that g + p is less than or equal to 100. And finally since Ali Baba can buy 20 camels for a pound of gold and 60 camels for a pound of platinum, the total number of camels C Ali Baba can buy is C = 20g + 60p. Putting everything together, we must find the values of g and p that maximizes the quantity of camels C = 60g + 40p subject to the inequalities

This is a basic linear programming problem that can be solved with the help of the following drawing.

The shaded region in the drawing consists of all those values of g and p that satisfy the inequalities. In other words, those values of gold and platinum that satisfy the sack requirements. To find the values of g and p that lie in the shaded region which maximize the number of camels Ali Baba can buy, we observe that the amount C is a constant on lines of the form 20g + 60p = constant, and so it is not difficult to see that this function is a maximum at the corner point (g, p) = (60, 40).
We could also resort to a basic result from linear programming, which states the maximum point lies at one of the corner points of the feasible set. In this problem, there are four corner points, which are (0, 0), (100, 0), (0, 40), and (60, 40). Evaluating the number of camels Ali Baba can buy at each of these corner points, we have

• when g = 0, p = 0, Ali Baba can buy C = 20 (0) + 60 (0) = 0 camels
  
• when g = 100, p = 0, Ali Baba can buy C = 20 (100) + 60 (0) = 2000 camels
  
• when g = 0, p = 40, Ali Baba can buy C = 20 (0) + 60 (40) = 2400 camels
  
• when g = 60, p = 40, Ali Baba can buy C = 20 (60) + 60 (40) = 3600 camels
  

Hence, Ali Baba should pack his sack with 60 pounds of gold and 40 pounds of platinum, which allows him to buy 3600 camels.

[Previous]	Problem 3 (Friday-the-13th Problem)
[Next]	Problem 5 (Clock Problem)
[Up]	November Solutions
[Home]	Home Page
[Mail]	Send EMail to Maine Math Talent Search
[Contents]	Maine Math Talent Search Contents

Last modified on Tuesday, January 12, 1999