If you like mathematical problems and puzzles...

"MathsBombe is aimed at students up to Year 13 (England and Wales), S6 (Scotland), Year 14 (Northern Ireland). You don't need to be a computer
whizz or a mathematical genius — you just need to keep your wits about you and be good at solving puzzles!"

Starts 16:00 GMT, 22nd January, 2025.

https://www.maths.manchester.ac.uk/mathsbombe/

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Sun, 19 Jan 2025 19:57:26 -0000 (UTC), David Entwistle wrote:

"MathsBombe is aimed at students up to Year 13 (England and Wales), S6 (Scotland), Year 14 (Northern Ireland). You don't need to be a computer
whizz or a mathematical genius — you just need to keep your wits about
you and be good at solving puzzles!"

Starts 16:00 GMT, 22nd January, 2025.

https://www.maths.manchester.ac.uk/mathsbombe/

Please don't post a direct answer to the question posed, but I'd welcome a
bit of guidance on Mathsbombe question 3.

When I look at the question, my reaction is "that doesn't look possible".
The "any positive integer cost can be paid" part of the question seems problematic. Am I misreading, or misunderstanding the question?

Thanks,
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/02/2025 09:40, David Entwistle wrote:

On Sun, 19 Jan 2025 19:57:26 -0000 (UTC), David Entwistle wrote:

"MathsBombe is aimed at students up to Year 13 (England and Wales), S6
(Scotland), Year 14 (Northern Ireland). You don't need to be a computer
whizz or a mathematical genius — you just need to keep your wits about
you and be good at solving puzzles!"

Starts 16:00 GMT, 22nd January, 2025.

https://www.maths.manchester.ac.uk/mathsbombe/

Please don't post a direct answer to the question posed, but I'd welcome a bit of guidance on Mathsbombe question 3.

When I look at the question, my reaction is "that doesn't look possible".
The "any positive integer cost can be paid" part of the question seems problematic. Am I misreading, or misunderstanding the question?

I agree; it doesn't look possible. I was tempted to cut code, but
I hit two ambiguities. What, precisely, does "no more than 14
coins of every given denomination" mean? It could mean an
up-to-14-coin subset of the available range, or up to 14
totapennies PLUS up to 14 totatuppences PLUS up to 14
totathruppences and so on ad nauseam. And what does "any positive
integer" mean? Does it, for example, include bloodybignumber? If
so, how about bloodybignumber factorial?

I don't care enough, I'm afraid, but if I *did*, then having
resolved those dilemmae, I would probably look at brute forcing a
few thousand candidate x's (3.0000, 3.0001, 3.0002, 3.0003 etc)
and then try to spot a pattern.

I would also look for tricks, eg i.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/02/2025 10:13, Richard Heathfield wrote:

On 09/02/2025 09:40, David Entwistle wrote:

On Sun, 19 Jan 2025 19:57:26 -0000 (UTC), David Entwistle wrote:

"MathsBombe is aimed at students up to Year 13 (England and Wales), S6
(Scotland), Year 14 (Northern Ireland). You don't need to be a computer
whizz or a mathematical genius � you just need to keep your wits about
you and be good at solving puzzles!"

Starts 16:00 GMT, 22nd January, 2025.

https://www.maths.manchester.ac.uk/mathsbombe/

Please don't post a direct answer to the question posed, but I'd welcome a >> bit of guidance on Mathsbombe question 3.

When I look at the question, my reaction is "that doesn't look possible".
The "any positive integer cost can be paid" part of the question seems
problematic. Am I misreading, or misunderstanding the question?

I don't instantly see why it would be impossible. It looks at least plausible to me. The x^k coins
go on without limit, so even for big numbers there will be big coins available for payment.

I agree; it doesn't look possible. I was tempted to cut code, but I hit two ambiguities. What,
precisely, does "no more than 14 coins of every given denomination" mean? It could mean an
up-to-14-coin subset of the available range, or up to 14 totapennies PLUS up to 14 totatuppences
PLUS up to 14 totathruppences and so on ad nauseam.

