Enigmatic Code

Programming Enigma Puzzles

Enigma 1589: Coin-cidence

From New Scientist #2754, 3rd April 2010 [link]

I recently purchased a number of seemingly identical antique coins knowing that an unspecified one of them was counterfeit and significantly different in weight from the others.

By coincidence, I have another exactly similar and authentic coin already in my collection.

Using a sensitive two-pan balance, I calculate that to be certain of finding the offending coin and whether it is heavier or lighter than the others, I shall need three weighings.

Had the number of coins I purchased been any larger, I would have needed at least one more weighing to be sure of achieving the same outcome.

How many coins did I purchase?

[enigma1589]

Advertisements

5 responses to “Enigma 1589: Coin-cidence

  1. jimrandell 24 January 2012 at 12:16 pm

    This is a tough one to solve programmatically.

    From n weighings there are 3^n outcomes, and with exactly one counterfeit coin to detect from m coins (which could be heavier or lighter) there are 2m possibilities. So the maximum number of coins that could satisfy the problem would be floor(3^n / 2), which for n=3 is 13.

    And this paper elegantly shows that 13 is indeed an achievable solution. [ http://www.link.cs.cmu.edu/15859-s11/notes-2005/maacoins.pdf ]

    Programatically, we construct a decision tree, by considering possible balance sets at each stage. For three balances this runs in 8.7s (or 4.0s using PyPy). Although I think it would be possible to reduce the runtime by exploiting the symmetry of the decision tree.

    Note: The program is longer than necessary, as it includes code to output the decision tree.

    from itertools import combinations
    
    # with n balances we can resolve at most 3^n outcomes
    
    # since we have one fake coin, which could be lighter or heavier
    # the maximum number of suspect coins we could distinguish with n weighings
    # is floor(3^n / 2)
    
    # determine how to balance the coins
    # with possible fakes ps
    # and m remaining balances
    # return the decision tree and outcomes
    def balance(coins, ps, m):
      # determine sets a0, b0 (of size n0) to weigh
      n = len(coins) // 2
      for n0 in range(1, n+1):
        for a0 in combinations(coins, n0):
          for b0 in combinations(coins.difference(a0), n0):
            if not(a0 < b0): continue
            # distribute the possibilities
            lt0, gt0, eq0 = [], [], []
            for w in ps:
              a = sum(w[i] for i in a0)
              b = sum(w[i] for i in b0)
              if a < b: lt0.append(w)
              elif a > b: gt0.append(w)
              else: eq0.append(w)
            # can the remaining balances hope to resolve the outcomes
            if any(len(x) > 3**m for x in (lt0, gt0, eq0)): continue
    
            # are we at the last balance? return the sets and the outcomes
            if m == 0: return ((a0, b0), (lt0, gt0, eq0))
    
            # otherwise we need to check that the outcomes we have can be resolved
            lt = balance(coins, lt0, m-1)
            if lt is None: return None
            gt = balance(coins, gt0, m-1)
            if gt is None: return None
            eq = balance(coins, eq0, m-1)
            if eq is None: return None
            # return the sets and the trees for the remaining balances
            return ((a0, b0), (lt, gt, eq))
      # no sets work
      return None
    
    # output the decision tree
    def output(t, pre=[]):
      # are we at a leaf?
      if type(t) is list:
        print(*pre, sep=' / ', end=' => ')
        if len(t) == 0:
          print('#') # no possibilities at this leaf
        else:
          # identify the fake coin
          w = tuple(i for i in t[0] if i != 0)[0]
          print(t[0].index(w), ('H' if w == 1 else 'L'), sep='')
        return
    
      (a, b), (lt, gt, eq) = t
      A = ','.join(map(str, a))
      B = ','.join(map(str, b))
      output(lt, pre + [A + ' < ' + B])
      output(eq, pre + [A + ' = ' + B])
      output(gt, pre + [A + ' > ' + B])
    
    
    # coin 0 is the good one, so let's start with 14 coins and work down
    for n in range(14, 0, -1):
      # the set of coins
      coins = set(range(n))
      # create the possibilities for the fake coin
      ps = []
      for i in range(1, n):
        for w in (-1, 1):
          ps.append(tuple((w if i == x else 0) for x in coins))
    
      # attempt a solution
      t = balance(coins, ps, 2)
      if t:
        print(n-1, "coins") # don't include the good coin
        output(t) # output the decision tree
        break # and we're done
    

    Solution: You purchased 13 coins.

    • jimrandell 25 January 2012 at 3:53 pm

      This is a much faster variant on the previous program (it runs in 64ms), although it doesn’t directly construct a decision tree (but you can deduce it from the computation). Instead of tracking the individual coins it deals with the number of different kinds of coins, keeping track of ‘G’ (good coins), ‘S’ (coins which may be suspect) and ‘H’, ‘L’ (coins which may be suspect, but if they are they are heavy or light respectively). It then reduces the search space by generating sets of different numbers of each kind of coin.

      Note: You can modify the terminating condition in the balance() function to allow a single suspect coin to terminate the function (without knowing if it’s heavier or lighter), and it turns out you could purchase 14 coins and still determine the fake (but you might not know if it’s heavier or lighter).

      from itertools import combinations
      
      def different_combinations(i, n):
        for x in set(combinations(i, n)):
          yield x
      
      def difference(l, i):
        n = list(l)
        for x in i: n.remove(x)
        return n
      
      # consider coins labelled one of:
      # G = good, S = suspect, H = possibly heavy, L = possibly light
      
      # how does the outcome of a balance change our knowledge
      ID = { 'S': 'S', 'H': 'H', 'L': 'L', 'G': 'G' }
      EQ = { 'S': 'G', 'H': 'G', 'L': 'G', 'G': 'G' }
      LT = { 'S': 'L', 'H': 'G', 'L': 'L', 'G': 'G' }
      GT = { 'S': 'H', 'H': 'H', 'L': 'G', 'G': 'G' }
      
      def translate(a, da, b, db, c, dc):
        return [da[x] for x in a] + [db[x] for x in b] + [dc[x] for x in c]
      
      
      def balance(coins, m):
        s, h, l, g = (coins.count(x) for x in list('SHLG'))
      
        # have we found the suspect coin?
        if s == 0 and h + l < 2: return ('S' if s else 'H' if h else 'L' if l else '#')
      
        # are we out of balances?
        if m == 0: return None
      
        # we only need one good coin
        for i in range(g-1): coins.remove('G')
      
        p = len(coins) // 2
        for n in range(1, p+1):
          for a in different_combinations(coins, n):
            ca = difference(coins, a)
            for b in different_combinations(ca, n):
              if a > b: continue
              c = difference(ca, b)
              eq = balance(translate(a, EQ, b, EQ, c, ID), m-1)
              if eq is None: continue
              lt = balance(translate(a, LT, b, GT, c, EQ), m-1)
              if lt is None: continue
              gt = balance(translate(a, GT, b, LT, c, EQ), m-1)
              if gt is None: continue
              return ((a, b), (eq, lt, gt))
        return None
      
      
      for n in range(13, 0, -1):
        t = balance(['G'] + ['S'] * n, 3)
        if t is not None:
          print(n, "coins")
          print(t)
          break
      
      • jimrandell 26 January 2012 at 10:47 am

        Although the general case of the problem is having a known good coin, I’m not sure that it’s obvious that multiple good coins are not necessary in the intervening stages (although, as it turns out, they are not).

        Certainly there’s no point having good coins on both sides of the balance. If you remove the condition of having a single good coin, and instead ignore balances with good coins on both sides this algorithm still finds the solution in under a second (750ms).

  2. Hugh Casement 1 April 2016 at 6:18 pm

    This is a well-known puzzle, but nowhere have I seen the following formulation of the solution, that lends itself to a generalization to larger numbers.

    Write down the integer 1 and three successive integers starting at 3: i.e. 1, 3, 4, 5.  Convert them to 3-digit numbers in base 3: 001, 010, 011, 012.  For each number, permute the digits cyclically: 112, 121, 122, 120; 220, 202, 200, 201.  For each digit position, we now have four numbers with each of 0, 1, and 2.  Write a different one of the twelve numbers on each coin.  In this variant with a thirteenth suspect coin, write 222 on it and 111 on the coin known to be good.

    Declare the left-hand scale pan as no. 1, the right-hand as no. 2 (it could be the other way about, but that seems a reasonable convention).

    In the first weighing, put all those with 1 as the first digit on scale pan 1, all those with 2 as the first digit on scale pan 2, and leave on the table those with 0 as the first digit.  Write down which pan goes down, or write 0 if they balance.  In the subsequent two weighings, repeat the procedure with the second and then the third digit position.  The three numbers we wrote down, read as a single 3-digit number, give the number of the coin that is heavier.  If there is no coin with that number, then swap 1s and 2s to give the number of the coin that is lighter.  For example, a number 210 means that coin 120 is the lighter one.  A result of 000 would mean that all coins have the same weight (though in this case one coin is known to be counterfeit).  If more than one coin is counterfeit, the method fails and one might do better to weigh each of the thirteen in turn against the good one.

    The method can be extended to 39 coins (or 40 if there is an additional one known to be good) with four weighings by extending the series to include nine successive integers starting at 9, and converting them all to 4-digit numbers in base 3.  That was the subject of Sunday Times Teaser no. 2500.  Five weighings should be enough for 120 coins (27 more integers starting with 27), and so on.

    The simplest case, of course, is three coins labelled 01, 12, 20, optionally with a fourth labelled 22 and a known-good one labelled 11, in two weighings.

    • Brian Gladman 7 April 2016 at 1:49 pm

      There are many different expositions showing how operations in the ternary (base 3) number system can be used to provide a systematic approach to their solution for aany number of coins. There is a nice overview at Cut The Knot site.

Leave a Comment

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: