6
$\begingroup$

An aid in this problem:

On a board of $7 \times 7$ each square is painted red or blue so that every square on the board has at least two neighboring squares blue. determine the minimum number of blue boxes on the board. Two cells are neighbors if they have a common side.

My progress is trying to have painted boxes that most have only two neighboring blue boxes, but my problem is:

How do I know I've got the minimum?

Will there be other settings with fewer blue boxes? Thank you.

$\endgroup$
6
  • $\begingroup$ Having almost all of the squares have two neighbours painted blue is not a sufficient condition for the minimum. For instance, for a $3 \times 3$ board, one of those solutions would be $$\begin{matrix} B & B & B \\ B & - & B \\ B & B & B \end{matrix}$$ while a solution with fewer blue squares would be $$\begin{matrix} B & B & - \\ B & B & B \\ - & B & B \end{matrix}$$ So I think knowing when you have a minimum is not so easy. $\endgroup$ – TMM Jul 24 '13 at 23:05
  • $\begingroup$ Yes TMM , thats the problem $\endgroup$ – giancarlo Jul 24 '13 at 23:10
  • $\begingroup$ I'm curious what your solution is. I can get to 31 blue boxes; can you go any lower? $\endgroup$ – TMM Jul 24 '13 at 23:15
  • $\begingroup$ Yes my solution is 31 , but my problem is how to justify that is the solution. $\endgroup$ – giancarlo Jul 24 '13 at 23:18
  • $\begingroup$ Hmm. The best lower bound I got was 29. $\endgroup$ – Michael Biro Jul 25 '13 at 1:00
8
$\begingroup$

I got a bit carried away, but the minimum seems to be $31$ indeed. Unfortunately my method does not seem to generalize very well, but maybe that's too ambitious.


We have a total of $49$ boxes, each of which must have $2$ edges painted blue, adding up to a total of $98$ edges to be painted blue. As the corner boxes have only $2$ edges available for painting, these two edges must be painted blue. This yields $8$ boxes painted blue, each having $3$ edges painted bue. This makes for a total of $24$ edges painted blue, leaving $74$ edges yet to be painted blue. The image on the left shows these $8$ boxes:

$\hspace{60pt}$enter image description here$\hspace{100pt}$enter image description here

Note that there are $24$ boxes yet to be painted that have 'excess' edges, i.e. edges that do not need to be painted blue. They are shown in green in the second picture. These are the $4$ corners, having $2$ excess edges each, the $12$ remaining side boxes, having $1$ excess edge each, and $8$ boxes adjacent to the $4$ interior boxes that already have $2$ blue edges, having $1$ excess edge each. This yields a total of $28$ excess edges, but we will encounter a few more excess edges later on.

The square is divided into $4$ quadrants by its diagonals. We will show that in each quadrant, at least $4$ excess edges must be painted blue. To this end we will paint the top quadrant, attempting to paint fewer than $4$ excess edges blue. We distinguish $5$ cases, painting towards a contradiction.

Both blue boxes in the top quadrant are adjacent to $2$ boxes with an excess edge, and at least $1$ of these $2$ boxes must be painted blue, hence at least $2$ more boxes in the top row must be painted blue. If we paint $4$ more boxes in the top row blue, then we paint $4$ excess edges blue, and we are done. So we restrict to the cases where we paint $2$ or $3$ more boxes in the top row blue.

After painting the top row, every box in the top row must have at least one blue edge. Painting only two boxes in the top row, there is only one way to do so; see the picture on the left.

$\hspace{60pt}$enter image description here$\hspace{100pt}$enter image description here

Then in order for our newly painted boxes to have $2$ blue edges, we must paint the boxes immediately below them blue, see the picture on the right. Then we have painted $4$ excess edges blue, and we are done.

Finally we paint precisely $3$ boxes in the top row blue. Up to symmetry, there are $4$ ways to do so, keeping in mind that each box must have at least $1$ blue edge. They are shown in the image below.

$\hspace{25pt}$enter image description here

Whenever a box in the top row has only $1$ blue edge, the box directly below it must be painted blue. These necessarily blue boxes are shown in the image below.

$\hspace{25pt}$enter image description here

In the left two cases, we see that $5$ excess edges are painted blue, and we are done. It remains to show that in the right two cases, at least one more excess edge must be painted blue.

In the middle right case, we are actually done already; in the left image below, the box highlighted in green has $3$ blue edges, so it has $1$ excess edge painted blue. With a total of $4$ excess edges painted blue, this case is closed.

$\hspace{60pt}$enter image description here

For the rightmost and final case, we continue painting edges blue without painting $3$ edges of the same box blue, towards a contradiction. In the middle image above, the only way for the highlighted box to have $2$ blue edges without any other boxes having $3$ blue edges, we must paint the box directly below it blue. For this newly painted box to have $2$ blue edges, at least one of the boxes to its left, right, or top must be painted blue. These are highlighted in orange in the right image above. But in each case one or both of the boxes highlighted in green will have $3$ blue edges, hence an excess edge painted blue.

We conclude that in each quadrant, there are at least $4$ excess edges painted blue. With $4$ quadrants, this yields a total of $16$ excess edges to be painted blue. Hence in total we must paint at least $74+16=90$ edges blue, after having painted the $8$ initial boxes blue. But as each box has only $4$ edges, this requires at least $\tfrac{90}{4}>22$ more boxes to be painted blue, i.e. at least $23$ more boxes. Together with the inital $8$ boxes, this yields a minimum of $8+23=31$ boxes to be painted blue. This is in fact the minimum:

$\hspace{25pt}$enter image description here

I wonder how many minimal solutions there are...

$\endgroup$
6
  • 1
    $\begingroup$ Via integer linear programming, I confirmed that the minimum is 31, and there are 263 solutions that attain that minimum. $\endgroup$ – RobPratt Apr 7 '20 at 15:51
  • $\begingroup$ @RobPratt That's interesting! Are those solutions up to rotation and reflection? Or is there some highly symmetrical solution to yield an odd total number of solutions? I'd be interested to see the latter. $\endgroup$ – Servaes Apr 7 '20 at 15:54
  • 1
    $\begingroup$ Sorry, I meant 264, and this is treating rotations and reflections as distinct solutions. $\endgroup$ – RobPratt Apr 7 '20 at 16:01
  • 1
    $\begingroup$ There are 48 optimal solutions up to symmetry. $\endgroup$ – RobPratt Apr 7 '20 at 16:30
  • 1
    $\begingroup$ I added a comment to that question just now. $\endgroup$ – RobPratt Apr 8 '20 at 15:29

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.