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 Sep 24 at 14:52
• Since each red square can touch at most four white squares, a lower bound is (# red) ≥ (# white) / 2, so (# red) ≥ 22. – 2012rcampion Sep 24 at 14:55
• @Bass OK. I added the phrase. – P.-S. Park Sep 24 at 15:16
• What about diagonals? If two squares' corners touch diagonally, are the squares themselves considered to touch? – Panzercrisis Sep 25 at 4:18
• It would be interesting to see how this evolves depending on the size of the chess board. – Dark Malthorp Sep 25 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). – 2012rcampion Sep 24 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. – Jaap Scherphuis Sep 24 at 15:46
• I confirmed via integer linear programming that 28 is optimal. – RobPratt Sep 24 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$. – RobPratt Sep 24 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$ – RobPratt Sep 25 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. – Ambo100 Sep 24 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. – Jasen Sep 25 at 6:03
• Ah, I didn't know that. I'll delete my spoiler. – P.-S. Park Sep 25 at 6:06
• I undeleted after 24 hours. – P.-S. Park Sep 26 at 1:57