Problem

Source: IMSC 2024 Day 1 Problem 3

Tags: combinatorics, combinatorics proposed, game, game strategy



Alice and Bob play the following game on a square grid with 2024×2024 unit squares. They take turns covering unit squares with stickers including their names. Alice plays the odd-numbered turns, and Bob plays the even-numbered turns. On the k-th turn, let nk be the least integer such that nk. If there is at least one square without a sticker, then the player taking the turn: selects at most n_k unit squares on the grid such that at least one of the chosen unit squares does not have a sticker. covers each of the selected unit squares with a sticker that has their name on it. If a selected square already has a sticker on it, then that sticker is removed first. At the end of their turn, a player wins if there exist 123 unit squares containing stickers with that player's name that are placed on horizontally, vertically, or diagonally consecutive unit squares. We consider the game to be a draw if all of the unit squares are covered but no player has won yet. Does Alice have a winning strategy? Proposed by Erik Paemurru, Estonia