5
$\begingroup$

Define a Skolem sequence to be a permutation of the sequence of 2n numbers 0, 0, 1, 1, 2, 2, ..., n-1, n-1 in which there are no numbers between the two 0s (the 0s are in adjacent positions), there is one number between the two 1s, there are two numbers between the two 2s, and more generally the two copies of each number k have k numbers in between them. An example would be:

3 0 0 2 3 1 2 1

Define a Skolem square to be a square matrix such that every row and every column is a Skolem sequence. A trivial example of a Skolem square is:

0 0
0 0

The question is: Do non-trivial Skolem squares exist? If so, what are the possible sizes of a Skolem square? If they don’t exist, why not?

RELATED QUESTIONS:

2x8 Langford Rectangle

The 8-dimensional vegetable kebab

Do Langford squares exist?

$\endgroup$

1 Answer 1

9
$\begingroup$

No non-trivial Skolem squares exist.

First, observe that any number $k$ appearing in a Skolem square must be part of an axis-aligned square of width and height $k$ whose four vertices are all $k$. For example, for $k=3$, this looks like:

3 . . 3
. . . .
. . . .
3 . . 3

This is because each $k$ must have another $k$ that's $k$ units away horizontally and another $k$ vertically, continuing a chain of $k$'s that must eventually close into a loop. If the chain doesn't immediately form a square of four $k$'s but instead turns like the one below (up to reflection and rotation), there's no way for the leftmost and rightmost $k$ to eventually reconnect without placing an additional $k$ in the middle column which isn't allowed.

3 . . 3 . . .
. . . . . . .
. . . . . . .
. . . 3 . . 3

Now, fixing some $k$, let's say two columns are linked if their $k$'s form a square. Each column is linked with exactly one column, and that column is $k$ positions away, either to its left or right. If we 1-index the columns, this means the first $k$ columns must be linked to their right: column $1$ is linked to column $k+1$, column $2$ to column $k+2$, and so on up to column $k$ being linked to column $2k$. Now the first $2k$ columns are all taken, so if there are more columns, the next $k$ must be linked rightward in the same pattern as the first $2k$ columns. If there are less than $2k$ columns left, some will be left without a match and the Skolem square will fail. And so on for the next $2k$ columns, and so on.

Here's an example of how this might look for $k=3$, using matching letters for linked columns, with $n=12$ for 24 columns:

A B C A B C D E F D E F G H I G H I J K L J K L

Observe that this requires $2n$ to be a multiple of $2k$, and so $n$ to be a multiple of $k$. But since $k$ was arbitrary from $1$ to $n$, this means $n$ is a multiple each positive integer below it. This is not possible for $n > 2$, say by considering $k=n-1$. We can rule out $n=2$ separately by noting that placing a square of zeroes must leave the two unoccupied spaces in its rows with 0 or 2 cells in between, which doesn't let 1's be placed. And, $n=1$ gives the trivial square of zeroes. So, we've ruled out non-trivial Skolem squares of any size.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.