Re: MathsBombe

In article <vo9v4b$hlsf$3@dont-email.me>,
Richard Heathfield  <rjh@cpax.org.uk> 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