13
$\begingroup$

Is it possible to paint the cells of a rectangular grid with $K$ different colours such that:

  1. No two adjacent (horizontally or vertically) cells have the same colour, and
  2. Every combination of two colours appears exactly once in some two adjacent (horizontally or vertically) cells, and
  3. The sides of the rectangle are greater than 1.

I don't know the answer to this question myself. The closest I have found so far is

A 4x7 grid painted in 10 different colours:

0124567
8906925
7431738
2864051

Here the first condition holds as no two adjacent cells share the same colour. The second condition almost holds. However the combination 3-9 is missing and the combination 4-6 appears twice.

$\endgroup$
  • 4
    $\begingroup$ I think you also want to add the condition that the width and height of the rectangular grid are also greater than 1. Otherwise it is essentially like laying a row of dominoes, which is easy. $\endgroup$ – Jaap Scherphuis Jul 8 at 12:43
  • 1
    $\begingroup$ Ah yes good point. Updated. $\endgroup$ – Dmitry Kamenetsky Jul 8 at 13:56
  • 4
    $\begingroup$ A lot of the issue here seems to be with the effect of edges and corners. I wonder if asking the same question, but embedding the grid on a torus so all "squares" have exactly 4 neighbors, might be more easily analyzed. $\endgroup$ – Jeremy Dover Jul 8 at 17:46
  • 3
    $\begingroup$ @JeremyDover In other words: Everything is better with doughnuts. $\endgroup$ – smithkm Jul 8 at 22:21
  • $\begingroup$ @smithkm: Endorsed :-) $\endgroup$ – Jeremy Dover Jul 8 at 22:58
5
+100
$\begingroup$

Solution:

AEHAGHC
FJKCJLE
IMGLINF
AKOFPBC
BLPMDKI
HMNOLQG
IQHJANC
BDOBQJD
GNEMCPH
EKPAOQF
BFGDIED

Commentary:

