# Painting a chessboard

On the following chessboard every white square meets at least two red squares.

Let's paint a new chessboard so that every white square meets exactly two red square. Every square should be painted either red or white. It is clearly possible from the following chessboard.

But, too many squares were painted red. What is the minimal number of squares should be painted red?

• Maybe specify that all squares must be painted either red or white. Otherwise there's a solution with zero.
– Bass
Commented Sep 24, 2020 at 14:52
• Since each red square can touch at most four white squares, a lower bound is (# red) ≥ (# white) / 2, so (# red) ≥ 22. Commented Sep 24, 2020 at 14:55
• @Bass OK. I added the phrase. Commented Sep 24, 2020 at 15:16
• What about diagonals? If two squares' corners touch diagonally, are the squares themselves considered to touch? Commented Sep 25, 2020 at 4:18
• It would be interesting to see how this evolves depending on the size of the chess board.
– user63779
Commented Sep 25, 2020 at 15:38

I can do

29

like so:

The pattern might be even prettier than that of @hexomino's answer. :-)

EDIT: sadly, no circle pattern anymore, but scores none better: (RE-EDIT: bold letter added because of Jaap's keen eyes; h3 must be red)

28:

And another one with the same amount of redness (RE-EDIT: my only decent solution), this time with more boring symmetry (and also optimal if we are to trust @2012rcampion's comment below):

• I think your second solution is the best possible (based on my computer results). Commented Sep 24, 2020 at 15:22
• Your first solution of 28 is incorrect. The white square in row 5 column 8 has only one red neighbour. When you fix that, it is essentially your first 29 solution rotated 180 degrees. Your symmetric solution looks correct. Commented Sep 24, 2020 at 15:46
• I confirmed via integer linear programming that 28 is optimal. Commented Sep 24, 2020 at 16:06
• For $n\in\{1,\dots,17\}$, the optimal values are $\{1,2,5,8,11,17,21,28,35,42,51,60,69,80,91,102,115\}$, from which I conjecture general formula $\lceil (n+2)^2/3 \rceil - 6$ for $n \ge 7$. Commented Sep 24, 2020 at 20:13
• @P.-S.Park Here are the counts for $n\in\{1,\dots,10\}$, ignoring symmetry: $1, 2, 5, 4, 2, 16, 2, 8, 2, 8$ Commented Sep 25, 2020 at 2:08

Not sure if this is minimal but there is a nice symmetric solution for

$$32$$ red squares

as follows

• Depending on how you look at it, the answer could also be 88. Commented Sep 24, 2020 at 22:44

OP's comment.

When I propose this problem, many people used to hand in the following patterns with 32 red squares.

That's a beautiful symmetric pattern. But, they are not a minimal answer. This problem was proposed to deceive people who were satisfied with the symmetric solutions. :-)

The correct answers with 28 red squares are as follows:

Note that Quadrants II and IV are symmetric and Quadrants I and III on each pattern are mixed with 2 types. So, ignoring symmetry, the total number of solutions of 28 red squares is 8 as commented by RobPratt.

The minimal answer for $$9 \times 9$$ board is a pattern with 35 red squares.

This pattern is symmetric, so the total number of solutions is just 2 as also commented.

• questions shoule be left open for more than 24 hours before the OP posts a spoiler. Commented Sep 25, 2020 at 6:03
• Ah, I didn't know that. I'll delete my spoiler. Commented Sep 25, 2020 at 6:06
• I undeleted after 24 hours. Commented Sep 26, 2020 at 1:57