### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,818 hits

Advertisements

Programming Enigma Puzzles

15 August 2016

Posted by on **From New Scientist #2310, 29th September 2001** [link]

After the Apathy Party swept into power in the General Election, George, its founder, realised one of the hazards of government: impractical proposals are liable to become law because no one has properly assessed the consequences. The latest is so bizarre that even the Apathy Party must reject it?

The Chancellor of the Exchequer thinks it would be fun to abolish the current coinage and mint just one denomination of coin and one of note. He has proposed an absurd pair of values, each a whole number of pence. George realises that although a large sum of money, such as £999.99, can be paid exactly in several different ways, there are precisely 10,000 amounts that can each be paid exactly using only one combination of the proposed notes and coins. Worse, there is a smaller, but still substantial, number of amounts that cannot be paid exactly using any combination of one or both of the denominations.

How many different amounts cannot be paid exactly?

See also **Enigma 1194**.

Thanks to Hugh Casement for providing a transcript for this puzzle.

[enigma1154]

Advertisements

%d bloggers like this:

See also:

Enigma 228.If there are two denominations

aandb, then any amount made using combinations of those denominations must be a multiple ofgcd(a, b). So for there to a be a finite number of amounts that are not possible to make we requiregcd(a, b) = 1. (For example, if bothaandbwere even it would be impossible to make any odd amount using combinations ofaandb.This kind of problem is known as a

Coin Changing Problem(alsoFrobenius Coin ProblemorSylvester Coin Problem).There are some useful results for the coin problem with two denominations that makes it quite easy to solve this particular puzzle:

For two denominations

aandb, wheregcd(a, b) = 1, if we consider positive integersnthat can be expressed as:Then, an integer

nisk-expressible if there are exactlykdifferent ways to of expressing it.We have the following results:

(1) The largest non-expressible integer is given by:

This is known as the

Frobenius Numberofaandb.In fact, the largest integer that is not expressible in k-different ways is given by:

And so

F(a, b) = F[1](a, b).(2a) The total number of non-expressible integers (or 0-expressible integers) is given by:

(2b) The total number of integers that have a unique expression (i.e. only one way of expressing them, or 1-expressible integers) is given by:

(2c) The total number of

k-expressible integers, fork ≥ 2is given by:All these results (and more) can be found in the paper:

“An extension of the Frobenius coin-exchange problem”, Mathias Beck and Sinai Robins [ https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Beck/Beck5.pdf ].We can use these results to attack this problem as follows:

We are told there are exactly 10000 amounts that are 1-expressible. So:

But there are only two ways to factor 10001, namely 1×10001 and 73×137.

If a denomination of 1 is available then any integer amount can be made, so it follows that the proposed denominations are 73 and 137.

From this we can calculate the number of 0-expressible amounts:

And this is the number of amounts that cannot be paid exactly.

Solution:There are 4896 amounts that cannot be paid exactly.This Python program calculates

N0(andN2+) givenN1. It solves the problem in 50ms.For comparison, the following Python program uses no analysis and constructively tries co-prime currency denominations until if finds a pair with

N1 = 10000, and0 < N0 < N1.It takes 14m25s to solve the problem, so there is some advantage to having done a bit of analysis.

Of course the run time is heavily dependent on the order in which the coprime pairs are generated by the

coprime_pairs()routine. In this instance (73, 137) is the 16,481st pair returned.