John P. Robertson
The company golf league is under way, so here’s a problem that is not likely to actually come up. Suppose you can hit the ball so it always goes in exactly the direction you want, but on each stroke you can only hit one of two distances. So, on any stroke, you might fall short of the hole, drop into the hole, or drive past the hole. Suppose the tee-to-hole distances for nine holes are 300, 250, 200, 325, 275, 350, 225, 375, and 400 yards. What two distances would you want to be able to hit? For example, if you could hit 200 yards and 25 yards, you could score 29 for the nine holes. In this case, for the eighth hole you could score 3 by hitting the ball 200 yards twice, which overshoots the hole, and then hitting a 25-yard shot once to land in the hole.But you can do better than this! Find a pair of distances that minimizes your total number of strokes for the nine holes.
Encoding Bits for Fun and Profit
This puzzle from Jon Evans involves a giant computer company that has a contract to encode large amounts of binary information on storage media. Statistically, each bit is equally likely to be 0 or 1, independent of the values of any other bits. However, the encoding machine produces a bad imprint for every bit in a sequence of 1s as long as, or longer than, a fixed length L. The client will pay $1 for every terabit (trillion bits, or 1012 bits) imprinted, but the consequence of a single incorrect bit is so catastrophic that the client charges $1 billion for each such bit.
The computer company can maintain its machine to achieve any value of L, as high as desired, but the cost rises exponentially with the value of L. Specifically, the maintenance cost per bit is $(2(L – 117)). For example to set L = 30 would only cost $(2–87) per bit or only about $0.000006 for a billion terabits, but to set L = 1000 would cost about $6 x 10286 for a billion terabits.
The question was, is it possible for the computer company to produce a positive expected profit?
Johnny Chen shows that with L = 76, an expected profit is possible, and this is the only such L. His solution is for fixed L, let B be the total number of bits encoded, e(B) be the random variable for the number of bits in error, and P be the random variable denoting profit or loss. Each bit produces a revenue of 10–12 and maintenance cost of 2 (L – 117) ; each bit in error costs 109. We show that E[e(B)] is 0 when B < L and [B(L + 1) – L(L – 1)]*2(–(L+1)) otherwise. This is clear for B < L since Pr(e(B) > 0) = 0. For B >= L we note that when B = L, there are only errors when all the bits are 1s; therefore E[e(L)] = L*2(–L). Now consider B = k > L. The expected number of errors in the first k – 1 bits is E[e(k – 1)]. The last bit adds to the error count in only two cases:
- The last L + 1 bits are 0, 1, 1, ..., 1: adds L errors.
- The last L + 1 bits are 1, 1, 1, ..., 1: adds 1 error.
Both cases occur with probability 2(–(L+1)), so E[e(k)] = E[e(k – 1)] + L*2(–(L+1)) + 1*2(–(L+1)) = E[e(k – 1)] + (L + 1)*2(–(L+1)). Since E[e(L)] = L*2(–L) and E[e(k)] – E[e(k – 1)] = (L + 1)*2(–(L+1)) for k > L, E[e(k)] = L*2(–L) + (k – L)*(L + 1)*2(–(L+1)); the formula above follows.
From this, we have E[P] = B * 10(–12) – B * 2(L – 117) – 109 * 2( –(L+1) ) * [B(L+1) – L(L – 1)] if B >= L and E[P] = B * 10(–12) – B * 2 (L – 117) otherwise. Assuming that we are only interested in B at least 1012, the case where B < L is not relevant (the maintenance cost is too high). For L = 76, E[P] > 0 and grows linearly with B.
Bob Conger included a risk analysis in his solution. He observes that while L = 76 produces a tidy expected profit per billion terabits, it is an expected value that comes from significantly variable outcomes. He suggests that another way to make a profit is to set L = 51, and then only take jobs of length 50 or less. He adds, “Of course, the scale of this business is so small as to be ridiculous, but we can say that there is at least the conceptual profit in this game plan.”'
David Atkinson, John Jansen, David Oakden, and David Uhland also submitted solutions.