A grid where every combination of two colours appears exactly once

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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...