Maths Olympiad Prep

Library / /79 of 105

Combinatorics Difficulty 6.4 National Olympiad Prove it North Macedonia

A 4×44 \times 4 table is divided into 16 white unit square cells. Two cells are called neighbours if they share a common side. A move consists in choosing a cell and changing its color and the colors of its neighbours from white to black or from black to white. After exactly nn moves all the 16 cells were black. Find all possible values of nn.

Solution

Figure covers at most 5 cells, so we need at least 4 steps to change color every cell. If we place figure 4 times so that center of figure lies in dark cell we consider that is possible to do that if n=4n=4.

Furthermore, applying operation two times on same cells we get that is possible to get table with every cell is colored black in nn steps for every even n4n \ge 4.

We shall prove that for nn odd it is not possible to do that. Look at picture. Let kk be a difference between white and black cells in dark area in picture. Every figure placed at table covers odd number of dark cells, so after every step kk is changed for number 2(mod4)\equiv 2 \pmod{4}. At the beginning k=10k=10 at the and k=10k=-10. From this it is clearly that we need even number of steps. So nn is every even number except 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.