AoPS - Problem

Source: Kazakhstan Republic Olympiad 2020 - 11 - P4

Tags: Arithmetic Progression, game strategy, combinatorics, arithmetic sequence

menpo

19.04.2021 09:39

Alice and Bob play a game on the infinite side of a checkered strip, in which the cells are numbered with consecutive integers from left to right (..., $-2$, $-1$, $0$, $1$, $2$, ...). Alice in her turn puts one cross in any free cell, and Bob in his turn puts zeros in any 2020 free cells. Alice will win if he manages to get such 4 cells marked with crosses, the corresponding cell numbers will form an arithmetic progression. Bob's goal in this game is to prevent Alice from winning. They take turns and Alice moves first. Will Alice be able to win no matter how Bob plays?

It indeed immediately follows from Szemeredi's theorem, but is is an overkill. It means that Alice can just put crosses here and there randomly (complying with the rules) in some large enough interval and in the end there will be a $4$ progression. This is a strong and very difficult claim. Since Alice is an active part, she can implement a method that ensures progression like that. I remember I found the official solution at the time this problem had appeared. It was some ingenious method of putting crosses so that in the end there were so many threats of making progressions that Bob could not prevent it from happening. However, I don't think it's an appropriate problem due to the mentioned overkill.