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, "b-", as -b if 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!