I agree that could be clearer. I read it as your second interpretation. If your first
interpretation were intended, wouldn't they just say "no more that 14 coins" and leave it at that?
[Plus I strongly suspect the first interpretation would indeed be impossible.]

And what does "any positive integer" mean? Does
it, for example, include bloodybignumber? If so, how about bloodybignumber factorial?

That's surely easy - it means any positive integer, integers being whole number like 1,2,3,4,...
There is no limit to how big integers get! Also there's no limit to how big the coin values x^k get
as k grows.

I don't care enough, I'm afraid, but if I *did*, then having resolved those dilemmae, I would
probably look at brute forcing a few thousand candidate x's (3.0000, 3.0001, 3.0002, 3.0003 etc) and
then try to spot a pattern.

That seems like a dead end - you will just be plagued by issues of rounding errors. You are not
"seeing the problem" in the right way :)

I would also look for tricks, eg i. >

i is not greater than 3.3, and neither is 4i etc.. x > 3.3 entails x being a real number...

I have not yet attempted to solve the problem, but as a BIG starter, if x were transcendental (like
Pi), how could 15 be paid...?

Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/02/2025 11:57, Mike Terry wrote:

<snip>

And what does "any positive integer" mean? Does it, for
example, include bloodybignumber? If so, how about
bloodybignumber factorial?

That's surely easy - it means any positive integer, integers
being whole number like 1,2,3,4,... There is no limit to how big
integers get!  Also there's no limit to how big the coin values
x^k get as k grows.

But these are actual minted coins, so there must be a finite
number of them, yes? Or does the government mint new coins for
every transaction? Really?

I don't care enough, I'm afraid, but if I *did*, then having
resolved those dilemmae, I would probably look at brute forcing
a few thousand candidate x's (3.0000, 3.0001, 3.0002, 3.0003
etc) and then try to spot a pattern.

That seems like a dead end - you will just be plagued by issues
of rounding errors.  You are not "seeing the problem" in the
right way :)

But the right answer is expressed to 4dp when submitted.

I would also look for tricks, eg i. >

i is not greater than 3.3, and neither is 4i etc..  x > 3.3
entails x being a real number...

3.3i then, or whatever. Besides, it was just an aside.

I have not yet attempted to solve the problem, but as a BIG
starter, if x were transcendental (like Pi), how could 15 be
paid...?

Presumably we're looking at a variation of e^i.pi = -1

But let us say that you can pay 15 with your x, whatever it might
turn out to be, we then have to show that you can WITH THE SAME X
pay 15!, 15!!, 15!!! etc - using no more than 14 coins of any
denomination.

I'm still not finding it plausible.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Sun, 9 Feb 2025 09:40:20 -0000 (UTC), David Entwistle wrote:

When I look at the question, my reaction is "that doesn't look
possible".

I suspect that is a defence mechanism I've evolved to have - "that looks difficult" - assume it is impossible and so avoid doing any work
associated with anything difficult.

The question was posed by University of Manchester mathematicians and
answered to their satisfaction a day after the problem was posed. So, I
should assume it is solvable. There was clearly a bit of to-ing and fro-
ing, but they settled on a solution, which suggests it is not trivial and thereby all the more interesting.
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/02/2025 15:03, Richard Heathfield wrote:

On 09/02/2025 11:57, Mike Terry wrote:

<snip>

And what does "any positive integer" mean? Does it, for example, include bloodybignumber? If so,
how about bloodybignumber factorial?

That's surely easy - it means any positive integer, integers being whole number like 1,2,3,4,...
There is no limit to how big integers get!� Also there's no limit to how big the coin values x^k
get as k grows.

But these are actual minted coins, so there must be a finite number of them, yes? Or does the
government mint new coins for every transaction? Really?

It's a puzzle. If you like, you could assume that the mint will manufacture as many coins as
required, but, dude, IT'S A *MATHS PROBLEM* not a manufacturing problem. :)

