10
$\begingroup$

This is a variation of my previous puzzle

Can you paint a $4 \times 4$ grid with $4$ colors, such that for every color the Euclidean distance* between any pair of cells of that color is distinct? Good luck!

*The Euclidean distance between cells $(r_1,c_1)$ and $(r_2,c_2)$ is $\sqrt{(r_1-r_2)^2+(c_1-c_2)^2}$.

$\endgroup$
1
  • 1
    $\begingroup$ Does this mean: for each colour c, the set of distances between cells of colour c must have 6 distinct elements; or does it mean that the set of all distances between cells of the same colour must be a set with 24 distinct elements? $\endgroup$
    – Hammerite
    Nov 23 '21 at 16:56
10
$\begingroup$

I think the answer is

Yes

C D D B
A C B C
A D A C
D B B A

First of all,

I identified all the possible distances on the 4x4 grid. They are: 1 (1x0), 2 (1x1), 4 (2x0), 5 (2x1), 8 (2x2), 9 (3x0), 10 (3x1), 13 (3x2), 18 (3x3). Since there are 9 possible distances in total, we can't have five cells with the same color (which makes 10 distances which can't be all different due to Pigeonhole principle). Therefore, each of 4 colors must occupy 4 cells each.

Then,

I went ahead to find some 4-cell patterns with six different distances that fit on a 4x4 grid:

o . . o
. o . o (1, 2, 4, 5, 9, 10)

o . o
o . .
. . .
. . o (1, 4, 5, 8, 9, 13)

o . o .
o . . .
. . . .
. . . o (1, 4, 5, 10, 13, 18)

o . . .
o . o .
. . . o (1, 2, 4, 5, 10, 13)

the last of which is pretty interesting because

given the two portions of the pattern

A . . .
A . B .
. . . B

rotating each pattern would fill the 4x4 grid nicely without overlapping

B A A B
A B B A
A B B A
B A A B

and therefore the entire grid. This gives the answer at the top.

$\endgroup$
4
  • $\begingroup$ Very nice solution, well done! $\endgroup$ Nov 22 '21 at 9:43
  • 1
    $\begingroup$ Can you find other solutions? $\endgroup$ Nov 22 '21 at 9:58
  • 1
    $\begingroup$ @DmitryKamenetsky I solved it by specifically looking for the 90-degree symmetry, and found a different solution ( row column coordinates 1,1; 2,1; 2,4; 3,3). There are probably many solutions without that symmetry. $\endgroup$ Nov 22 '21 at 10:16
  • 1
    $\begingroup$ Now I can see a couple other patterns that can fill two T-shapes, one symmetric (2,7,13,14/3,4,10,15) and another asymmetric (4,7,13,14 and the rest). That already makes quite a few different solutions. $\endgroup$
    – Bubbler
    Nov 22 '21 at 10:22
4
$\begingroup$

It seems that

There are 106 solutions, not accounting for symmetries and rotations.

Here are some ways

to color the grid
enter image description here
enter image description here
enter image description here

These were found with an exhaustive algorithmic search. My code in R:

    # Create the grid
grid<-data.frame(x=1:4,b=1) %>% left_join(data.frame(y=1:4,b=1)) %>% mutate(b=1:16)
squaredDiff<-function(a) (a-lag(a))^2
squaredDist<-function(n,p){grid %>% filter(b %in% c(n,p)) %>% summarise(across(.cols = c(x,y),.fns = squaredDiff)) %>% sum(na.rm=TRUE)}

# list possible ways to place one colour
solutions<-data.frame(p1=numeric(0),p2=numeric(0),p3=numeric(0),p4=numeric(0))
for(p1 in 1:13){
  for(p2 in (p1+1):14){
    for(p3 in (p2+1):15){
      d<-c(squaredDist(p1,p2),squaredDist(p1,p3),squaredDist(p3,p2))
      if(!anyDuplicated(d)){
        for(p4 in (p3+1):16){
          dd<-c(d,squaredDist(p1,p4),squaredDist(p4,p3),squaredDist(p4,p2))
          if(!anyDuplicated(dd)){
            solutions %>% add_row(p1,p2,p3,p4)->>solutions
          }
        }
      }
    }
  }
}
# There are 184 ways
l<-nrow(solutions)

# sets of 4 solutions
setOf4<-data.frame(s1=numeric(0),s2=numeric(0),s3=numeric(0),s4=numeric(0))
for(s1 in 1:(l-3)){
  for(s2 in (s1+1):(l-2)){
    v<-c(solutions[s1,],solutions[s2,]) %>% unlist %>% unname()
    if(!anyDuplicated(v)){
      for(s3 in (s2+1):(l-1)){
        vv<-c(v,solutions[s3,]) %>% unlist %>% unname()
        if(!anyDuplicated(vv)){ print(vv)
          for(s4 in (s3+1):l){
            vvv<-c(vv,solutions[s4,]) %>% unlist %>% unname()
            if(!anyDuplicated(vvv)){ print(vvv)
              setOf4<<-setOf4 %>% add_row(s1,s2,s3,s4)
            }
          }
        }
      }
    }
  }
}
# There are 106 solutions
nrow(setOf4)->nbSolutions

# Visualization
oneSetOf4<-tibble(x=numeric(),y=numeric(),c=numeric())
solutions %>% filter (row_number() %in% (setOf4[sample(x = 1:nbSolutions,size = 1),] %>% unlist %>% unname)) -> tempTab
for(c in 1:4){
  for(d in (tempTab[c,] %>% unlist %>% unname)) {
    oneSetOf4 %>% bind_rows(grid %>% filter(b==d) %>% select(x,y) %>% mutate(c=c)) -> oneSetOf4
  }
}
oneSetOf4 %>% mutate(c=as.character(c)) %>%  gf_tile(c~x+y) + theme_minimal() + scale_fill_brewer(palette = "YlOrRd") +theme(legend.position = "none")
$\endgroup$
7
  • 1
    $\begingroup$ great work! I didn't realize there are so many. $\endgroup$ Nov 22 '21 at 13:16
  • 1
    $\begingroup$ @DmitryKamenetsky : I adapted my code for any grid size and I had the surprise to discover that with n=5, there is no solution to put the 5 colors, even though there are 280 configurations for choosing 5 tiles with distinct distances. $\endgroup$
    – Evargalo
    Nov 22 '21 at 14:43
  • 2
    $\begingroup$ This is my finding too. For n>4 I couldn't find any solutions with n colours. $\endgroup$ Nov 22 '21 at 23:28
  • 1
    $\begingroup$ I can confirm that there is no solution for n=6 either (and only 16 ways to place one color). $\endgroup$
    – Evargalo
    Nov 23 '21 at 7:21
  • 2
    $\begingroup$ @GregMartin In the linked puzzle it was already shown that the number of ways of placing n pieces of one colour is impossible for n=8, so this puzzle is impossible too. No larger ones have been found. According to the video in the linked answer, size 16 and larger are proved impossible. It is unclear to me whether sizes 11-15 have been fully checked. (I think I did 8-10 myself.) So it looks like there can be no solutions to the n-colour version for n>4. $\endgroup$ Nov 23 '21 at 14:31

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.