Square is painted as fast as possible
Source: 43rd International Tournament of Towns, Senior O-Level P3, Fall 2021
February 18, 2023
combinatoricsboardTournament of Towns
Problem Statement
In a checkered square of size all cells are initially white. Ivan selects two cells and paints them black. At each step, all the cells that have at least one black neighbor by side are painted black simultaneously. Ivan selects the starting two cells so that the entire square is painted black as fast as possible. How many steps will this take?Ivan Yashchenko