I don't care enough, I'm afraid, but if I *did*, then having resolved those dilemmae, I would
probably look at brute forcing a few thousand candidate x's (3.0000, 3.0001, 3.0002, 3.0003 etc)
and then try to spot a pattern.

That seems like a dead end - you will just be plagued by issues of rounding errors.� You are not
"seeing the problem" in the right way :)

But the right answer is expressed to 4dp when submitted.

Yes, that's just to confirm the puzzler has found the correct solution. (The actual solution will
have infinitely many digits, but the puzzle setters cannot ask puzzlers to enter infinitely many
digits. You might say that there is a chance that the puzzler has somehow got the wrong answer, but
it just happened to match to 4dp. That is correct but unlikely.)

I would also look for tricks, eg i. >

i is not greater than 3.3, and neither is 4i etc..� x > 3.3 entails x being a real number...

3.3i then, or whatever. Besides, it was just an aside.

I have not yet attempted to solve the problem, but as a BIG starter, if x were transcendental
(like Pi), how could 15 be paid...?

Presumably we're looking at a variation of e^i.pi = -1

No, x is a real number greater than 3.3.

IF x were transcendental, then no combination of non-unit coins could sum to an integer. (That's
effectively what "transcendental" amounts to.) So the only way to pay 15 would be with 15 unit
coins, which is not allowed by the problem. So x CANNOT be transcendental! (x must be an
"algebraic" number...)

But let us say that you can pay 15 with your x, whatever it might turn out to be, we then have to
show that you can WITH THE SAME X pay 15!, 15!!, 15!!! etc - using no more than 14 coins of any
denomination.

Yes, that's the puzzle!

I'm still not finding it plausible.

If we forget all the rational/irrational stuff and just consider x=10, so we have a decimal coinage
system with coins 1, 10, 100, 1000, ... then clearly every integer amount could be payed with a max
of 9 coins of each denomination, right? But hey, what about 33^(8333!!!!!!!+1) That number is
huge, but then what about [33^(8333!!!!!!!+1)]!!!!!!!!!!!!!!!!!!!!. That's even huger!! but can
obviously be paid with no more than 9 coins of each of our denominations. [Yeah, the mint would
have to make lots of coins to pay it....]

Of course, x=10 is not the solution as x (and x^2, x^3, x^4...) must be irrational.
Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vo9t64$hlp5$[email protected]>,
David Entwistle <[email protected]> wrote:

Please don't post a direct answer to the question posed, but I'd welcome a >bit of guidance on Mathsbombe question 3.

I have guessed the correct answer without understanding the problem.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 10/02/2025 00:54, Richard Tobin wrote:

In article <vo9t64$hlp5$[email protected]>,
David Entwistle <[email protected]> wrote:

Please don't post a direct answer to the question posed, but I'd welcome a >> bit of guidance on Mathsbombe question 3.

I have guessed the correct answer without understanding the problem.

*APPLAUSE*

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 09/02/2025 22:39, Mike Terry wrote:

On 09/02/2025 15:03, Richard Heathfield wrote:

On 09/02/2025 11:57, Mike Terry wrote:

<snip>

And what does "any positive integer" mean? Does it, for
example, include bloodybignumber? If so, how about
bloodybignumber factorial?

That's surely easy - it means any positive integer, integers
being whole number like 1,2,3,4,... There is no limit to how
big integers get!  Also there's no limit to how big the coin
values x^k get as k grows.

But these are actual minted coins, so there must be a finite
number of them, yes? Or does the government mint new coins for
every transaction? Really?

It's a puzzle.  If you like, you could assume that the mint will
manufacture as many coins as required, but, dude, IT'S A *MATHS
PROBLEM* not a manufacturing problem.  :)

No, as stated it defines a manufacturing problem, and an
insoluble one.

A maths problem would not bother to mention coins unless so doing
clarifies the problem statement, which here it clearly doesn't.

Pace! Evidently we differ over this and neither of us is likely
to change the other's mind, so I'll let you grump off into your
corner while I grump off into mine, and we can both simmer
quietly about that guy over there in the other corner. :-)

