Teaser 1858: Cash flow
From The Sunday Times, 26th April 1998 [link]
We play a variation of a famous puzzle game using coins instead of rings. We start with a pile of coins consisting of at least one of each of the 1p, 2p, 5p, 10p, 20p, 50p and £1 coins, with no coin on top of another that is smaller in diameter. So the 5p coins are on the top, then the 1p, 20p, £1, 10p, 2p and 50p coins respectively, with the 50p coins being on the bottom. One typical pile is illustrated:
The object of the game is to move the pile to a new position one coin at a time. At any stage there can be up to three piles (in the original position, the final position, and one other). But in no pile can any coin ever be above another of smaller diameter.
We did this with a pile of coins recently and we found that the minimum number of moves needed equalled the value of the pile in pence. We then doubled the number of coins by adding some 1p, 5p and 50p coins totalling less than £3, and we repeated the game. Again the minimum number of moves equalled the value of the new pile in pence.
How many coins were in the pile for the first game?
This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.
[teaser1852]
Frits are discussing. 
GeoffR and 
John Crabtree and 
Lise Andreasen and 
S2T2 
Jim Randell 8:46 am on 30 August 2020 Permalink |
(See also: Enigma 1254, Enigma 14).
In a standard Towers of Hanoi problem there are n discs of different sizes.
In the optimal solution the largest disc is moved 1 time, the next largest 2 times, then 4 times, 8 times, 16 times, …
So we get a total number of moves: H(n) = 2^n − 1.
In this version there are multiple discs the same size, but we can treat a block of k discs the same size as a single disk that requires k moves, and solve the puzzle in the same way.
So, the stack shown in the diagram (which I denote (1, 2, 1, 1, 3, 1, 1), by counting the number of coins of each size, starting at the bottom), will require: 1×1 + 2×2 + 1×4 + 1×8 + 3×16 + 1×32 + 1×64 = 161 moves.
In general if there number of coins of each size is (A, B, C, D, E, F, G) then the number of moves is:
and the monetary value of the coins is:
and if these values are equal, we get:
In the puzzle, the number of coins is doubled by increasing A by a, F by f, G by g, and their monetary value is less than £3:
but the monetary value of the augmented stack is still equal to the number of moves required, so:
We can work out possible values for a, f, g, and their sum gives us the initial number of coins (which is the answer to the puzzle).
We can then look for stacks of coins of this size with the monetary value and number of moves, and then add the extra coins to the stack and see if the condition still holds.
This Python 3 program runs in 54ms.
Run: [ @replit ]
from enigma import (irange, div, printf) # denominations of coins by size (largest diameter to smallest diameter) ds = (50, 2, 10, 100, 20, 1, 5) # number of moves for sequence of discs (largest to smallest) def H(ns): t = 0 m = 1 for n in ns: t += m * n m *= 2 return t # decompose <t> into <k> positive numbers def decompose(t, k, s=[]): if k == 1: yield s + [t] else: for x in irange(1, t + 1 - k): yield from decompose(t - x, k - 1, s + [x]) # choose a value for a (= 50p, so there must be 1-5) for a in irange(1, 5): # choose a value for g (= 5p) for g in irange(1, (299 - 50 * a) // 5): # calculate f f = div(49 * a - 59 * g, 31) if f is None or f < 1 or not(50 * a + 5 * g + f < 300): continue # the total number of extra coins = the number of original coins n = a + f + g # output solution printf("n={n} [a={a} f={f} g={g}]") # allocate the number of original coins (n in total) for ns in decompose(n, 7): # calculate the total value of the stack t = sum(n * d for (n, d) in zip(ns, ds)) # calculate the number of moves for the stack m = H(ns) if m != t: continue # make the final stack ns2 = list(ns) ns2[0] += a ns2[5] += f ns2[6] += g # calculate the total value of the stack t2 = sum(n * d for (n, d) in zip(ns2, ds)) # output solution printf("-> {ns} [{t}] -> {ns2} [{t2}]")Solution: There were 12 coins in the original pile.
There is only one possible size for the original pile, and it must be composed of: (2× 50p, 1× 2p, 1× 10p, 1× £1, 3× 20p, 1× 1p, 3× 5p), making a total value of 288p and requiring 288 moves.
We then add: (5× 50p, 6× 1p, 1× 5p) = 261p to make a pile with total value 549p and requiring 549 moves.
LikeLike