Enigmatic Code

Programming Enigma Puzzles

Enigma 1298: Odd change

From New Scientist #2456, 17th July 2004

I have some coins in my purse whose total value is less than 1 pound sterling. I have tried to make various totals using one or more of these coins and I have discovered two interesting facts.

First, each possible total can only be achieved by one particular combination of denominations. Secondly, the number of different totals possible equals the total value of the coins in pence. If I added any number of 1 pound coins to my purse those two facts would still be true.

Current UK coins with a value less than 1 pound are 50p, 20p, 10p, 5p, 2p, and 1p.

How much money do I have in total in my purse?

Note: I am waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1298]

Advertisements

One response to “Enigma 1298: Odd change

  1. Jim Randell 27 August 2014 at 1:30 pm

    If there are n combinations and we add a pound coin there are now n combinations (without the pound coin), n combinations (with the pound coin) and the pound coin by itself, so 2n + 1 combinations.

    And if the initial amount was p pence, with the addition of the pound coin it is (100 + p) pence.

    But these are equal, so:

    2x + 1 = 100 + x
    ⇒ x = 99

    So it seems that if the problem has an answer the answer is 99p. We just need to find a combination of denominations of coins that sum to 99p that has has 99 different amounts that can be made in only one way (obviously the combinations will be all the values between 1p and 99p). One simple solution to this is 99× 1p.

    This Python 3 program looks for all combinations of coins that sum to 99p in total and can make 99 different combinations. It runs in 284ms.

    from collections import Counter
    from itertools import product
    from enigma import multiply, irange, printf
    
    T = 99
    
    # coins
    coins = (50, 20, 10, 5, 2, 1)
    
    # generate collections of coins to a certain sum
    def generate(cs, t, coins):
      if t == 0:
        yield cs
      else:
        for (i, x) in enumerate(coins):
          if not(x > t):
            yield from generate(cs + [x], t - x, coins[i:])
    
    for cs in generate([], T, coins):
      # count the different denominations
      ds = tuple(Counter(cs).items())
      # count the combinations of denominations (exclude the empty set)
      t = multiply(n + 1 for (d, n) in ds) - 1
      if t != T: continue
    
      # generate the actual combinations
      ts = set()
      for ns in product(*(irange(0, n) for (d, n) in ds)):
        s = sum(d * n for ((d, _), n) in zip(ds, ns))
        if s == 0: continue
        ts.add(s)
      # and count them
      if len(ts) != t: continue
    
      print(cs, len(cs))
    

    Solution: There is 99p in the purse.

    The program finds 18 different combinations of coins that satisfy the conditions of the problem.

    The largest number of coins is 99× 1p (99 coins).

    The smallest number of coins is 10, and there are 4 different ways of achieving this, e.g.: 1× 50p, 4× 10p, 1× 5p, 4× 1p.

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: