Enigmatic Code

Programming Enigma Puzzles

Enigma 998: Multiple purchases

From New Scientist #2153, 26th September 1998

The denominations of coins in circulation which are less than a pound are 50, 20, 10, 5, 2 and 1p.

Harry, Tom and I went into a shop recently and each made a purchase costing less than £1 (100p). The cost of each of these purchases was different. We each paid with a £1 coin and each received four coins in change — in each case the change due could not be given in fewer than four coins; but equally if we had paid the exact price for our purchases it would have been possible for each of us to have done so with four coins, but not with fewer.

The total cost of our three purchases was not only more than, but also an exact multiple of, the total amount of change than between us we received.

What did each of our purchases cost?

[enigma998]

One response to “Enigma 998: Multiple purchases

  1. Jim Randell 9 August 2019 at 8:58 am

    This Python program finds the amounts that are expressible using exactly 4 coins but no fewer, and then finds three of these amounts that satisfy the remaining conditions.

    It runs in 94ms.

    Run: [ @repl.it ]

    from enigma import subsets, div, printf
    
    # denominations of coins
    coins = [ 1, 2, 5, 10, 20, 50 ]
    
    # amounts expressible using k coins
    f = lambda k: set(t for t in map(sum, subsets(coins, size=k, select='R')) if t < 100)
    
    # find amounts that require 4 coins
    t4s = f(4).difference(f(1), f(2), f(3))
    
    # looks for amounts where the change is also in the list
    ts = list(t for t in t4s if 100 - t in t4s)
    
    # choose 3 prices for T, D, H
    for costs in subsets(ts, size=3, select='C'):
      # total is a multiple of the change
      t = sum(costs)
      m = div(t, 300 - t)
      if m is None or m < 2: continue
      # output solution
      printf("costs = {costs} [total cost = {t}, total change = {x}]", x=300 - t)
    

    Solution: The purchases cost 37p, 81p, 82p.

    37p = 20p + 10p + 5p + 2p; change = 63p = 50p + 10p + 2p + 1p
    81p = 50p + 20p + 10p + 1p; change = 19p = 10p + 5p + 2p + 2p
    82p = 50p + 20p + 10p + 2p; change = 18p = 10p + 5p + 2p + 1p

    Total cost = 200p; Total change = 100p

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: