Can you paint the cells of a 4x4 grid with 7 colours such that every pair of different colours is orthogonally adjacent at least once?
Bonus: Can you achieve this with one cell unpainted?
$\begingroup$
$\endgroup$
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
2
Answer:
Yes, I can!
Explanation:
-
2$\begingroup$ That's correct, well done! Now you can try the bonus. $\endgroup$Dmitry Kamenetsky– Dmitry Kamenetsky2026-03-29 15:02:22 +00:00Commented 2 days ago
-
3$\begingroup$ @DmitryKamenetsky. I’ve been trying and it feels impossible, but I don’t have a nice argument yet. reveal spoilerI can trivially rule out a central square being unpainted because that would leave only 20 edge-adjacent pairs, whereas we need 21. So have to think only about square on an edge or at a corner. $\endgroup$Pranay– Pranay2026-03-29 16:59:01 +00:00Commented 2 days ago
$\begingroup$
$\endgroup$
4
The minimum number of colored cells, obtained via integer linear programming, is
15:
-
$\begingroup$ Nice! Is there any solution where reveal spoilera square on the edge (not corner) is uncoloured? $\endgroup$Pranay– Pranay2026-03-29 17:28:32 +00:00Commented 2 days ago
-
3$\begingroup$ @Pranay there is no such solution. $\endgroup$RobPratt– RobPratt2026-03-29 17:36:27 +00:00Commented 2 days ago
-
$\begingroup$ If an edge is missing the puzzle is impossible. Here's why: There would be exactly 21 adjacencies, and we need exactly 21 pairs. Therefore no duplicates allowed. Next, if you mark off in each box how many adjacencies it has, you get this: 2 2 - 1 3 4 3 3 3 4 4 3 2 3 3 2 Each of the 7 colors must occupy boxes which sum to 6 exactly. That means the three central 4s need a 2, the 1 needs a 2 and a 3 and the 3s need another 3. Assign colors 1,2,3 to the central 4s. Color 4 to the "1" corner and color 5 to the 4th central square. Forces 6 and 7 to the edge below the 1" corner $\endgroup$Six-Figure Logic– Six-Figure Logic2026-03-31 12:09:47 +00:00Commented 16 hours ago
-
$\begingroup$ cont'd... Fill in the grid and you'll see now that color 6 borders 4 (above), 5 (left) and 7 (below). it needs now to border 1, 2 and 3, but there is no where else it can go that is adjacent to a square which can have a 1,2,3 around it. note: to check this, notice that no two diagonals can share a number, nor two squares on opposite side of the same box, so as to avoid repeat pairs. $\endgroup$Six-Figure Logic– Six-Figure Logic2026-03-31 12:15:37 +00:00Commented 16 hours ago
$\begingroup$
$\endgroup$
3
I wrote a program to convince myself there are no 15-cell colorings.
I found two solutions modulo rotations, reflections and color permutations.
-
$\begingroup$ Your left solution is the same as RobPratt’s answer. $\endgroup$Pranay– Pranay2026-03-29 20:02:46 +00:00Commented 2 days ago
-
2$\begingroup$ Indeed. The point was that there are 2 solutions in total. And I wanted to show the similarities between the two. $\endgroup$Florian F– Florian F2026-03-29 21:05:23 +00:00Commented 2 days ago
-
$\begingroup$ I understand! The right solution is obtained from the left by permuting a 2, a 3, and a 5 cyclically, and moving the 0 in the corner to the empty corner. $\endgroup$Pranay– Pranay2026-03-29 21:10:04 +00:00Commented 2 days ago
$\begingroup$
$\endgroup$
Not an answer, moreso a simple counting proof that 14 cells or less cannot be done:
Consider the grid as follows:
0 1 2 3
4 5 6 7
8 9 A B
C D E F
It is then easy to see that for the first row, 0, 1, 2 each admit 2 unique pairs in a "lowercase r shape" (01, 04; 12, 15, NOT 10; 23, 26, NOT 21), and 3 admits the pair 37. Thus, each row admits 7 additional unique pairs, barring the last row, which admits 3: CD, DE, EF.
Thus the 4x4 grid admits 3x7+3 = 24 unique pairs. Removing a center removes 4 pairs, which destroys any possible solutions. So a 15-cell solution may be obtained via removing a corner square (which has been done), or an edge square (which has not yet been done).
Removing 2 corners re-introduces the problem of there only being 20 unique pairs, and so there are no solutions that use 14 cells.
$\begingroup$
$\endgroup$
Here's my solution to the standard problem:
I just started with 7 colors, and then added more in as needed (seeing which colors needed which adjacencies), while also keeping in mind that corners only have 2, edges have 3 and centers have 4 "pairs". this helps keep things balanced as the board fills up.
