Saturday, September 24, 2016

Twelve coin problem

Things are a bit quiet in climate blogging - so with a weekend coming I'll honor my ancient promise of diverting to some recreational math. I saw a few weeks ago a mention at Lucia's of the old twelve coin problem. Twelve coins, one of which is fake and of different weight to the others, and to be found with three weighings on a balance (Update: the usual spec, as here, is that you also have to say whether it is heavier or lighter). This first came to prominence in WWII, when it was said to have become a distraction to the war effort in places like Bletchley Park, leading to suspicions that it had been planted by the Germans. A suggested counter was for the RAF to drop it on Germany.

I first encountered it when I started University; it was posed in circumstances where I was expected to be able to solve it, and I was embarrassed. A year later, I went to a lecture on information theory (newish in those days). I was struck by the proposition, helpful in later years, that the information in a result was a function of prior uncertainty. So that is the clue - each weighing should be arranged so each of 3 outcomes was as near equally probable as could be managed, maximising prior uncertainty. Then I could solve it easily, and also versions with more coins.

The basic constraint is that in N weighings there are 3N possible outcomes, while with n coins, there are 2n situations to resolve, since only once coin is false, and could be heavy or light. So for 12 coins, there are 24 possibilities and 27 outcomes of 3 weighings, so it is tight but possible. An alternative to the equiprobable outcome method is a requirement that each weighing should be so that each outcome was resolvable with the remaining weighings.

When I saw it mentioned again, I started thinking of a constructive algorithm that would also prove feasibility for all cases where there were enough results to theoretically resolve. I had an idea of describing the proof, but then my other recent hobby of Javascript programming seemed it might help. So I've made an interactive version (below) with the information needed to solve.

You can choose a number of coins up to 121, and then start (or restart any time). There are boxes for left, right and off-scale. The buttons representing coins have colored bands top and maybe bottom. The top band is what I call the HL score. Initially each coin might the bad one, heavy or light (HL). But once there has been a weighing that tilted, some possibilities fail. On the side that dropped, the coins could no longer be light, hence H. On the other side, they are L. And any not on the balance must be good (G). So the total number of possibilities remaining is the HU score = 2*HL+H+L.

There is another more subtle score - DU. This applies to the coins on the balance before weighing, and relate to whether you will gain information if the left balance goes down or up. HL coins will always become either H or L, so they are not scored. But if left pan down, then L on left or H on right would then be known to be good, so they are marked as D; if the left pan went up, that would tell nothing new about D coins. And similarly H on left or L on R would be counted as R.

You can move coins to the right (cyclic) by mouse click, or left by click with shift key pressed. If they are H or L, you will see the lower DU bar change as they move. When a weighing has been set up, click the weigh button.

The color scheme for top bars is HL black; H orange; L blue and G yellow. For the bottom, only H and L coins on the balance have color, and it's red for D, green for U. Here is an image of the gadget immediately following afirst weighing of 12 coins. Note the balance tilt. The four coins on the left are now H because they are on the heavy side, and U because they are H and left. On the right, they are L similarly, and also U. The off balance coins are all G, yellow.



You'll see a table with the HL counts for on and off, and the D and U counts. Three are in large fonts, and those are the ones needed for solution. The strategy is that for every weighing, the D and U should be as near equal as possible, and the off HL score should be about half the on. More critically, each should be ≤ 3M, where M is the number of weighings to follow after the one being set up. So in the image, for the next weighing, these numbers should all be ≤3. So take 3 off, then swap the others until the D and U scores are each ≤3. You'll see that as you rearrange, the system pads with known good coins (if available) to retain balance, and removes surplus. You can try to minimise usage of dummies; you should be able to reduce the need to at most two. If known good coins aren't available (first weighing), don't worry; the system will imagine them present.

So here is the gadget. Just press start, then move coins for weighing with click and shift-click, bearing in mind the above strategy. As long as the three big numbers are ≤ 3M, you can solve in minimum weighings. It is solved when there is just one coin with H or L color showing.



I have to say, it is now a bit mechanical. You don't need to know the coin numbers, or even what the colors mean, as long as you keep your eye on the scores. But the Javascript isn't solving it - it's just adding up what you could count yourself, but displayed in a helpful way.

Update I have changed the DU score to count 1 each for HL (black) coins. This is more consistent when there are such coins. It means that all 3 large font numbers should now be made as nearly as possible equal an ≤3^M.

