### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

9 November 2015

Posted by on **From New Scientist #2350, 6th July 2002** [link]

Harry, Tom, and I have joined the Apathy Party, which as reported in Colin Singleton‘s puzzle

Enigma 1154proposes to reduce the currency to just two denominations. We each want a currency composed of two coins, each a whole number of pence. We have each suggested which two denominations should be chosen.We have calculated for each of the three suggestions the largest integral amount that

cannotbe paid exactly with any combination of the two coins, and also the largest amount thatcanbe paid exactly by only one combination of the two coins.In each case the answer is a two-digit number. Indeed, the largest integral amount that

cannotbe paid exactly by any combination of my two denominations is the same as the largest amount thatcanbe paid exactly by only one combination of Harry’s two denominations and also the same as the largest amount thatcanbe paid exactly by only one combination of Tom’s two denominations. (A “combination” need not include both denominations).Harry’s denominations are different from Tom’s.

Which two denominations have I suggested?

[enigma1194]

Advertisements

%d bloggers like this:

See also

Enigma 228.A bit of analysis (and hand-waving) gives us a quick program.

For positive integers,

aandb, withgcd(a, b) = 1, if we consider:Then we know

F(a, b, 1)is theFrobenius numberofaandb:I claim (without proof – although it seems intuitively reasonable):

This gives rise to the following Python program, which runs in 40ms.

Solution:The setter’s denominations are 3p and 20p.Tom and Harry’s denominations are (3, 8) and (2, 13) – in some order.

F(3, 20, 1) = F(3, 8, 2) = F(2, 13, 2) = 37We should also note that

F(3, 20, 2) = 97(the largest value not expressible in 2 different ways for the setter), andF(3, 8, 1) = 13(the largest value not expressible for Tom/Harry) andF(2, 13, 1) = 11(the largest value not expressible for Harry/Tom), which are all 2-digit numbers as required.Here’s an alternative program that constructively computes

F(a, b, n)(although note that the number passed as thenparameter in this case is one less than that of my previous comment). It also verifies that the computed values match the formula given above. It’s slower than the previous program (it takes 26.7s), but gives the same answer.Here is a solution using my number theory library: