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?

$\endgroup$
  • 4
    $\begingroup$ Maybe specify that all squares must be painted either red or white. Otherwise there's a solution with zero. $\endgroup$ – Bass Sep 24 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 Sep 24 at 14:55
  • $\begingroup$ @Bass OK. I added the phrase. $\endgroup$ – P.-S. Park Sep 24 at 15:16
  • $\begingroup$ What about diagonals? If two squares' corners touch diagonally, are the squares themselves considered to touch? $\endgroup$ – Panzercrisis Sep 25 at 4:18
  • $\begingroup$ It would be interesting to see how this evolves depending on the size of the chess board. $\endgroup$ – Dark Malthorp Sep 25 at 15:38
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$
  • 1
    $\begingroup$ I think your second solution is the best possible (based on my computer results). $\endgroup$ – 2012rcampion Sep 24 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 Sep 24 at 15:46
  • 3
    $\begingroup$ I confirmed via integer linear programming that 28 is optimal. $\endgroup$ – RobPratt Sep 24 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 Sep 24 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 Sep 25 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$
  • 6
    $\begingroup$ Depending on how you look at it, the answer could also be 88. $\endgroup$ – Ambo100 Sep 24 at 22:44
1
$\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$
  • $\begingroup$ questions shoule be left open for more than 24 hours before the OP posts a spoiler. $\endgroup$ – Jasen Sep 25 at 6:03
  • $\begingroup$ Ah, I didn't know that. I'll delete my spoiler. $\endgroup$ – P.-S. Park Sep 25 at 6:06
  • 1
    $\begingroup$ I undeleted after 24 hours. $\endgroup$ – P.-S. Park Sep 26 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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