This curious game was invented by Princeton mathematician John H. Conway.
Two players take turns naming positive integers, but an integer is off limits if it's the sum of nonnegative multiples of integers already been named.
Once 1 is named, everything is off limits (because no new positive integer can be named).
A player forced to name "1" - i.e. having no other choice loses the game.
Devise a winning strategy for the 1st player.
The Wikipedia article on Sylver coinager, the name of this game,
leads to the following strategy for the first player:
Choose 5 as the first move. After each of the second player's moves, play the largest number still available. After the second player's first move this is easily calculated: Call the first two moves, already played, A and B. The highest number still available is A*B - (A+B). The article gives this as (A-1)*(B-1)-1.
From then on the first player's strategy is still to take the highest number still available, but this will be harder to calculate once more numbers are given. Such a number is called the
Frobenius number
Wikipedia states:
There is an explicit formula for the Frobenius number when there are only two different coin denominations, x and y: xy - x - y. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input).[2] No known algorithm is polynomial time in the number of coin denominations, and the general problem, where the number of coin denominations may be as large as desired, is NP-hard.[3][4]
|
|
Posted by Charlie
on 2017-12-23 16:26:49 |
Researched answer
