16
$\begingroup$

A Langford sequence is a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which 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 1 2 1 3 2

Define a Langford square to be a square matrix such that every row and every column is a Langford sequence. The question is: Do Langford squares exist? If so, what is the smallest size of a Langford square? If they don’t exist, why not?

$\endgroup$
7
  • 1
    $\begingroup$ I assume you want to rule out the 2-by-2 square of 1's? $\endgroup$
    – xnor
    Commented Mar 28, 2023 at 19:21
  • 4
    $\begingroup$ @xnor That wouldn't qualify anyway, as there must be a number between the ones. $\endgroup$ Commented Mar 28, 2023 at 19:29
  • 2
    $\begingroup$ Oh, I see, I'd call that two units apart. I think saying one "number in between" would be clearer. $\endgroup$
    – xnor
    Commented Mar 28, 2023 at 19:34
  • 2
    $\begingroup$ @WillOctagonGibson Do you know the answer to this puzzle? $\endgroup$ Commented Mar 28, 2023 at 20:28
  • 1
    $\begingroup$ @DanielMathias A 2-by-2 square of 0's would qualify though. Probably the only possible solution. $\endgroup$ Commented Mar 29, 2023 at 16:15

1 Answer 1

30
$\begingroup$

Langford squares are not possible.

Consider the middle two rows of a $2n \times 2n$ Langford square. They, like all rows, must contain $n$'s. Any $n$ must have a partner $n$ in its column that's $n+1$ spaces above or below it, but that's off the grid for the middle-row $n$'s.

$\endgroup$
5
  • $\begingroup$ Excellent answer! $\endgroup$ Commented Mar 28, 2023 at 22:52
  • $\begingroup$ Strictly speaking this only shows that $n\times n$ Langford squares don't exist for even $n$. (But I think it's fairly trivial to extend it to odd $n$ as well.) $\endgroup$
    – N. Virgo
    Commented Mar 29, 2023 at 4:39
  • 4
    $\begingroup$ @N.Virgo Each row and column of a Langford square is by definition a Langford sequence. A Langford sequence has an even number of entries because the sequence is made of pairs of numbers. Therefore a Langford square with an odd number of rows or columns is impossible. $\endgroup$ Commented Mar 29, 2023 at 5:10
  • $\begingroup$ @WillOctagonGibson right, of course - sorry for the silly comment! $\endgroup$
    – N. Virgo
    Commented Mar 29, 2023 at 6:11
  • 2
    $\begingroup$ @N.Virgo Your comment wasn’t silly; you were being thorough. $\endgroup$ Commented Mar 29, 2023 at 14:32

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.