wellons: Barrels of Gold

Problem

My friend Brian Marion posed a variant of the following problem:
Suppose I just robbed Fort Knox. I was in a rush and I put the gold in what I had available: 3 large barrels. I didn't keep track of how much I put in each one, I just threw bars into whichever was closest until the klaxons drove my nerves over the edge. Then I hammered down their lids and bailed - I can't even be sure that a particular barrel has anything in it.
Since you helped plan the heist, I'll let you have any one of these three sealed barrels that you want. Of course, even an empty barrel is too heavy to lift by hand, so it's hard to tell which has the most gold. The only way you can measure their contents is to see if the forklift can lift them. As a safety feature, our forklift can be calibrated to a certain weight, which it will lift no more than. However we can only set this once because changing it a second time requires retooling and a visit from the manufacturer, which would blow our cover.
We know this: these barrels are holding between 0 and 1000 pounds of gold, with a uniform, random distribution. You get to pick a weight, any weight you'd like and test which barrels are heavier than that, and which are lighter. If just one is heavier and two are lighter - great! You found the one with the most gold. If there's a tie for heaviest, you'll just have to pick one. But hey, you might eliminate the lightest one and that's better than no information, right?
Suppose the forklift's zero calibration is the weight of an empty barrel, so we can ignore that number. Therefore, if you set it to 500 pounds, you have exactly a 1/2 chance of getting a particular barrel too heavy to lift, but a 3/8 chance of getting one too heavy and two too light. On the other hand, you might get two too heavy, and you'll wish you had set it higher. Obviously, there's a tradeoff: higher weights are less likely to have a tie among several barrels being the heaviest, but on the other hand they risk overshooting all the barrels and you'll be stuck just picking one of the three.
What is the weight capacity you should set on the forklift to maximize your average expected gain?

Solution

First we'll solve a more general problem, then plug in the numbers to solve this one. Without loss of generality, say the amount of gold in a barrel ranges from 0 to 1. Suppose there are

barrels and

(for guesses) calibrations available to us. Suppose the set

is the set of calibrations, which we'll write as
$C = \{c_{i} \hspace{.3em} \vert \hspace{.3em} i \in [1,g]\}$ . $c_{g}$ will be the biggest one and they descend from there, so this equation is true:

$\displaystyle 0 < c_{1} < ... < c_{g-1} < c_{g} < 1$

(1)

Finally, add the two constants $c_{g+1} = 1$ and $c_{0} = 0$ to make our formulas cleaner. Each barrel can fall into any of the

ranges: less than the smallest calibration, bigger than the largest, or between any pair of consecutive calibrations.
To find the expected value of a set of calibrations, we can find the expected values of each of these gaps and multiply those values by their probabilities, then sum up the products. The average value of a barrel between $c_{i+1}$ and $c_{i}$ is
$\frac{c_{j+1}+c_{j}}{2}$ and the only way you'll end up with that as the amount of gold you get is if the largest barrel is in that range. Fortunately, that probability is easy to calculate: the chance of all the barrels being less than $c_{i+1}$ is $c_{i+1}^{b}$ and the chance of them all being smaller than $c_{i}$ is $c_{i}^{b}$ , so we can simply subtract these two powers to get the probability that all the barrels are less than $c_{i+1}$ , but not all are less than $c_{i}$ .
Then the expected value is

$\displaystyle E(C)$	$\textstyle =$	$\displaystyle \sum_{j = 0}^{g}\frac{c_{j+1}+c_{j}}{2}(c_{j+1}^{b} - c_{j}^{b})$	(2)
	$\textstyle =$	$\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j+1}+c_{j})(c_{j+1}^{b} - c_{j}^{b}) \right]$
	$\textstyle =$	$\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j+1}^{b+1} - c_{j+1}c_{j}^{b} +c_{j}c_{j+1}^{b} - c_{j}^{b+1}) \right]$
	$\textstyle =$	$\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j}c_{j+1}^{b} - c_{j+1}c_{j}^{b}) +\sum_{j = 0}^{g}(c_{j+1}^{b+1}- c_{j}^{b+1}) \right]$
	$\textstyle =$	$\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j}c_{j+1}^{b} - c_{j+1}c_{j}^{b}) + 1 \right]$

The maximum value of

can be found by taking partial derivatives with respect to each $c_{i} \in C$ , setting these expressions to zero, and solving them simultaneously. The constant 1 will not survive differentiation and the $\frac{1}{2}$ is superfluous. A variable $c_{i}$ appears in 4 terms, namely

$\begin{eqnarray*}c_{i}c_{i+1}^{b}-c_{i}^{b}c_{i+1} + c_{i-1}c_{i}^{b}-c_{i-1}^{b}c_{i}\end{eqnarray*}$

with derivative,

$\begin{eqnarray*}c_{i+1}^{b}-bc_{i}^{b-1}c_{i+1} + bc_{i-1}c_{i}^{b-1}-c_{i-1}^{b}\end{eqnarray*}$

Thus the solution can be found by solving the equations:

$\displaystyle c_{i+1}^{b}-bc_{i}^{b-1}c_{i+1} + bc_{i-1}c_{i}^{b-1}-c_{i-1}^{b} = 0, \forall i \in [1, g]$

(3)

Finally, If g = 1 and b = 3

Returning to our original problem, if there are 3 barrels and 1 calibration $C = \{c_{1}\}$ , the Equations (3) require that we solve

$\begin{eqnarray*}1 - 3c_{1}^{2} & = & 0\end{eqnarray*}$

Therefore, the solution is
$c_{1} = \frac{1}{\sqrt{3}} = 0.57735...$ , meaning the best calibration is 577 lbs. This has a nice 42% chance of isolating the heaviest barrel and a mere 27% chance of not separating the barrels at all. You must be wondering what your payout is. By Equation 2 it is 748 pounds of Gold.

Another Example, g = 3 and b = 4

As another example, for 3 calibrations
$C = \{c_{1}, c_{2}, c_{3}\}$ and 4 barrels, Equations (3) are

$\begin{eqnarray*}c_{2}^{4}-4c_{1}^{3}c_{2} & = & 0 \\c_{3}^{4}-4c_{2}^{3}c_{3......{4} & = & 0 \\1-4c_{3}^{3} + 4c_{2}c_{3}^{3}-c_{2}^{4} & = & 0\end{eqnarray*}$