17
$\begingroup$

Is it possible to fill every interior square in this grid with one of 3 colors (red, green, or blue) so that no two adjacent cells have the same color? (Adjacent meaning horizontal or vertical, but not diagonal.)

If it is possible, give a solution. If it is not possible, give a proof of impossibility.

square grid with boundary squares colored red, green, and blue

Here is the same grid in text format:

RGBGBRGRGRBR
G..........B
R..........R
G..........B
R..........R
G..........B
B..........G
R..........B
B..........R
G..........B
R..........G
BGRBRBGBRGRB

Penpa+ version

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
19
$\begingroup$

It is impossible.

Proof: We can prove this by contradiction. Assume that the grid has been 3-colored.

We can consider placing arrows between some pairs of adjacent cells in the grid, keeping track of a score while doing so. If we place an arrow that points from a red square to a green square, increase the score by 1. If we place an arrow pointing from a green square to a red square, decrease the score by 1.

Place one arrow pointing clockwise on each pair of adjacent cells on the boundary of the grid. Using the colors given, we have that the total score of these arrows is 2. Here is an illustration: enter image description here

Now, for every vertex in the interior of the grid, place four arrows surrounding it in a counterclockwise direction.

For every vertex, we can check that placing these arrows does not change the score (by checking every 2x2 configuration of colors surrounding the vertex), since these arrows have a total score of 0. For example, the arrows surrounding the vertex in the image below have a total score of 0.
enter image description here

This means that after this arrow-placing step, the total score is still 2.

After these two steps, every edge between two cells would have a pair of arrows pointing in opposite directions. Each pair of arrows has a total score of 0, so the total score of all the arrows is 0. This means that 0 = 2. This is a contradiction, so it is impossible to 3-color the grid.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Out of the two answers so far, this is closer to what I had in mind. I think this step is a little unclear: reveal spoiler"For each vertex, we can check that placing these arrows does not change the score..." Did you simply check every possible 2x2 configuration or is something else going on there? $\endgroup$ Commented Apr 11 at 20:58
  • 6
    $\begingroup$ Here's a cleaner proof that every reveal spoiler2x2 configuration has the desired property: reveal spoilerThere must be a color that appears twice. Call it color A. The two squares of color A are not adjacent. So every arrow is either entering color A, or leaving that color. Moreover, involving each of the other two squares there is one arrow entering color A and one leaving color A. So the four arrows in the 2x2 square consist of two pairs of reversed colors. As a result, the total score must be 0. $\endgroup$ Commented Apr 12 at 5:15
  • 3
    $\begingroup$ Food for thought: This argument is very reminiscent of (the proof of) Green’s theorem aka the divergence theorem in $\Bbb R^2$. $\endgroup$ Commented Apr 12 at 5:58
  • 3
    $\begingroup$ @GregMartin That's one of the inspirations for this proof! $\endgroup$ Commented Apr 12 at 6:14
  • 1
    $\begingroup$ @mathlander My version had reveal spoiler1 point for red->green, green->blue, or blue->red, and -1 for the reverse of any of those. A consequence of this is that the score of any closed loop must be divisible by 3, since the score essentially keeps track of how far the color travels around the color cycle. You can use this to show the score of a 2x2 loop must be 0 (if it wasn't, it would have to be 3 or -3, but since every step is 1 or -1, the total score of 4 steps can't be odd.) $\endgroup$ Commented Apr 12 at 19:39
4
$\begingroup$

This coloring is

unfortunately impossible.

Here is the proof. It relies on

  • a local forcing rule, together with
  • an exhaustive computational separation argument.

The local forcing rule is the following: in any 2×2 block, if the top-right and bottom-left cells are different, then the bottom-right cell is forced to equal the top-left cell. The reason is that the bottom-right cell must differ from both its top and left neighbors; if those two neighbors already have different colors, then only one color remains.

Because the boundary colors are fixed by the OP, this forcing severely restricts the last interior row. In fact, Row 10 has exactly 10 admissible patterns that avoid clashing with the bottom and side borders:

  • BGRGRBRGRB, BGRGRBRBRB, BGRGRBGBRB, BGRBRBRGRB, BGRBRBRBRB
  • BGRBRBGBRB, BGRBGRGBRB, BGRBGBRGRB, BGRBGBRBRB, BGRBGBGBRB

Finally, I wrote a complete computer check to confirm the impossibility by testing where the top and bottom halves of the grid could meet. The search treats each interior row as a length-10 word in {R, G, B} with no repeated adjacent colors. Boundary restrictions eliminate rows that clash with the fixed edge colors, and vertical compatibility is enforced by requiring neighboring rows to differ in every column.

The program then computes, exhaustively:

  • the set T of all Row 9 patterns that can be extended upward to the top boundary;
  • the set B of all Row 9 patterns that can be extended downward to the bottom boundary, starting from the restricted Row 10 patterns.

In the end, it finds that T ∩ B = ∅. Since these two sets are disjoint, no possible Row 9 can fit both the top half and the bottom half of the grid. Therefore, the upper and lower parts can never be joined, and

no full coloring exists.

so

I would not try to solve it manually.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.