Answers by Chronocidal and subrunner eliminated many grid sizes. I further eliminated the possibility of a 12 color grid (as noted in a comment on Chronocidal's answer). For 17 colors, as suggested by Chronocidal, I preferred to try a 7 by 11 grid which I thought has more interior squares which should be less restrictive. I didn't see any clear reasons why such a grid could not exist.

Solution was found by computer-aided search. I filled in the border of the grid by hand and then took a fairly brute force approach. Program was running for several days in the background before this solution popped out. (Program not particularly efficient or well-designed, but I judged it to have a chance of completion.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have verified your solution and it is correct. Very well done!!! We have our first solution. Now I wonder if there any others for larger grids? $\endgroup$ – Dmitry Kamenetsky Jul 14 at 2:23
  • 1
    $\begingroup$ @DmitryKamenetsky My guess is that many grids are possible provided they do not violate the kinds of restrictions already discussed (or similar restrictions). Larger grids will tend to have a higher ratio of middle squares which ought to make things more permissive. There are probably also multiple grids of this size as well. Including the border, I think my program had only considered variations to about half of the grid before finding this solution which I think is a pretty small fraction of the search space. $\endgroup$ – tehtmi Jul 14 at 2:45
  • 1
    $\begingroup$ Dang, great work! I had written a program to automate the elimination of different grid sizes and "color classes," having just gotten around to implementing every piece of reasoning present in these answers and comments (including generalizing yours on K=12). I was getting worried, though, that if a solution did exist, it would be beyond the realm of efficient computer construction. But this is a great end to things. $\endgroup$ – Feryll Jul 14 at 13:20
  • 2
    $\begingroup$ I'm still going to be investigating the toroidal case, and will post a solution if I find one; I find it to be a lot more fun, given all the symmetries of translation and mirroring. $\endgroup$ – Feryll Jul 14 at 13:21
12
$\begingroup$

I am going to assume that the grid must be at least 2-by-2

This avoids the Trivial Case of $K=3$ using the 4-by-1 pattern ABCA


Every colour must connect to every other colour once, and only once. As such, the number of Connections for $K$ colours must be the $(K-1)^{th}$ Triangular number, or $\frac{(K-1)^2+(K-1)}{2}$, which we can rewrite as $\frac{K^2-K}{2}$

For any X by Y grid (for X>1 and Y>1), each cell has 3 possibilities:

  • $C$orner: Adjacent to 2 other colours
  • $E$dge: Adjacent to 3 other colours
  • $M$iddle: Adjacent to 4 different colours

An $X$ by $Y$ grid has $4$ Corner squares, $2(X-2)+2(Y-2)$ Edge squares and $(X-2)(Y-2)$ Middle squares. Between them, these contribute $8$, $6(X+Y-4)$, and $4(XY-2X-2Y+4)$ half-connections (since connections are paired)

Rearrange that, and you get $2XY-(X+Y)$ connections.

So, as a first rule, we can only fit $K$ colours into an $X$ by $Y$ grid, if $\frac{K^2-K}{2}=2XY-(X+Y)$

Next comes the types of combinations. Every Colour must make exactly $K-1$ connections. If we take your example of $K=10$, then we can make $9$ in 3 different ways:

- $3E=3*(3)$
- $C+E+M=(2)+(3)+(4)$
- $3C+E=3*(2)+(3)$

We can immediately made several deductions from this:

First, we see that every colour must appear on at least 1 Edge Piece (of which there are 14), and, second, that either all 4 Corners are different, or 3 of them are the same colour.

However, we also see that there is only 1 method for using each of our 10 $M$iddle pieces - and this requires 1 Corner per Middle piece. But, there are only 4 Corners!

As such:

It is impossible to solve the puzzle for 10 Colours in a 4*7 grid.


After messing around for a while, going in circles (Literally - I thought I was managing to get somewhere, but all I proved was that the $(K-1)^{th}$ triangular Number was, in fact, a triangular number), I got bored, and brute-forced some Integer Solutions to $\frac{K^2-K}{2}=2XY-(X+Y)$ in Excel. Sorry.

The lowest match integer match to the First Rule that neither subrunner nor myself have proven impossible is $K=12$, for $X=4$ and $Y=10$.

This gives us

- 4 Corners
- 20 Edges
- 16 Middles

How many ways to make $11$?

$4C+1E = 4*(2)+1*(3)$
$2C+1E+1M = 2*(2)+1*(3)+1*(4)$
$1C+3E = 1*(2)+3*(3)$
$1E+2M = 1*(3)+2*(4)$

Excellent, this looks promising. Let's start by eliminating all 4 Corners, and cutting down the Edges:

4 number, each costing 1 Corner and 3 Edges.
The total is then 4 Corners, 12 Edges. This leaves us:
- 0 Corners
- 8 Edges
- 16 Middles
Note: We can't use $4C+1E$, because that leaves 19 Edges and 16 Midles, which are not in a 1:2 ratio. Similarly, we can't use $2C+1E+1M$, because that leaves either 18 Edges and 14 Midles (2 numbers, each in 2 corners) or 13 Edges and 15 Midles (3 numbers, 1 in 2 corners and 2 in 1 corner each), because - again - we do not have the 1:2 ratio

This is absolutely perfect, because:

Our remaining 8 numbers will each cost 1 Edge and 2 Middles.
This adds up to 8 Edges, and 16 Middles - exactly what we have left!

The second lowest answer to our First Rule is $K=17$, for $X=11 \lor 20$ and $Y=7 \lor 4$

This gives us

- 4 Corners
- 28 or 40 Edges
- 45 or 36 Middles

So, how many ways can we make $16$?

- $2C+4E=2*(2)+4*(3)$
- $2C+3M=2*(2)+3*(4)$
- $1C+2E+2M=1*(2)+2*(3)+2*(4)$
- $4E+1M=4*(3)+1*(4)$
- $4M=4*(4)$

This also looks promising - if we allocate a different number to each Corner:

4 numbers, costing 4 Corners, 8 Edges, and 8 Middles
- 0 Corners
- 20 or 32 Edges
- 37 or 28 Middles

Next, we allocate all of the remaining Edges:

5 numbers, costing 20 Edges and 5 Middles or
8 numbers, costing 32 Edges and 8 Middles - 0 Corners
- 0 or 0 Edges
- 32 or 20 Middles

Which leaves us with

8 numbers, costing 32 Middles or
5 numbers, costing 20 Middles

This gives us

3 theoretical grids to test:
$K=12$, 4*10
$K=17$, 7*11
$K=17$, 4*20

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm pretty sure there's a way to expand this answer into a more General Form, but I currently do not have time to do so... Feel free to pick it up an run with it. $\endgroup$ – Chronocidal Jul 8 at 13:28
  • 1
    $\begingroup$ Very nice! Ah forgot about that K=3 case. I will update my question. $\endgroup$ – Dmitry Kamenetsky Jul 8 at 13:54
  • $\begingroup$ @DmitryKamenetsky It's not just $K=3$, it applies to any odd value of $K$ (the First and Last colour will be the same, and will appear 1 more time than the other colours do) $\endgroup$ – Chronocidal Jul 8 at 14:07
  • $\begingroup$ Yep. I've added a constraint that grid sides must be greater than 1, which should rule out those cases $\endgroup$ – Dmitry Kamenetsky Jul 8 at 14:17
  • 2
    $\begingroup$ Argument against K = 12: 24 spaces along the border and 24 connections will appear around the border. 16 spaces taken up by the 4 1C+3E colors. Only 6 (4 choose 2) distinct connections allowed among this group. Can't place 16 people in a circle of 24 chairs with only 6 adjacent pairs: only 8 empty chairs can break up the 16 pairs, so at least 8 adjacent pairs must exist. $\endgroup$ – tehtmi Jul 10 at 11:17
7
$\begingroup$

Another step in the logical chain:

Starting with @Chronocidal's anwer, following can be said:

$\frac{K(K-1)}{2} = 2xy - x - y\\\\$

Now assume our rectangle has the width $x=2$:

$\frac{K(K-1)}{2} = 4y - 2 - y$

$3y = \frac{1}{2}K(K-1) + 2$

$y$ needs to be a positive integer. This equation can only be fulfilled if neither $K$ nor $K-1$ are divisible by three. (Assume that either one is divisible by three, then $S:=\frac{1}{2}K(K-1)$ will be divisible by 3 and thus $S + 2$ is not divisible by three which leads to y being not an integer).

So neither $K$ nor $K-1$ are divisible by three. This can only be the case if there is a natural number $a$ so that $K = 3a + 2$ (it follows that $K-1 = 3a + 1$, and plugging that back into the equation means that $3y = \frac{1}{2}(3a+2)(3a+1) + 2 = \frac{9}{2}a(a+1) + 3$, which is definitely divisible by 3)

So there exists an $a\in\mathbb{N}$ so that $K=3a + 2$. As @Chronocidal has observed, $K$ colors means that there are $K-1$ pairs per color, and that this number must be distributed to Corner (2 pairs), Edge (3 pairs) and Middle (4pairs) spots. Since we have a grid with width 2, we have no middle pieces. However, we need to reach a sum of $K-1=3a+1$ via Edges and Corners: $3e + 2c$ ($e$ is the number of edge spots, $c$ is the number of corner spots).

This is possible if we use either $c=2$ (2 Corner spots) or $c=4$ (all Corner spots). If we use $c=2$, we can have 2 colors at most ($K=2$) - afterwards we run out of corners. For $c=4$, we run out of corners after the first color. However, we must have $K>2$ if we want to have at least a 2x2 grid.

Result for $x=2$:

It is not possible to fill a 2-by-y, y>1 rectangle with K colors so that all conditions are fulfilled.

$x=3$:

$\frac{K(K-1)}{2} = 6y - 3 - y$

$5y = \frac{1}{2}K(K-1) + 3$

Following a similar argument as for $x=2$, it follows that

$\exists a\in\mathbb{N}: K=5a+2 \lor K=5a+3 \lor K=5a+4$ (if either $K$ or $K-1$ were divisible by 5, then S would be divisible by 5 and $S+3=5y$ would not be divisible by five)

Plugging that back into the equation means

K=5a+2: $5y=\frac{1}{2}(5a+2)(5a+1) + 3 = \frac{5}{2}a(5a+3) + 4$, which is not divisible by 5 (due to the +4 at the end)

K=5a+3: $5y=\frac{1}{2}(5a+3)(5a+2) + 3 = \frac{25}{2}a(a+1) + 6$, which is not divisible by 5 (due to the +6 at the end)

K=5a+4: $5y=\frac{1}{2}(5a+4)(5a+3) + 3 = \frac{5}{2}a(5a+7) + 9$, which is not divisible by 5 (due to the +9 at the end)

Result for $x=3$:

There is no $3 \times y, y\in\mathbb{N}$ grid so that the conditions can be fulfilled

===============

Edit 2020-07-15 reversed due to faulty logic...

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You're claiming that $K=17$, $7 \times 11$ is not solvable, but @tehtmi exhibited a solution. $\endgroup$ – RobPratt Jul 15 at 17:29
  • $\begingroup$ yeah, just realized that... trying to figure out where the hole in my logic is... $\endgroup$ – subrunner Jul 15 at 18:06

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.