Problem:
Alice and Bob play the following game on the whiteboard. First, Alice writes an odd number in binary on the board. Then, beginning with Bob, the players take turns modifying the number in one of two ways: subtracting from it (preserving the binary notation), or erasing its last digit. When the whiteboard is blank, the last player to have played wins. Which player has a winning strategy?
Solution:
Bob can win using the following strategy: Play so as to leave an empty whiteboard or a number with an odd number of terminal zeros (preceded by a ). We claim that Bob can fulfill this requirement at every move.
On his first move, or indeed any move in which Alice leaves an odd number on the board, it is easy to see how the requirement can be fulfilled. Unless the number on the board is (in which case Bob wins instantly), it ends in a followed by either an even or an odd number of zeros; in these two cases Bob should subtract one and erase the respectively.
If Alice leaves an even number on the board, it must be by erasing a final from a number left by Bob. Bob can then erase another zero, and the number of terminal zeros will remain odd.