Update - proof

I originally planned this post as a constructive proof - show a method that is sure to work. I think the scoring goes a long way there. But a method can be spelt out. Suppose we have a set of coins with HL score g≤3N+1, to resolve in N+1 weighings. It's enough to show that a weighing can be made to reduce this to an assured score h≤3N. And the point of the big font numbers in the gadget is that they are the respective HL scores after each possible outcome.

Let g=2*p+q, where 3N≥p≥q≥0. Normally p=3N is OK, but if that leaves q<0, you can reduce p until q is positive. Then take a set of coins, HL score q (including all known good ones), to be kept off the balance. If all coins have HL score 2 (as at the start), that's still possible, because g and hence q must be even.

Then put the remaining coins one by one on the balance. Depending on what side, the D and U scores will increment by 1 or zero. Put all the H coins on first, alternating sides so the gap between D and U is never more than 1. Then the L, also so as to increase whichever of D,U is less. That will also alternate, so there will be a max imbalance of coin numbers of 2. Then finally, if there are HL coins, put them on whatever side improves coin number balance; each will increase both D and U by 1.

This ensures D+1≥U≥D. And since D+L is the HU score, when loaded, D=U=p≤3N. Since D,L and q are the respective HL scores after each possible balance result, and each ≤3N, that completes the proof.

Numbers of coins on each pan may differ by up to two. After the first weighing, this can be balanced by adding known good coins. On the first weighing, if g<3N-1, you can always choose p even, so the coins can split equally. In the worst case where g=3N-1 (eg 13 coins in 3 weighings) an external known good coin is needed.






