Alice an Bob play a game on a square grid
Source: IMSC 2024 Day 1 Problem 3
June 28, 2024
combinatoricscombinatorics proposedgamegame strategy
Problem Statement
Alice and Bob play the following game on a square grid with 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 -th turn, let be the least integer such that . If there is at least one square without a sticker, then the player taking the turn:
[list = i]
[*] selects at most 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 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