Enigmatic Code

Programming Enigma Puzzles

Enigma 1194: Only two coins

From New Scientist #2350, 6th July 2002 [link]

Harry, Tom, and I have joined the Apathy Party, which as reported in Colin Singleton‘s puzzle Enigma 1154 proposes to reduce the currency to just two denominations. We each want a currency composed of two coins, each a whole number of pence. We have each suggested which two denominations should be chosen.

We have calculated for each of the three suggestions the largest integral amount that cannot be paid exactly with any combination of the two coins, and also the largest amount that can be paid exactly by only one combination of the two coins.

In each case the answer is a two-digit number. Indeed, the largest integral amount that cannot be paid exactly by any combination of my two denominations is the same as the largest amount that can be paid exactly by only one combination of Harry’s two denominations and also the same as the largest amount that can be paid exactly by only one combination of Tom’s two denominations. (A “combination” need not include both denominations).

Harry’s denominations are different from Tom’s.

Which two denominations have I suggested?

[enigma1194]

Advertisements

3 responses to “Enigma 1194: Only two coins

  1. Jim Randell 9 November 2015 at 8:20 am

    See also Enigma 228.

    A bit of analysis (and hand-waving) gives us a quick program.

    For positive integers, a and b, with gcd(a, b) = 1, if we consider:

    F(a, b, n) = the largest integer, not expressible as a sum of multiples of a and b in n different ways.

    Then we know F(a, b, 1) is the Frobenius number of a and b:

    F(a, b, 1) = a.b − (a + b)

    I claim (without proof – although it seems intuitively reasonable):

    F(a, b, n) = n.a.b − (a + b)

    This gives rise to the following Python program, which runs in 40ms.

    from collections import defaultdict
    from enigma import irange, gcd, printf
    
    # generalised Frobenius numbers
    def F(a, b, n=1):
      return n * a * b - (a + b)
    
    # record (a, b) pairs by values
    f1s = defaultdict(list)
    f2s = defaultdict(list)
    
    # consider 1 < a < b < 100
    for b in irange(2, 99):
      for a in irange(2, b - 1):
        if gcd(a, b) > 1: continue
        f1 = F(a, b, 1)
        f2 = F(a, b, 2)
        if not(9 < f1 < f2 < 100): continue
        f1s[f1].append((a, b))
        f2s[f2].append((a, b))
        printf("[a={a} b={b}, F1={f1} F2={f2}]")
    
    # choose my pair from f1s
    for (k, Ds) in f1s.items():
      # Tom and Harry have the same k in f2s
      THs = f2s[k]
      if len(THs) > 1:
        printf("D = {Ds}, T/H = {THs}")
    

    Solution: The setter’s denominations are 3p and 20p.

    Tom and Harry’s denominations are (3, 8) and (2, 13) – in some order.

    F(3, 20, 1) = F(3, 8, 2) = F(2, 13, 2) = 37

    We should also note that F(3, 20, 2) = 97 (the largest value not expressible in 2 different ways for the setter), and F(3, 8, 1) = 13 (the largest value not expressible for Tom/Harry) and F(2, 13, 1) = 11 (the largest value not expressible for Harry/Tom), which are all 2-digit numbers as required.

    • Jim Randell 9 November 2015 at 8:26 am

      Here’s an alternative program that constructively computes F(a, b, n) (although note that the number passed as the n parameter in this case is one less than that of my previous comment). It also verifies that the computed values match the formula given above. It’s slower than the previous program (it takes 26.7s), but gives the same answer.

      from collections import defaultdict
      from enigma import irange, gcd, printf
      
      # count the number of ways to express n as i.a + j.b
      # (for non-negative integers i, j)
      def express(n, a, b):
        t = 0
        for jb in irange(0, n, step=b):
          (i, r) = divmod(n - jb, a)
          if r == 0:
            t += 1
        return t
      
      # compute generalised Frobenius Numbers of (a, b)
      # where a < b and gcd(a, b) = 1
      # return a tuple corresponding to ns where each element is the largest
      # integer expressible in n different ways, for each n in ns
      def F(a, b, *ns):
        r = dict((n, None) for n in ns)
        xs = list()
        x = 0
        while True:
          x += 1
          # look at subsequences of length a + 1
          # add in the number of ways of expressing x
          xs.append(express(x, a, b))
          if len(xs) > a:
            x0 = xs[0]
            m = min(xs[1:])
            if m > x0 and x0 in r:
              r[x0] = x - a
              if None not in r.values():
                assert all(r[n] == (n + 1) * a * b - (a + b) for n in ns)
                return tuple(r[n] for n in ns)
            xs.pop(0)
      
      # record (a, b) pairs by values
      f1s = defaultdict(list)
      f2s = defaultdict(list)
      
      # consider 1 < a < b < 100
      for b in irange(2, 99):
        for a in irange(2, b - 1):
          if gcd(a, b) > 1: continue
          (f1, f2) = F(a, b, 0, 1)
          if not(9 < f1 < f2 < 100): continue
          f1s[f1].append((a, b))
          f2s[f2].append((a, b))
          printf("[a={a} b={b}, F1={f1} F2={f2}]")
      
      # choose my pair from f1s
      for (k, Ds) in f1s.items():
        # Tom and Harry have the same k in f2s
        THs = f2s[k]
        if len(THs) > 1:
          printf("D = {Ds}, T/H = {THs}")
      
  2. Brian Gladman 10 November 2015 at 4:29 pm

    Here is a solution using my number theory library:

    from itertools import combinations
    from collections import defaultdict
    
    from number_theory import gcd, frobenius_number, frobenius_solve
    
    d1, d2 = defaultdict(list), defaultdict(list)
    for a in range(2, 100):
      for b in range(a + 1, 100):
        if gcd(a, b) == 1:
          # calculate the largest amount that cannot be 
          # made with these two coins
          fr = frobenius_number((a, b))
          if 10 <= fr < 100:      
          
            # calculate the largest amount that can be made
            # in only one way
            for f in range(150, fr, -1):
              fr_sol = list(frobenius_solve((a, b), f))
              if len(fr_sol) == 1:
                if 10 <= f < 100:
                  # only (a, b) values that give both amounts
                  # with two digits need to be considered
                  d1[fr].append((a, b))
                  d2[f].append((a, b))
                break
    
    # find my first values that are Tom/Harry's second values  
    for f in sorted(d1.keys() & d2.keys()):
      # we need two coin sets for Tom and Harry 
      if len(d2[f]) > 1:
        # my coin set 
        for m in d1[f]:
          # Tom and Harry's coin sets
          for t, h in combinations(d2[f], 2):
            fs = "Amount {}, Mine {}, <Tom|Harry> <{}|{}>"
            print(fs.format(f, m, h, t)) 
    

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: