The Great Sultan of the Indies was sent by one of his viziers 99 bags of gold, each containing exactly 50 coins. Hidden somewhere in those 99 bags is a hollowed coin (indistinguishable to the naked eye from the others) containing a secret message destined to His Most Excellent Majesty. Using a simple two-pan balance, in how many weighing can you find the bag containing the lighter coin? With how many further weighing can you find the coin within the bag?
The solution of the problem is not that complicated, but depends entirely on the assumptions you make on the balance. If one supposes that the balance is large enough to pile the 99 bags in either one of its pan, and that is locked while you’re loading it, giving its reading only once you’re done loading it, the solution that comes to mind is to split the bags in two halves, and then look for the lighter pan, take the bags in the heavier pan and send them to the treasury (as not containing the message), and splitting the lighter pan in two, repeating until only two bags are left.
This approach is simple, and will, on average, surprisingly, necessitate fewer than weighing (if is the number of bags). While intuitively we think that we will simply divide piles of bags in two each time, it’s easy to forget that the pile may contain an odd number of bags, and as such, not amenable to the two-pan device: we must leave a bag out.
Two things can happen. One: a pan rises (while the other sinks), and we must continue our search, or, Two: the pans level, and the bag withheld contains the hollowed coin. If the bag withheld contains the coin, the (bag-level) search stops.
The recurrence relation is therefore given by:
If the bags are thoroughly mixed, each time we have an odd number of bags, we have chances that the bag withheld is the one containing the hollow coin, and we stop; but we continue with probability . If we have an even number of bags, we must continue.
The possibility of early stopping reduces the expected number of weighing, but how much? Plotting , we see that it is bounded:
Indeed, I conjecture:
Depending on , the procedure that leaves one bag out once in a while may save up to weighing compared to the direct estimation of .
This problem is often found in recreational mathematics compendia where the goal is to force the layman to devise a method of finding the bag or the coin within the bag (the procedure is the same, of course), but it does not often completely describe the problem. What kind of scale is it? How do you define a “weighing”? I would expect, for example, that a scale that can hold that many bags of coins can’t possibly load bags in a single “atomic” operation, taking 0 time, for both pan simultaneously. A realistic interpretation is that you will load the bags two by two (one in each pan at more or less the same time) and look at the balance each time. If you take this interpretation, you may find the lighter bag before finishing loading the balance for the first weighing; and therefore you could answer the first question (how many complete weighings to find the bag) by 0 or 1.