If Kevin Stone is still watching, I'd like to raise a related
grouse, if I may.

Brainbashers sometimes poses a puzzle of the day along these lines:

David, Marmaduke, Kevin and Sebastian like fried tomatoes in
their cooked breakfast, but Andrew, Harold, Luke and Stuart
prefer baked beans.

What does Richard prefer?

Kevin would have us answer 'fried tomatoes', but it'll be a
frosty day in hell before I eat another fried tomato, no matter
how many consonants my name has. Strange as it may seem, people's
likes and dislikes have no discernible connection to the number
of vowels and consonants in their names.

Yes, "here are example members from two mutually exclusive sets -
into which of the two sets would you place /this/ item?" may be a
lot balder, but it does have the advantage of not lying about the
world.

No, I don't suppose Kevin will change his puzzles for my sake,
and arguably the way they are might well make for a slightly more
entertaining puzzle for more people than it annoys; nevertheless,
I feel better for having dislodged the gripe from my sternum.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vobinl$1jvp$[email protected]>,
Richard Tobin <[email protected]> wrote:

In article <vo9t64$hlp5$[email protected]>,
David Entwistle <[email protected]> wrote:

Please don't post a direct answer to the question posed, but I'd welcome a >>bit of guidance on Mathsbombe question 3.

I have guessed the correct answer without understanding the problem.

I have now understood the problem (and its solution).

Let me clarify the points that have caused some doubt about the
problem itself.

(1) The coins have value x^0 (=1), x^1 (=x), x^2, x^3, ... for some
irrational x > 3.3.

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

Here are some obvious observations:

(1) We could equally well consider the problem to be representing an
integer in the irrational base x, where the digits are 0 .. 14.

(2) We need to find an irrational x such that we can add multiples of
its powers to get integers. That rules out x being transcendental
by definition.

And finally a hint that should not give much away until you are on the
right track:

You may, like me, stumble upon the correct value of x and then see
that it works for numbers up to N - a number greater than 400 - but
not immediately see how it works beyond that. I had to think of it
somewhat differently to see that it does.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 10 Feb 2025 15:38:08 +0000 (UTC), Richard Tobin wrote:

I have now understood the problem (and its solution).

Thanks for the clarification on the question and guidance on how to
approach a solution. Not having worked through it yet, I'm now simply surprised, rather than disbelieving, that you can converge on any integer,
no matter what size, with a fixed number of coins. It's working on things
that are surprising that are most rewarding. I'll get on it.

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <voevo3$1m9hs$[email protected]>,
David Entwistle <[email protected]> wrote:

Not having worked through it yet, I'm now simply
surprised, rather than disbelieving, that you can converge on any integer,
no matter what size, with a fixed number of coins.

I think you must have misunderstood:

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

You can use up to 14 coins of each denomination.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vo9v4b$hlsf$[email protected]>,
Richard Heathfield <[email protected]> wrote:

I agree; it doesn't look possible. I was tempted to cut code, but
I hit two ambiguities. What, precisely, does "no more than 14
coins of every given denomination" mean? It could mean an
up-to-14-coin subset of the available range

Let's knock this one on the head. It is not possible to have a set of
coins as described where an arbitrary integer value can be made with at
most 14 coins in total.

Proof:

Let the coins have the denominations 1, x, x^2, ... and add in a coin
with value 0 so we can say exactly 14 coins rather than at most 14.

How many values can we make with the denominations up to x^n? There
are n+2 different such denominations (x^0 .. x^n and 0). So there
are (n+2)^14 ways of choosing our coins in order, and less than that
since the order doesn't matter. (And of course most of them won't
produce an integer anyway.)

How many different values do we need to be able to make with those
coins? All the values less than x^(n+1), since we can't use the x^(n+1) denomination or larger to make a value less than x^(n+1).

