Seemingly simple games can serve as thought-provoking exercises in mathematical logic. They can provide deep insights into subtle issues that confront logicians who are interested in the foundations of mathematics.
So-called Ehrenfeucht games have proved particularly useful for tackling certain aspects of mathematical logic. They were developed in the 1960s by Andrzej Ehrenfeucht, who is now a computer science professor at the University of Colorado in Boulder.
Ehrenfeucht games can also be studied for their own sake as interesting and often surprisingly subtle games, an approach adopted by Caroline Nguyen of Stuyvesant High School in New York City. Nguyen was one of 40 finalists in the 2001 Intel Science Talent Search (STS). Her goal was to identify, for a specific type of two-player Ehrenfeucht game, the starting positions in which the player moving second will always win.
The game is played with two sequences of zeros and ones. Each sequence can be of any lengt