Sunday Times Teaser 3159 – King Coin
by Mark Valentine
Published Sunday April 09 2023 (link)
The new King’s currency has 64 Minims (circular coins) per Suttas (notes). Each coin’s value is proportional to its face area, and is a whole number of cm in diameter, starting with 1 cm for 1 Minim.
The King only wanted denominations such that his citizens can pay any amount below 1 Suttas using no more than a certain number of coins for the transaction. This number is the smallest possible, given the above conditions. His mint suggested that if just two values could require an extra coin, they could reduce the number of denominations needed. The King agreed and placed one of each minted denomination flat and face up in a rectangular display, with each coin’s edge resting along the display’s base. The order of the coins minimised the width of the display, with the smallest coin to the right of the centre.
What are the diameters in cm, from left to right?
I needed to see Jim’s solution to understand the puzzle.
My program doesn’t support multiple adjacent coins which can be minimized (the diameters don’t differ enough for this)
A simpler formula for r (in miminize function) is (a * b) / (sqrt(a) + sqrt(b))^2
While my intermediate results are the same as Brians my final dsiplay line-up is different. I can’t figure out why. Any ideas?
Hi John, your width variable ndw is sometimes too small. In your final solution the 4th coin may not be considered in the width as it fits in the gap between the 3rd and 5th coin (without adding to the total width). I have written a minimize function for such cases.
For a picture see:
You are assuming (as I also did initially) that adjacent coins are touching. But if a small coin sits between two larger coins, it can be the two larger coins that touch each other leaving the smaller coin free to move left or right to touch one or the other of them.
Interestingly, finding the minimum width of the arrangement for a given set of coin radii is a much harder task than it seems at first and requires checking as the coins are placed (say left to right) which of the already placed coins will be the one that will touch the next one to be placed. I ‘cheated’ and used the algorithm found by Jim Randell.
See this picture
Thanks, I should have realized that. Here is my revised code including a recursive function to eliminate ‘interstitial’ circles. It is not designed to deal with ‘complete overhang’ which is precluded by the circle sizes in this teaser.