Path: ...!weretis.net!feeder8.news.weretis.net!newsfeed.xs3.de!nntp-feed.chiark.greenend.org.uk!ewrotcd!feeds.news.ox.ac.uk!news.ox.ac.uk!usenet.inf.ed.ac.uk!.POSTED!not-for-mail
From: richard@cogsci.ed.ac.uk (Richard Tobin)
Newsgroups: rec.puzzles
Subject: Re: MathsBombe
Date: Tue, 11 Feb 2025 11:46:29 +0000 (UTC)
Organization: Language Technology Group, University of Edinburgh
Lines: 33
Message-ID: <vofdal$ie1$1@macpro.inf.ed.ac.uk>
References: <vmjlf6$2fg3n$1@dont-email.me> <vo9t64$hlp5$2@dont-email.me> <vo9v4b$hlsf$3@dont-email.me>
NNTP-Posting-Host: macaroni.inf.ed.ac.uk
X-Trace: macpro.inf.ed.ac.uk 1739274389 18881 129.215.197.42 (11 Feb 2025 11:46:29 GMT)
X-Complaints-To: usenet@macpro.inf.ed.ac.uk
NNTP-Posting-Date: Tue, 11 Feb 2025 11:46:29 +0000 (UTC)
X-Newsreader: trn 4.0-test76 (Apr 2, 2001)
Originator: richard@cogsci.ed.ac.uk (Richard Tobin)
Bytes: 2333

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