The Great Sultan of the Indies

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?

two-pan-balance

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 O(\lg n) weighing (if n 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:

\displaystyle B(n)=\begin{cases} 0&\text{if }n<2\\ 1+\frac{n-1}{n}B\left(\frac{n-1}{2}\right)&\text{if }n\text{ is odd}\\ 1+B\left(\frac{n}{2}\right)&\text{otherwise.} \end{cases}

If the bags are thoroughly mixed, each time we have an odd number of bags, we have \frac{1}{n} chances that the bag withheld is the one containing the hollow coin, and we stop; but we continue with probability \frac{n-1}{n}. 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 B(n), we see that it is bounded:

balance-fct

Indeed, I conjecture:

\displaystyle \log_2 n - \phi \leqslant B(n) \leqslant \log_2 n

where \displaystyle \phi=\frac{1+\sqrt{5}}{2}.

Depending on n, the procedure that leaves one bag out once in a while may save up to \approx 1.6 weighing compared to the direct estimation of \log_2 n.

*
* *

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 n/2 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.

3 Responses to The Great Sultan of the Indies

  1. freininghaus says:

    Thanks for this interesting post!

    I would like propose a different approach: Since each step can have three different outcomes (bags on the left are heavier, bags on the right are heavier, or both have the same weight), one could try to make the probabilities of each of these outcomes approximately equal. This will minimize the average number of steps that are required to find the hollow coin.

    The idea is to split all bags into three almost equally sized sets, such that the number of bags in each set differs at most by one, and at least two sets have the same number of bags (this is always possible). Then check the balance of two such sets. If both have the same weight, then the hollow coin is in the third set.

    To find C(n), the average number of weighings that we need with this approach, we have to consider the following cases:

    (a) n C(n) = 0

    (b) 2 <= n < 4:

    C(n) = 1

    (c) n is a multiple of 3:

    C(n) = 1 + C(n/3)

    (d) n – 1 is a multiple of 3:

    Two sets have n1 = (n-1)/3 bags, the third has n2 = n1 + 1 = (n+2)/3 bags.

    The probability that n1 or n2 bags will remain in the next step is 2*n1/n or n2/n, respectively.

    C(n) = 1 + 2*n1/n * C(n1) + n2/n * C(n2)

    (e) n – 2 is a multiple of 3:

    One set has n1 = (n-2)/3 bags, the other two have n2 = n1 + 1 = (n+1)/3 bags.

    C(n) = 1 + n1/n * C(n1) + 2*n2/n * C(n2)

    If I got the maths right, then C(n) 15.

    For n=7 and n=15, B(n) < C(n), i.e., your approach is better.

    log_3(n) is a lower bound of C(n), and for all n which are powers of 3, we have C(n) = log_3(n).

    In contrast to B(n), the function C(n) increases monotonically. What's interesting is that for all n between 2*3^(m-1) and 3^m, C(n) will have the same value C(n)=m.

  2. freininghaus says:

    Thanks for this interesting post!

    I would like propose a different approach (2nd attempt, I hope that WordPress will get the formatting right now): Since each step can have three different outcomes (bags on the left are heavier, bags on the right are heavier, or both have the same weight), one could try to make the probabilities of each of these outcomes approximately equal. This will minimize the average number of steps that are required to find the hollow coin.

    The idea is to split all bags into three almost equally sized sets, such that the number of bags in each set differs at most by one, and at least two sets have the same number of bags (this is always possible). Then check the balance of two such sets. If both have the same weight, then the hollow coin is in the third set.

    To find C(n), the average number of weighings that we need with this approach, we have to consider the following cases:

    (a) n C(n) = 0

    (b) 2 <= n < 4:

    C(n) = 1

    (c) n is a multiple of 3:

    C(n) = 1 + C(n/3)

    (d) n – 1 is a multiple of 3:

    Two sets have n1 = (n-1)/3 bags, the third has n2 = n1 + 1 = (n+2)/3 bags.

    The probability that n1 or n2 bags will remain in the next step is 2*n1/n or n2/n, respectively.

    C(n) = 1 + 2*n1/n * C(n1) + n2/n * C(n2)

    (e) n – 2 is a multiple of 3:

    One set has n1 = (n-2)/3 bags, the other two have n2 = n1 + 1 = (n+1)/3 bags.

    C(n) = 1 + n1/n * C(n1) + 2*n2/n * C(n2)

    If I got the maths right, then C(n) is smaller than B(n) for all n larger than 15.

    For n=7 and n=15, B(n) is smaller than C(n), i.e., your approach is better.

    log_3(n) is a lower bound of C(n), and for all n which are powers of 3, C(n) is exactly log_3(n).

    In contrast to B(n), the function C(n) increases monotonically. What's interesting is that for all n between 2*3^(m-1) and 3^m, C(n) will have the same value C(n)=m.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: