Problem:
Aerith and Bob take turns picking a nonnegative integer, each time changing exactly one digit from the other's last number. The first person to pick a number that (s)he picked before loses. If Aerith goes first, and both play optimally, who wins?
(Note: There are no leading zeroes, except in the number itself. For instance, if one person picks , the other could respond by picking , however the reverse does not hold.)
Solution:
Bob wins. One winning strategy for Bob is: each time Aerith picks an even number, add one, and each time Aerith picks an odd number, subtract one. This only changes the last digit, since there are no carryovers in either case.
Bob would only get into a situation where he repeated an even number if Aerith had repeated the succeeding number twice, and similarly he would only need to repeat an odd number if Aerith had picked the preceding number twice. In either case, Aerith would have already lost.