Solution
Take Away a Perfect Square
Show the problem again
A pile contains n stones. Two players alternate; on each turn a player must remove a positive perfect square number of stones (1, 4, 9, 16, ...), no more than the pile holds. The player who takes the last stone wins. For how many values of n with 1 ≤ n ≤ 100 does the player to move lose with optimal play? Give an integer.
Worked solution
The answer is 20. There is no closed form for this game, so the losing positions are found by backward induction: n is losing exactly when n minus every square ≤ n is a winning position. Starting with 0 losing, the losing positions are 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, 52, 57, 62, 65, 67, 72, 85, 95, ... There is no further losing position up to 100 after 95, and 0 itself is outside the range. Counting 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, 52, 57, 62, 65, 67, 72, 85, 95 gives 20 losing starting sizes.
Source: Classic take-away game (squares); no traceable original source. Statement written for AxiomIQ.