[seqfan] Re: Currency puzzle
David Wilson
davidwwilson at comcast.net
Fri Sep 25 14:28:14 CEST 2015
I screwed up the ellipsis, it should have read:
1, 2, 2, 3, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64...
so the sequence continues ad infinitum in the obvious way.
So I blew this puzzle.
Robert Wilson's GF for ways of making change was incorrect because it counts zero or more instances of any coin/bill.
Robert Pratt's GF was also incorrect, the term for a duplicated denomination d should be (1 + x^d)^2, not (1 + 2x^d).
William Kieth's GF is correct:
GF = (1 + x) (1 + x^2)^2 (1 + x^3) (1 + x^4)^2 (1 + x^8)^2 ...
(amended to go on to forever per my original idea).
But we have
(1 + x^2) (1 + x^4) (1 + x^8) ... = 1 / (1 - x^2), so
GF = (1 + x) (1 + x^3) / (1 - x^2)^2
Dividing 1 + x twice out of top and bottom
GF = (1 - x + x^2) / (1 - x)^2
= 1 + x / (1 - x^2)
In the latter form, it is easier to recover the sequence of change counts:
1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
So we can change 0 blatz in 1 way (as always), and n blatz in n ways for n > 0.
I believe this is the unique currency in which each value n > 0 can be changed n ways in distinct denominations.
For example, letting b stand for bill, and c for coin, here are the 10 ways to make change for 10 blatz:
b8 + b2
b8 + c2
c8 + b2
c8 + c2
b4 + c4 + b2
b4 + c4 + c2
b4 + c3 + b2 + c1
b4 + c3 + c2 + c1
c4 + c3 + b2 + c1
c4 + c3 + c2 + c1
More information about the SeqFan
mailing list