MathDB

C5

Part of 2018-IMOC

Problems(1)

game, coloring grids in chessboard ft. Alice and Bob

Source: IMOC 2018 C5

8/16/2021
Alice and Bob are playing the following game: They have an 8×88\times8 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?
combinatoricsgame