reduce the string of binary numbers
Source: ItaMO 2010, p5
February 29, 2012
combinatorics proposedcombinatorics
Problem Statement
In the land of Cockaigne, people play the following solitaire. It starts from a finite string of zeros and ones, and are granted the following moves:
(i) cancel each two consecutive ones;
(ii) delete three consecutive zeros;
(iii) if the substring within the string is , one may replace this by substring .
The moves (i), (ii) and (iii) must be made one at a time. You win if you can reduce the string to a string formed by two digits or less.
(For example, starting from , one can win using move (iii) first in the last two digits, resulting in , then playing the move (i) on two 'ones', and finally the move (ii) on the three zeros, one will get the empty string.)
Among all the possible strings of ten-digit binary numbers, how many are there from which it is not possible to win the solitary?