On 20/02/2025 14:24, David Entwistle wrote:
On Thu, 20 Feb 2025 08:48:47 -0000 (UTC), David Entwistle wrote:
I'll try and think differently... :o)
I wouldn't have guessed, nor predicted the sequence of numbers of coins of
each denomination required to match the desired increasing monetary value.
221 matched by 221.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 11 * x^0
222 matched by 222.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 12 * x^0
223 matched by 223.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 13 * x^0
224 matched by 224.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 14 * x^0
225 matched by 225.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 0 * x^0
226 matched by 226.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 1 * x^0
227 matched by 227.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 2 * x^0
228 matched by 228.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 3 * x^0
229 matched by 229.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 4 * x^0
230 matched by 230.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 5 * x^0
Does anyone have an easy explanation why steps are jumped in the sequence
of additional coins, or is it a mistake on my part?
tldr; it's because of the base-15 nature of the solution. Put another way it's because of the "casting out 15s" process explained below, which naturally has jumps in behaviour when going over powers of 15...
-----------------------
Longish (due to worked example), but easy to follow explanation for why the solution works...
I could ask what is your x. Tobin has assumed you have it correctly as the positive solution for
x^2 + x = 15 [1].
Now we can use this to convert any number like say 8241 (chosen at random) into a set of coins using no more than 14 of each denomination. Effectively we're looking for a polynomial in x, using only integer coefficients 0 to 14. The power of x^n in the polynomial represents the coins of denomination x^n.
The secret of this is that we start by ignoring the "max 14 coins of any denomination" restriction, and then make a succession of substitutions to "cast out" multiples of 15 as they occur, using [1].
So....
8241 = 561*15 + 6 = 561*(x^2 + x) + 6
= 561x^2 + 561x + 6
...ok, so far we have the final 6 [= 6x^0], which is less than 15, and some polynomial with terms of order x^1 and higher. We can use 6 coins of denomination 1, but we're not allowed 561 coins of denomination x because 561 > 15. So we continue "casting out 15s". Note that all the steps that follow do not affect the "resolved" term 6x^0 on the right of the above equations...
= 561x^2 + (37*15 + 6)x + 6
= 561x^2 + (37*(x^2 + x) + 6)x + 6
= 561x^2 + 37x^3 + 37x^2 + 6x + 6
= 37x^3 + 598x^2 + 6x + 6
...ok now we've sorted the x^1 term as 6x^1, and 6<15 and we can move on to the 598x^2 term, and so on...
= 37x^3 + (39*15 + 13)x^2 + 6x + 6
= 37x^3 + (39*(x^2 + x) + 13)x^2 + 6x + 6
= 37x^3 + 39x^4 + 39x^3 + 13x^2 + 6x + 6
= 39x^4 + 76x^3 + 13x^2 + 6x + 6
...(x^2 term sorted, move on to 76x^3)...
= 39x^4 + (5*15 + 1)x^3 + 13x^2 + 6x + 6
= 39x^4 + (5*(x^2 + x) + 1)x^3 + 13x^2 + 6x + 6
= 39x^4 + 5x^5 + 5x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + 44x^4 + 1x^3 + 13x^2 + 6x + 6
...
= 5x^5 + (2*15 + 14)x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + (2*(x^2 + x) + 14)x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + 2x^6 + 2x^5 + 14x^4 + 1x^3 + 13x^2 + 6x + 6
= 2x^6 + 7x^5 + 14x^4 + 1x^3 + 13x^2 + 6x + 6
...and we're done. If called upon to pay 8241, we can do so with
2 coins of denomination x^6,
and 7 coins of denomination x^5,
and 14 coins of denomination x^4,
and 1 coins of denomination x^3,
and 13 coins of denomination x^2,
and 6 coins of denomination x^1,
and 6 coins of denomination x^0,
The above process is tedious, and probably I've made a miscalculation somewhere, but it's just an example to show that the "casting out 15s" approach works. Each step makes progress, sorting out the next lowest unresolved coin denomination, and clearly the steps end at some point otherwise we would be getting higher and higher powers of x cropping up. But x > 3.3 so x^n grows without bound as n increases, so at some point a single x^n coin would exceed our starting amount to be paid, which can't happen.
Note that the above process could be applied with any "similar" algebraic positive number x, with obvious adjustments. E.g. if x satisfied
x^7 + 3x^4 + 17x^3 + 4x = 41
then we could pay any whole number amount using no more than 40 coins of any denomination, by "casting out 41s".
So I suppose the maths bit of the puzzle is realising this (i.e. understanding the casting out process or something equivalent) and the puzzly bit is working out which polynomial equation x must satisfy given the constraints x > 3.3, no more than 14 coins etc.. (There's only one equation that could conceivably work!)
Hope this helps,
Mike.
MathsBombe
Re: MathsBombe