19 comments:

  1. Intuitively I thought:
    Weight one half of the coins against the other half (if odd, leave one out)
    Take the half that reads lower and repeat. (if they're equal, then you must have left one out and it's the guilty party).

    This essentially then just becomes a matter of converting a decimal (# of coins) to binary. INT[Log2(n)] where the integer portion will tell you how many weightings you'll need to reach a conclusion.

    I then realized that when n is greater than 15 using 1/3 vs 1/3 is the best weighing strategy. Not knowing exactly how to formalize this I experimented a little in a spreadsheet and it looks like when n > 15, then INT[Log3(n)] +1, and if n < 15, then INT[Log2(n)] gives what I think are the minimum number of weighings for any number (n) of coins where one coin is different than the rest.

    ReplyDelete
    Replies
    1. "I then realized that when n is greater than 15 using 1/3 vs 1/3 is the best weighing strategy. "
      I think you should always get as cloase as you can. That is related to maximising uncertainty - 1/3 chance left, 1/3 R and 1/3 balance.

      "INT[Log3(n)] +1"
      I think it is INT[Log3(n*2)]+1, if the coins could be heavy or light (hence the *2). That determines the first weighing. You should kep off the max number you could resolve in one less weighing, which you'll have to do if it balances.

      Delete
  2. I must be missing something. FWIW, this was intuitively obvious or I didn't understand it. The third weighing has to be one coin against another. the second weighing would have to be two coins on each side and the only way to get there would be to qualify the group of four - this can be done by weighing 8 of the coins first, if they balance the off-coin isn't in that group and you now can look at the four coin remainder.

    Maybe what you are interested in here isn't solving the thing but establishing the limits within which it can or cannot be solved.

    it's too bad I've never been able to do anything useful with this talent (if that's what it is) at this sort of thing.

    ReplyDelete
    Replies
    1. jf,
      Try out the gadget. The final weighing can resolve three coins, as long as you by know know that they can only be one kind (heavy or light, H or L in my terms). Say you have 2 H, 1 L. Put an H each side, and leave one off. If it tilts, you'll know which is heavy; if not, then it's the one left off. You always have to learn as much as possible from each result, including level, which tells you the fake is not on the balance.

      "Maybe what you are interested in here isn't solving the thing but establishing the limits within which it can or cannot be solved."
      The limits are in the earlier arithmetic; to do n coins in M weighings, 2*n≤3^M. With this method, you can actually achieve that, which isn't too hard to demonstrate.

      Remember, we don't know if the fake is heavy or light. But if the first weighing tilts left then we know:
      1. The left coins can't be light
      2. The right coins can't be heavy
      3. The coins off balance must be good.

      Delete
    2. I can now see why it wasn't as easy as I thought. sorry to waste your time.

      Delete
    3. "sorry to waste your time"

      That's what this problem is famous for :)
      Besides, I wasn't clear - hope it's better now.

      Delete
  3. You don't know the bias up or down

    ReplyDelete
  4. Nick, I think using n*2 adds an extra step. E.g., with 21 coins: INT[Log3(n*2)]+1 = 4 while INT[Log3(n)] + 1 = 3. And with 21 coins you can find the false coin in 3 weighings.

    ReplyDelete
    Replies
    1. Kevin,
      "And with 21 coins you can find the false coin in 3 weighings."
      Only if you know whether it is heavy or light. Otherwise, with 21 coins there are 21*2=42 possibilities to distinguish. And with 3 weighings, there are only 3*3*3=27 possible outcomes to discriminate them.

      Delete
    2. Kevin.
      A way to think about it - could you get 2 coins in 1 weighing? You could weigh them against each other, but if it tilts left, you don't know whether the left is heavy or the right light. And if it balances, you know it's the off one, but not whether heavy or light. Actually, the last is probably OK within the rules; the method I'm describing always not only identifies the fake, but gives that info. I'm not sure whether not having to know that makes a huge difference.

      INT(log3(2))+1=1, but INT(log3(2*2+1))=2, and I think 1 weighing isn't enough in all cases.

      Delete
    3. I've added above to specify that the answer has to include whether the fake is heavy or light.

      Delete
    4. ps Kevin,
      Sorry I didn't make that extra requirement clear. I see how it was causing a difficulty. It's actually a much harder problem if you don't have that requirement.

      Delete
    5. I thought more about the version of the problem where you don't have to say whether the fake is heavy or light. It isn't much harder - I think it extends the number you can identify by just 1. Think of the case of 3 weighings and N coins. If N≤13 you can just follow the same method; you'll identify the fake and whether heavy or light. But what if N>13?

      The max you can put on the balance at first is 9 (with good coin to even up). If it tilts, you have the same remaining problem as above - 9 coins where you have ruled out heavy or light, and the N-9 you left off are all good. If no tilt, then at the next weighing you can put at most 3 on, since that's all you can resolve if tilt. But if no tilt again, then in the third weighing you can only put 1 on; with 2 unknown coins you can't say anything if it tilts and no more weighing possible. So that is 9+3+1=13 coins put on. But at the last stage, you could also have a coin off balance. If tilt, then it's good, and if not, then it is the fake, even though it has never been on the balance, so you don't know if it is heavy or light. So N=14, but not more.

      Delete
  5. Nick -
    Cool Java program. But when the script "imagines" the existence of known good coins, it's not true to the original problem statement. And that's significant: with N=4 coins (2*N=8 possibilities), the script allows a solution in 2 steps. [That's consistent with the ceil(log3(2*N)) formula based on information. One can start by weighing #1&#2 vs. #3, for example.] But without a known good coin, one can only start by comparing 1-v-1 or 2-v-2, either of which allow a path with 4 possibilities remaining, requiring two more steps for a guaranteed solution.

    Another example with N=12 occurs when the initial 4-v-4 comparison is unequal; one can put 3 from the heavier side & 3 from the lighter side on the left pan and weigh. This is a good strategy -- that is, one stays on the max-3-weighings path -- but without positing additional coins beyond the 12, there are only 4 known good coins at that point in the tree.

    [Also, a nitpick - the balance code isn't quite right in what it shows, displaying 2 known-good coins offsetting one unknown. At least some of the time.]

    ReplyDelete
    Replies
    1. HaroldW,
      Thanks. The need for prior good coins to balance is only pressing for the maximal case of (3^N-1)/2 - 13 coins in 3 weighings, for example, or 4 in 2. If there is 1 coin less, (like the common 12) it's not needed. Of course, you can make use of the bonus coins if you want - by putting 8 on one side with good coins to balance, for example. But you can do the first weighing without that, and later there are always enough known coins from that weighing.

      Of course the program just tips the balance based on its knowledge of where the fake is - arranging to add the good coins to balance numbers is for appearance, and it may not always get it right. I'll check.

      Delete
    2. Harold,
      Yes, on checking I see that the balancing coins arrangement is not working. It was - I must have messed it up somehow. Working on it.

      Delete
    3. Balancer looks fine now!

      Delete
  6. "Things are a bit quiet in climate blogging"

    No kidding. If you do run across a climate science blog that actually works the math and physics angles, tell me about it please?






    ReplyDelete