The number of values increases exponentially, but the number of coin combinations increases polynomially. So as n increases the number of
values will eventually exceed the number of combinations available to
make them.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 11 Feb 2025 11:11:56 +0000 (UTC), Richard Tobin wrote:

I think you must have misunderstood:

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

You can use up to 14 coins of each denomination.

You are quite right, I had misunderstood. My level of surprise is even
more diminished.

Thanks,
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 11 Feb 2025 19:28:57 -0000 (UTC), David Entwistle wrote:

You are quite right, I had misunderstood. My level of surprise is even
more diminished.

Congratulations, this is the correct answer!

Thanks for all the comments and guidance. I have now stumbled on the
answer reported as correct. I can't say I'm all that happy with it, but it gives me a starting point to look a little deeper and see if I can
increase my contentment.

Best wishes,
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 10 Feb 2025 15:38:08 +0000 (UTC), Richard Tobin wrote:

You may, like me, stumble upon the correct value of x and then see that
it works for numbers up to N - a number greater than 400 - but not immediately see how it works beyond that. I had to think of it somewhat differently to see that it does.

Yes... That's where I'm at at the moment.

I'll try and think differently... :o)

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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?

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vp7dvm$2s8nd$[email protected]>,
David Entwistle <[email protected]> wrote:

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

So you have correctly chosen x such that x^2 + x = 15. Up to here we
are working in base 15 with the x^0 coins (obviously) acting as the
units column, and pairs of x^1 and x^2 coins acting as the 15s column.

To continue in base 15 beyond 224 we need a column for 15^2. Since
x^2 + x is 15, (x^2 + x)^2 is 15^2, and is equal to x^4 + 2x^3 + x^2.
So you can get 225 by using a set of one x^4, two x^3, and one x^2
coin.

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

As you have presumably noticed, this works for a while, but will run
into a problem when you get to 435 = 15^2 + 14*15 which would be

1*x^4 + 2*x^3 + 15*x^2 + 14*x^1

because now you have more than 14 of one coin.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thu, 20 Feb 2025 15:04:52 +0000 (UTC), Richard Tobin wrote:

As you have presumably noticed, this works for a while, but will run
into a problem when you get to 435 = 15^2 + 14*15 which would be

1*x^4 + 2*x^3 + 15*x^2 + 14*x^1

because now you have more than 14 of one coin.

433 matched by 433.00, 1 * x^4 + 2 * x^3 + 14 * x^2 + 13 * x^1 + 13 * x^0
434 matched by 434.00, 1 * x^4 + 2 * x^3 + 14 * x^2 + 13 * x^1 + 14 * x^0
435 matched by 435.00, 2 * x^4 + 3 * x^3 + 0 * x^2 + 14 * x^1 + 0 * x^0
436 matched by 436.00, 2 * x^4 + 3 * x^3 + 0 * x^2 + 14 * x^1 + 1 * x^0

Thanks for the explanation. I have to admit to being slightly amazed that anyone can not only understand, but also clearly describe, what is going
on.

Personally, I'm very happy to have gone from not understanding the
question at all to fully grasping the the question, arriving at a solution
and almost fully-understanding that solution. I'll work on the last bit.

Thanks to all for the support. Onwards and upwards...

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <[email protected]>,
Mike Terry <[email protected]> wrote:

[detailed description and worked example]

To reduce it to its minimum...

If
15 = x^2 + x
then
15x^n = x^(n+2) + x^(n+1)

so we can exchange 15 coins of any one denomination for one each of
the two next higher denominations.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 20/02/2025 20:41, Richard Tobin wrote:

In article <[email protected]>,
Mike Terry <[email protected]> wrote:

[detailed description and worked example]

To reduce it to its minimum...

If
15 = x^2 + x
then
15x^n = x^(n+2) + x^(n+1)

so we can exchange 15 coins of any one denomination for one each of
the two next higher denominations.

-- Richard

Right - and we can keep repeating that as many times as required so that eventually all
denominations have less than 15 coins used. (That's effectively what happens in my example,
starting with 8241 unit coins.)

Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)