On a $5 \times 5$ board, $n$ white markers are positioned, each marker in a distinct $1 \times 1$ square. A smart child got an assignment to recolor in black as many markers as possible, in the following manner: a white marker is taken from the board, it is colored in black, and then put back on the board on an empty square such that none of the neighboring squares contains a white marker (two squares are called neighboring if they share a common side). If it is possible for the child to succeed in coloring all the markers black, we say that the initial positioning of the markers was good. a) Prove that if $n = 20$, then a good initial positioning exists. b) Prove that if $n = 21$, then a good initial positioning does not exist.
Problem
Source: JBMO 2008 Shortlist C1
Tags: JBMO, combinatorics
VicKmath7
11.08.2019 22:41
Position 20 white markers on the board such that the left-most column is empty. This positioning is good because the coloring can be realized column by column, starting with the second (from left), then the third, and so on, so that the white marker on position (i, j) after the coloring is put on position (i, j − 1). b) Suppose there exists a good positioning with 21 white markers on the board i.e. there exists a re-coloring of them all, one by one. In any moment when there are 21 markers on the board, there must be at least one column completely filled with markers, and there must be at least one row completely filled with markers. So, there exists a ”cross” of markers on the board. At the initial position, each such cross is completely white, at the final position each such cross is completely black, and at every moment when there are 21 markers on the board, each such cross is monochromatic. But this cannot be, since every two crosses have at least two common squares and therefore it is not possible for a white cross to vanish and for a black cross to appear by re-coloring of only one marker.