Enigma 316: The min-factor game
23 October 2015
Posted by on
From New Scientist #1464, 11th July 1985 [link]
This is a game between you and the Devil. It starts with the natural numbers from 1 to N written in a row. You and the Devil play alternately, you first. The rules are simple:
(a) You take any number you choose (subject to rule (d) below) from those remaining in the row and delete it from the row.
(b) He then deletes from the numbers remaining in the row all those which are factors of the number you just took.
(c) Go to (a).
(d) You can never take a number which has no factor remaining in the row; that is, your take must permit the Devil in his turn to delete at least one number.
The game stops when you can legally take no more numbers, and you want the sum S of all the numbers you have taken to be as small as possible.
The picture records a game with N=7 and S=6. You did very well. Now try with N=30.
How small can you make S?