game, coloring grids in chessboard ft. Alice and Bob
Source: IMOC 2018 C5
August 16, 2021
combinatoricsgame
Problem Statement
Alice and Bob are playing the following game: They have an chessboard. Initially, all grids are white. Each round, Alice chooses a white grid and paints it black. Then Bob chooses one of the neighbors of that grid and paints it black. Or he does nothing. After that, Alice may decide to continue the game or not. The goal of Alice is to maximize the number of connected components of black grids, on the other hand, Bob wants to minimize that number. If both of them are extremely smart, how many connected components will be in the end of the game?