Enigmatic Code

Programming Enigma Puzzles

Enigma 1154: Funny money

From New Scientist #2310, 29th September 2001 [link]

After the Apathy Party swept into power in the General Election, George, its founder, realised one of the hazards of government: impractical proposals are liable to become law because no one has properly assessed the consequences. The latest is so bizarre that even the Apathy Party must reject it?

The Chancellor of the Exchequer thinks it would be fun to abolish the current coinage and mint just one denomination of coin and one of note. He has proposed an absurd pair of values, each a whole number of pence. George realises that although a large sum of money, such as £999.99, can be paid exactly in several different ways, there are precisely 10,000 amounts that can each be paid exactly using only one combination of the proposed notes and coins. Worse, there is a smaller, but still substantial, number of amounts that cannot be paid exactly using any combination of one or both of the denominations.

How many different amounts cannot be paid exactly?

See also Enigma 1194.

Thanks to Hugh Casement for providing a transcript for this puzzle.

[enigma1154]

Advertisements

One response to “Enigma 1154: Funny money

  1. Jim Randell 15 August 2016 at 8:45 am

    See also: Enigma 228.

    If there are two denominations a and b, then any amount made using combinations of those denominations must be a multiple of gcd(a, b). So for there to a be a finite number of amounts that are not possible to make we require gcd(a, b) = 1. (For example, if both a and b were even it would be impossible to make any odd amount using combinations of a and b.

    This kind of problem is known as a Coin Changing Problem (also Frobenius Coin Problem or Sylvester Coin Problem).

    There are some useful results for the coin problem with two denominations that makes it quite easy to solve this particular puzzle:

    For two denominations a and b, where gcd(a, b) = 1, if we consider positive integers n that can be expressed as:

    n = (i × a) + (j × b) for non-negative integers i, j

    Then, an integer n is k-expressible if there are exactly k different ways to of expressing it.

    We have the following results:

    (1) The largest non-expressible integer is given by:

    F(a, b) = (a × b) − (a + b)

    This is known as the Frobenius Number of a and b.

    In fact, the largest integer that is not expressible in k-different ways is given by:

    F[k](a, b) = k × (a × b) − (a + b)

    And so F(a, b) = F[1](a, b).

    (2a) The total number of non-expressible integers (or 0-expressible integers) is given by:

    N[0](a, b) = (a − 1) × (b − 1) / 2

    (2b) The total number of integers that have a unique expression (i.e. only one way of expressing them, or 1-expressible integers) is given by:

    N[1](a, b) = (a × b) − 1

    (2c) The total number of k-expressible integers, for k ≥ 2 is given by:

    N[k](a, b) = (a × b)

    All these results (and more) can be found in the paper: “An extension of the Frobenius coin-exchange problem”, Mathias Beck and Sinai Robins [ https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Beck/Beck5.pdf ].

    We can use these results to attack this problem as follows:

    We are told there are exactly 10000 amounts that are 1-expressible. So:

    N[1](a, b) = (a × b) − 1 = 10000
    ⇒ a × b = 10001

    But there are only two ways to factor 10001, namely 1×10001 and 73×137.

    If a denomination of 1 is available then any integer amount can be made, so it follows that the proposed denominations are 73 and 137.

    From this we can calculate the number of 0-expressible amounts:

    N[0](a, b) = (a − 1) × (b − 1) / 2 = 72 × 136 / 2 = 4896

    And this is the number of amounts that cannot be paid exactly.

    Solution: There are 4896 amounts that cannot be paid exactly.

    This Python program calculates N0 (and N2+) given N1. It solves the problem in 50ms.

    from enigma import divisor_pairs, gcd, printf
    
    # if the denominations are (a, b) and we consider amounts n that can be
    # expressed as:
    #   n = i.a + j.b (for non-negative i, j)
    #
    # the number of amounts with no expression is:
    #   N0(a, b) = (a - 1)(b - 1)/2
    #
    # the number of amounts with a unique expression is:
    #   N1(a, b) = ab - 1
    
    import sys
    argv = sys.argv[1:]
    
    # the N1 value we are interested in
    N1 = (10000 if len(argv) < 1 else int(argv[0]))
    
    # find possible denominations (a, b)
    for (a, b) in divisor_pairs(N1 + 1):
      if gcd(a, b) != 1: continue
      # calculate N0(a, b)
      N0 = (a - 1) * (b - 1) // 2
      printf("a={a} b={b} N0={N0} N1={N1} N2+={N2}", N2=a * b)
    

    For comparison, the following Python program uses no analysis and constructively tries co-prime currency denominations until if finds a pair with N1 = 10000, and 0 < N0 < N1.

    from itertools import count
    from enigma import irange, coprime_pairs, printf
    
    # count the number of ways to express t as i.a + j.b
    # (for non-negative integers i, j)
    def express(t, a, b):
      n = 0
      for jb in irange(0, t, step=b):
        (i, r) = divmod(t - jb, a)
        if r == 0:
          n += 1
      return n
    
    # is the number of 1-expressible exactly N1?
    # return None (if it isn't) or the number of numbers that cannot be expressed (if it is)
    def check(a, b, N1):
      # n0 = number of 0-expressible amounts
      # n1 = number of 1-expressible amounts
      # c2 = number of consecutive amounts 2+-expressible amounts
      n0 = n1 = c2 = 0
      for i in count(1):
        n = express(i, a, b)
        if n == 0:
          n0 += 1
        if n == 1:
          n1 += 1
          if n1 > N1: return None
          c2 = 0
        elif n > 1:
          c2 += 1
          if c2 == a: break
      return (n0 if n1 == N1 else None)
    
    
    # the number of 1-expressible amounts we are looking for
    N1 = 10000
    
    # consider possible denominations
    for (a, b) in coprime_pairs():
      # is the number of 1-expressible amounts equal to N1?
      # if it is determine N0, the number of 0-expressible amounts
      N0 = check(a, b, N1)
      if N0 is not None and 0 < N0 < N1:
        printf("N0={N0} a={a} b={b}")
        exit()
    

    It takes 14m25s to solve the problem, so there is some advantage to having done a bit of analysis.

    Of course the run time is heavily dependent on the order in which the coprime pairs are generated by the coprime_pairs() routine. In this instance (73, 137) is the 16,481st pair returned.

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: