) about Sylver Coinage
before reading this, or it won't make much sense!
Our goal is to prove that any sequence of positive integers a1,a2,... such that ak is not expressible as a sum c1a1 + ... + ck-1ak-1 with nonnegative coefficients ci must be finite.
So suppose we have a1,...,ak. The number dk = gcd(a1,...,ak) is very important here; clearly a1 = d1 >= d2 >= ... >= 1. And note that all "forbidden" moves (numbers which would be illegal to play as ak+1) are multiples of dk. However, it is not generally true that dk > dk+1 -- for instance, "6 4 2" is a legal (if stupid) sequence of moves.
It is possible to write the greatest common divisor as an integer combination of the values, albeit with some negative coefficients:
dk = b1a1 + ... + bkak.
Define the "negative part" of b
", as -b
<0, 0 otherwise. Then all numbers which are multiples of dk
and greater than
mk = b1-a1 + ... + bk-ak
are illegal moves.
So after finitely many (at most mk/dk) moves, one player has to play a move which is not a multiple of dk (in which case the next d will be strictly smaller, making progress towards d=1).
So eventually we reach dN=1; the same argument holds, except now all numbers greater than mN are illegal moves, so only finitely many legal moves remain -- and at some stage the game ends!