S2T2

Jim Randell 4:41 pm on 6 May 2019 Permalink Reply
Tags: by: Graham Smithers ( 82 )   

• 

  Jim Randell 4:42 pm on 6 May 2019 Permalink | Reply

  We know there is at least one of each denomination of coin. So that is 1/2 + 1 + 3 + 6 + 12 + 24 + 30 = 76.5d accounted for, leaving us only 43.5d to worry about, and we need to make this amount from quantities that are 1 less than a perfect square.

  It turns out there are 6 different ways to achieve this. Five of them use 3 different quantities, the sixth way uses 4 different quantities, and gives us the solution.

  This Python 3 program runs in 73ms.

  Run: [ @repl.it ]

  from enigma import (defaultdict, isqrt, irange, arg, printf)
  
  # express total <t> using denominations <ds>, quantities <qs>
  def express(t, ds, qs, s=[]):
    if t == 0:
      if not ds:
        yield s
      elif 0 in qs:
        yield s + [0] * len(ds)
    elif ds:
      d = ds[0]
      for i in qs:
        if d * i > t: break
        yield from express(t - d * i, ds[1:], qs, s + [i])
  
  # denominations of coins (in half-pennies)
  coins = (1, 2, 6, 12, 24, 48, 60)
  
  # total amount (of half-pennies)
  T = arg(240, 0, (lambda x: int(2 * float(x))))
  printf("[T={T}(1/2)d]")
  
  # subtract one of each coin from the total
  t = T - sum(coins)
  
  # squares - 1 (up to t)
  squares1 = list(i * i - 1 for i in irange(1, isqrt(t)))
  
  # collect results by how many different quantities there are
  r = defaultdict(list)
  
  # consider ways to express t using (i^2 - 1) quantities
  for qs in express(t, coins, squares1):
    # record result by the numbers of different quantities
    k = len(set(qs))
    printf("[{qs} -> {k} values]")
    r[k].append(qs)
  
  # look for keys with unique values
  for (k, vs) in r.items():
    if len(vs) == 1:
      # include the first coin of each denomination
      qs = list(n + 1 for n in vs[0])
      # output quantities and denominations (in half-pennies)
      printf("{k} values -> {T}(d/2) = {qs} x {coins}(d/2)")
  

  Solution: The numbers of coins in the piles (from half-crowns down to half-pennies) are: 1, 1, 1, 4, 1, 9, 36.

  LikeLike

  • 

    Frits 3:36 pm on 5 June 2024 Permalink | Reply

    “The cashier set out the coins in separate piles”.

    I understand you have assumed that the cashier made 7 piles per denomination. I would also have considered fi 4four piles (with 4, 4, 36 and 196 coins).

    LikeLike

    • 

      Jim Randell 5:02 pm on 5 June 2024 Permalink | Reply

      @Frits: My natural interpretation was that each denomination is in a separate pile, so there is (exactly) one pile per denomination.

      LikeLike

• 

  GeoffR 9:26 pm on 6 May 2019 Permalink | Reply

  % A Solution in MiniZinc
  include "globals.mzn";
  
  % HP = No. HalfPennies, P3 = No. Threepence, P6 = No. Sixpence....
  var 1..150:HP; var 1..100:P; var 1..40:P3; var 1..20:P6;     
  var 1..10:SH; var 1..5:FL; var 1..4:HC; 
  
  % even number of half-pennies needed to make 120p
  constraint HP mod 2 == 0;  
  
  % the number of coins in each pile was a square
  set of int: sq = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
  
  % all types of coins are squares
  constraint HP in sq /\ P in sq /\ P3 in sq /\ P6 in sq
  /\ SH in sq /\ FL in sq /\ HC in sq;
  
  % number of coins/types to make 120p 
  constraint HP * 1 div 2 + P*1 + P3*3  + P6*6 + SH*12 
  + FL*24 + HC*30 == 120;
  
  var set of int: coins = {HP, P, P3, P6, SH, FL, HC};
  
  solve satisfy;
  output [ show([HP,P,P3,P6,SH,FL,HC]) ++ "  " ++ show(coins) ];
  
  % [HP, P, P3,P6,SH,FL,HC] Set of Coins
  % ------------------------------------ 
  % [64, 4, 4, 1, 1, 1, 1]  {1,4,64}
  % [4, 25, 1, 4, 1, 1, 1]  {1,4,25}
  % [4, 16, 4, 4, 1, 1, 1]  {1,4,16}
  % [4, 1, 9, 4, 1, 1, 1]  {1,4,9}
  % [36, 9, 1, 4, 1, 1, 1]  {1,4,9,36} << only set of 4 coin types
  % [16, 1, 1, 1, 4, 1, 1]  {1,4,16}
  % ==========
  % Answer: 1 Half Crown, 1 Florin, 1 Shilling, 4 Sixpence
  % 1 Threepence, 9 Pennies and 36 HalfPennies
  
  
  

  LikeLike