0

There is a 4*4 cells table. We paint cells by the following rule: any unpainted cell has an adjacent side with a painted cell, and any painted cell has an adjacent side with an unpainted cell. For example, for n = 12 (1 - painted, 0- not painted)

1 1 0 1
0 1 1 1
1 1 1 0
1 0 1 1
Now the question. Is it possible to paint 14 instead of 12 cells? (I think that we can't)

student28
  • 385

2 Answers2

1

Each corner must be either be unpainted, or adjacent to an unpainted cell.

In a $4\times4$ grid there is is no cell that is adjacent to 2 corners.

There must be at least 4 unpainted cells.

Doug M
  • 57,877
  • This is the basic idea, although you didn't take into account the possibility of a corner cell itself being unpainted. – browngreen Mar 13 '17 at 22:01
1

It is impossible to paint more than 12 cells.

If you divide the grid into four 2x2 grids, then each section must have at least one unpainted cell. For each section, either the corner cell itself is unpainted, or one of the adjacent cells is unpainted. Therefore, there will be at least 4 unpainted cells in total.

browngreen
  • 1,898