Two players play tic-tac-toe (also known as noughts and crosses, or Xs and Os) on a board which is an infinite row of squares. The first player on each of his turns marks one of the squares with a cross, and the second player marks 1000 squares with noughts (not necessarily in succession) on each of his turns. Can the crosses form an arithmetic progression of length 4? ( (Four positions of the arithmetic progression with an arbitrary step are filled only with the crosses).
Asked
Active
Viewed 368 times
1
-
2Welcome to StackExchange! Please add your thoughts to the question. It helps people write an answer which is at your level of knowledge and doesn't repreat things you already know – lioness99a May 16 '17 at 09:45
1 Answers
4
Yes, the first player can form a four-term arithmetic progression of crosses.
Identify the row of squares with the set of all integers. The first player's strategy is very simple: at each turn, he marks the smallest positive integer which has not been marked by either player. This ensures that the set of positive integers marked by the first player (if the game is played to infinity) has lower density at least $\frac1{1001}.$ By a theorem of Endre Szemerédi, a set of natural numbers with positive upper density must contain a four-term arithmetic progression; thus the first player wins.
Szemerédi subsequently extended his theorem to arithmetic progressions with any finite number of terms; see the Wikipedia article on Szemerédi's theorem.
bof
- 78,265