还记得小时候有一道经典奥数题，大概是让你把两个数字 1 、两个数字 2 、两个数字 3 和两个数字 4 排成一个 8 位数，使得其中两个数字 1 之间正好夹着 1 个数字，两个数字 2 之间正好夹着 2 个数字，两个数字 3 之间正好夹着 3 个数字，两个数字 4 之间正好夹着 4 个数字。稍作尝试便可得出正确答案： 4, 1, 3, 1, 2, 4, 3, 2 。如果把逆序后的数列视作本质相同的数列，那么上面这个答案是唯一的。这个问题是由 C. Dudley Langford 在 1958 年提出的，因此我们把它叫做 Langford 数列。

    当 n = 3 时， Langford 数列也是唯一的： 2, 3, 1, 2, 1, 3 。我小时候曾经没日没夜地试图寻找 n = 5 时的 Langford 数列，结果却怎么也找不到。后来才知道， n = 5 时的 Langford 数列根本就不存在。这是为什么？你能证明这一点吗？

    Donald Knuth 的 The Art of Computer Programming 第四卷开篇就提到了 Langford 数列问题。书中有一段非常精彩的证明。

    为了把 {1, 1, 2, 2, 3, 3, 4, 4, 5, 5} 按照要求放进 _ _ _ _ _ _ _ _ _ _ 这 10 个格子里，我们需要让两个数字 1 要么都在奇数编号的格子里，要么都在偶数编号的格子里。类似地，两个数字 3 的位置编号也具有相同的奇偶性，两个数字 5 的位置编号也具有相同的奇偶性，而两个数字 2 的位置编号则会一奇一偶，两个数字 4 的位置编号也会一奇一偶。然而，我们一共有 5 个奇数编号的格子和 5 个偶数编号的格子，你会发现它们无论如何也不可能既无重复又无遗漏地被填满。

    事实上，在 2n 个格子中，奇数编号的格子和偶数编号的格子总是各占一半，因此我们总是要求 {1, 1, 2, 2, …, n, n} 占据相同数目的奇数编号格子和偶数编号格子。其中，每一对偶数都会非常听话地占据奇偶格子各一个，因而填满格子的艰巨任务就落在了奇数身上。由于每一对奇数只占据其中一种格子，因此我们必须要有偶数对奇数才行。这意味着，在 1, 2, …, n 当中必须有偶数个奇数才行。由此可知，只有 n = 3, 4, 7, 8, 11, 12, … 时，即形如 4m – 1 或者 4m 时， Langford 数列才存在。

    不过，当 n = 4m – 1 或者 n = 4m 时， Langford 数列一定存在吗？换句话说，刚才的条件同时也是充分的吗？ 1959 年， Roy Davies 给出了一种构造解，从而证明了这一点。让我们首先来看一下 n = 4m 时 Langford 数列的构造方法。我把整个构造过程分成 6 步，如下图所示。图中显示的是 n = 100 时的例子，其中 _____(x)_____ 表示连续 x 个还没有填数进去的空格，省略号表示连续奇数或者连续偶数。

    每一步我们都会把还没有用过的数成对地填进剩余的空格里。各个步骤的文字说明如下：

      （1）填入两个 4m – 4 和两个 4m ；
      （2）填入两个 2m – 1 ；
      （3）用连续奇数和连续偶数填充部分空白；
      （4）填入两个 4m – 2 ；
      （5）再次用连续奇数和连续偶数填充部分空白；
      （6）在最后剩下的两个空格中填入两个 4m – 1 。

    当 n = 4m – 1 时，只需要在 n = 4m 时的构造上做一点修改即可：把最后两项（分别是 4m 和 2m – 1 ）去掉，然后把中间的那项 4m 改成 2m – 1 。不过，这个构造解并不是唯一解。当 n = 12 时，一共有 108144 个解，上述构造解只是其中之一。