19
$\begingroup$

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

enter image description here

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.

enter image description here

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

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

3 Answers 3

Reset to default
15
$\begingroup$

I can do

29

like so:

enter image description here

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:
enter image description here

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):

enter image description here

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ I think your second solution is the best possible (based on my computer results). $\endgroup$
    – 2012rcampion
    Commented Sep 24, 2020 at 15:22
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jaap Scherphuis
    Commented Sep 24, 2020 at 15:46
  • 3
    $\begingroup$ I confirmed via integer linear programming that 28 is optimal. $\endgroup$
    – RobPratt
    Commented Sep 24, 2020 at 16:06
  • 4
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Sep 24, 2020 at 20:13
  • 1
    $\begingroup$ @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$ $\endgroup$
    – RobPratt
    Commented Sep 25, 2020 at 2:08
10
$\begingroup$

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

$32$ red squares

as follows

enter image description here

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ Depending on how you look at it, the answer could also be 88. $\endgroup$
    – Ambo100
    Commented Sep 24, 2020 at 22:44
2
$\begingroup$

OP's comment.

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

enter image description here

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:

enter image description here

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.

enter image description here

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ questions shoule be left open for more than 24 hours before the OP posts a spoiler. $\endgroup$
    – Jasen
    Commented Sep 25, 2020 at 6:03
  • $\begingroup$ Ah, I didn't know that. I'll delete my spoiler. $\endgroup$
    – P.-S. Park
    Commented Sep 25, 2020 at 6:06
  • 1
    $\begingroup$ I undeleted after 24 hours. $\endgroup$
    – P.-S. Park
    Commented Sep 26, 2020 at 1:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.