15
$\begingroup$

Given a 4-by-4 array of distinct words, is it possible to scramble the array in four different ways in such a fashion that each possible word-pair appears adjacently in one of the five arrays (the original array along with the four scrambled arrays)?

Notice that among 16 words there are 120 word-pairs, and that each of the five arrays produces 24 adjacencies, so the governing inequality is tight.

Equivalently, we are trying to express the complete graph on 16 vertices as the union of five disjoint subgraphs, each of which is isomorphic to the square-grid-graph with 16 vertices and 24 edges.

As the title of the post suggests, this question is prompted by the “Connections” puzzles that have recently been appearing in the New York Times: see https://www.nytimes.com/games/connections

I’d also be interested in knowing about the $n$-by-$n$ case (with $(n^2+n)/4$ arrays) or the more symmetrical version of the problem with wrap-around adjacency (with $(n^2-1)/4$ arrays) for suitable $n$. I have found a solution to the latter when $n$ is a prime congruent to 3 mod 4; see the comments.

Improve this question
$\endgroup$
2
  • $\begingroup$ (1 of 2) Regarding the wrap-around-adjacency variant I referred to at the end: Let $p$ be a prime of the form $4k+3$ so that the ring of Gaussian integers modded out by $p$ is a field $F$ with $p^2$ elements that we write as $a+bi$ with $-(p-1)/2 \leq a,b \leq (p-1)/2$ forming a $p$-by-$p$ “reference array”. Let $Q$ be the set of $a+bi \in F$ with $1 \leq a \leq (p-1)/2$ and $0 \leq b \leq (p-1)/2$. Write $Q$ as $\{q_1,…,q_m\}$ with $m = (p^2-1)/4$. Now form $m$ $p$-by-$p$ arrays, where the $j$th array is obtained from the reference array by multiplying the respective entries by $q_j$ mod $p$. $\endgroup$
    – James Propp
    Commented Feb 6 at 12:02
  • $\begingroup$ (2 of 2) The fact that the $4m$ elements $q_k$, $-q_k$, $iq_k$, and $-iq_k$ with $1 \leq k \leq m$ are all distinct readily implies that no adjacencies are repeated, which (given the tightness of the governing bound) implies that all adjacencies occur. $\endgroup$
    – James Propp
    Commented Feb 6 at 12:03

1 Answer 1

Reset to default
16
$\begingroup$

Yes, here is one solution for the 4-by-4 case found by a computer search. Each array is obtained from the previous one by applying the permutation (0 1 2 3 4)(5 6 7 8 9)(10 11 12 13 14) to the entries.

\begin{bmatrix} 7 & 5 & 9 & 11\\ 15 & 0 & 1 & 8\\ 12 & 6 & 10 & 13\\ 4 & 2 & 14 & 3 \end{bmatrix}

\begin{bmatrix} 8 & 6 & 5 & 12\\ 15 & 1 & 2 & 9\\ 13 & 7 & 11 & 14\\ 0 & 3 & 10 & 4 \end{bmatrix}

\begin{bmatrix} 9 & 7 & 6 & 13\\ 15 & 2 & 3 & 5\\ 14 & 8 & 12 & 10\\ 1 & 4 & 11 & 0 \end{bmatrix}

\begin{bmatrix} 5 & 8 & 7 & 14\\ 15 & 3 & 4 & 6\\ 10 & 9 & 13 & 11\\ 2 & 0 & 12 & 1 \end{bmatrix}

\begin{bmatrix} 6 & 9 & 8 & 10\\ 15 & 4 & 0 & 7\\ 11 & 5 & 14 & 12\\ 3 & 1 & 13 & 2 \end{bmatrix}

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Kirby: Great! Thanks very much. Did you have some reason to think that there’d be a solution of this kind, associated with a permutation of order 5? $\endgroup$
    – James Propp
    Commented Feb 6 at 17:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .