Read (or

know) about

Sylver Coinage before reading this, or it won't make much sense!

Our goal is to prove that any sequence of positive integers `a`_{1},a_{2},... such that `a`_{k} is not expressible as a sum `c`_{1}a_{1} + ... + c_{k-1}a_{k-1} with nonnegative coefficients `c`_{i} must be finite.

So suppose we have `a`_{1},...,a_{k}. The number `d`_{k} = gcd(`a`_{1},...,a_{k}) is very important here; clearly `a`_{1} = d_{1} >= d_{2} >= ... >= 1. And note that all "forbidden" moves (numbers which would be illegal to play as `a`_{k+1}) are multiples of `d`_{k}. However, it is not generally true that `d`_{k} > d_{k+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:

`d`_{k} = b_{1}a_{1} + ... + b_{k}a_{k}.

Define the "negative part" of

`b`, "

`b`^{-}", as -

`b` if

`b`<0, 0 otherwise. Then all numbers which are multiples of

`d`_{k} and greater than

`m`_{k} = b_{1}^{-}a_{1} + ... + b_{k}^{-}a_{k}

are illegal moves.

So after finitely many (at most `m`_{k}/d_{k}) moves, one player has to play a move which is *not* a multiple of `d`_{k} (in which case the next `d` will be strictly smaller, making progress towards `d`=1).

So eventually we reach `d`_{N}=1; the same argument holds, except now *all* numbers greater than `m`_{N} are illegal moves, so only finitely many legal moves remain -- and at some stage the game ends!