Enigmatic Code

Programming Enigma Puzzles

Enigma 1129: Minimal change

From New Scientist #2285, 7th April 2001 [link]

The coins from 1p to 100p in circulation are for 1p, 2p, 5p, 10p, 20p, 50p and 100p. If one receives 40p in change for a purchase it can be paid in a minimum of 2 coins (20p + 20p) but could be paid in one coin more than that minimum number (20p + 10p + 10p). But a few amounts of change cannot be paid for in one coin more than the minimum possible number of coins, for instance 1p and 50p.

Harry, Tom and I each paid 100p for an item priced such that the change due could not be paid in one coin more than the minimum possible number of coins. Each item cost a different amount.

Next day Harry and Tom bought the same items at the same price as on the previous day, whereas I bought a different item at a different price from any of the others, which again was such that the change due from 100p could not be paid in one coin more than the minimum possible number of coins. Each day the total cost of the three purchases was a prime number of pence.

How much did each of my purchases cost?

[enigma1129]

Advertisements

2 responses to “Enigma 1129: Minimal change

  1. Jim Randell 6 February 2017 at 8:08 am

    This Python program runs in 42ms.

    from itertools import combinations
    from enigma import irange, Primes, diff, cached, printf
    
    # can amount <t> be made from <n> coins in <ds>
    @cached
    def make(t, n, ds):
      # amounts we can make from 1 coin
      if n == 1: return (t in ds)
      # otherwise use a coin less than t
      return any(make(t - d, n - 1, ds) for d in ds if d < t)
    
    # denominations to use
    denominations = (1, 2, 5, 10, 20, 50, 100)
    
    # consider values less than 100p
    vs = list()
    for v in irange(1, 99):
      # find the minimum number of coins required
      for m in irange(1, v):
        if make(v, m, denominations):
          # record values that can't be done using m + 1 coins
          if not make(v, m + 1, denominations):
            printf("[{v} -> {m}]")
            vs.append(v)
          break
    
    printf("[vs = {vs}]")
    
    # possible prices of items
    ps = list(100 - v for v in vs)
    
    # primes up to 300
    primes = Primes(300)
    
    # choose item amounts for D on the two days (in some order)
    for (D1, D2) in combinations(ps, 2):
      # choose item amounts for H, T (in some order)
      for (H, T) in combinations(diff(ps, [D1, D2]), 2):
        # item total on both days is prime
        if not(H + T + D1 in primes and H + T + D2 in primes): continue
        printf("D1={D1} D2={D2} [H/T={H}/{T}]")
    

    Solution: The purchases cost 49p and 95p.

    There are only 4 change values (below 100p) that meet the criteria of the puzzle: 1p, 5p, 50p, 51p, 55p.

    Harry and Tom’s purchases cost 45p and 99p, so the total cost of the purchases on the two days were 193p and 239p.

  2. Brian Gladman 6 February 2017 at 2:49 pm
    from itertools import combinations
    from bisect import bisect
    
    coins = (1, 2, 5, 10, 20, 50, 100)
    
    # simple prime detection up to 360
    pr = {2, 3, 5, 7, 11, 13, 17}
    def is_prime(x):
      return x in pr or x > 18 and all(x % p for p in pr)
    
    # find the minimum number of coins to make <change>
    def min_coins(change, coins):
      cns = []
      while change:
        c = coins[bisect(coins, change) - 1]
        cns += [c]
        change -= c
      return cns
    
    # find whether <change> can be made with <n> coins
    def make(change, n, coins):
      if n == 1:
        return change in coins
      else:
        for c in coins:
          if c < change and make(change - c, n - 1, coins):
            return True
        else:
          return False
    
    # find items that can be bought when change cannot be
    # provided with one more coin than the minimum possible 
    item_costs = []
    for change in range(1, 100):
      nbr = len(min_coins(change, coins))
      if not make(change, nbr + 1, coins):
        item_costs += [100 - change]
    
    # look for combinations of three items from those identified for 
    # which their sum is prime
    triples = [t for t in combinations(item_costs, 3) if is_prime(sum(t))]
    
    # look for pairs of triples that share two items
    for t1, t2 in combinations(triples, 2):
      ins = set(t1).intersection(t2)
      if len(ins) == 2:
        # and extract the items that are not shared
        a, b = sorted((*set(t1).difference(ins), *set(t2).difference(ins)))
        print('{}p and {}p.'.format(a, b))
    

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: