🔍 点击查看可视化演示 (landford.html)
兰福德问题（Langford Problem）
问题描述
有 8 块砖头，规则如下：
- 两黑砖之间隔 1 块
- 两红砖之间隔 2 块
- 两黄砖之间隔 3 块
- 两紫砖之间隔 4 块
简而言之：
两黑 （间隔 1）
两红 （间隔 2）
两黄 （间隔 3）
两紫 （间隔 4）
答案
答案有两种（互为镜像），其中一种排列方式如下：
紫、黑、黄、黑、红、紫、黄、红
验证一下：
- 紫： 在第 1 位和第 6 位（中间隔了 2, 3, 4, 5，共 4 块）。
- 黑： 在第 2 位和第 4 位（中间隔了 3，共 1 块）。
- 黄： 在第 3 位和第 7 位（中间隔了 4, 5, 6，共 3 块）。
- 红： 在第 5 位和第 8 位（中间隔了 6, 7，共 2 块）。
另一种解法（倒过来排）：
红、黄、紫、红、黑、黄、黑、紫
两个数学问题
有两个问题是兰福德问题（Langford Problem）的核心。第一个问题是数论推导（为什么有的 n 无解），第二个问题是代数计数（如何用多项式算出解的数量）。
第一部分：为什么 n 必须模 4 余 0 或 3 才有解？
这是一个基于“位置求和（Position Sum Argument）”的数论证明。
假设我们有 n 对数字（即 1 到 n），总共 2n 个位置。
对数字 k，它的两个位置分别为 \( p_k \) 和 \( q_k \)，满足：
\[ q_k = p_k + k + 1 \]
所有位置的总和为：
\[ S = 1 + 2 + \dots + 2n = n(2n+1) \]
另一方面，每一对数字占据的位置和为：
\[ p_k + q_k = 2p_k + k + 1 \]
于是：
\[ n(2n+1) = \sum_{k=1}^{n} (2p_k + k + 1) = 2\sum_{k=1}^{n} p_k + \frac{n(n+1)}{2} + n \]
化简可得：
\[ n(3n-1) = 4\sum_{k=1}^{n} p_k \]
因此， \( n(3n-1) \) 必须是 4 的倍数。逐一检验 \( n \pmod 4 \) 的情况，可得：只有当 \( n \equiv 0 \) 或 \( 3 \pmod 4 \) 时，方程才可能成立。
第二部分：多项式乘法解法（Godfrey–Smith算法）
该方法将组合排列问题转化为代数问题。
以 \( n=3 \) 为例，共有 6 个位置 \( x_1, \dots, x_6 \)。
对每个数字 k，构造一个多项式，列出其所有可能占据的位置对。
\[ P_1 = x_1 x_3 + x_2 x_4 + x_3 x_5 + x_4 x_6 \]
\[ P_2 = x_1 x_4 + x_2 x_5 + x_3 x_6 \]
\[ P_3 = x_1 x_5 + x_2 x_6 \]
将三者相乘：
\[ Q = P_1 \cdot P_2 \cdot P_3 \]
展开后，每一项对应一种放置方案。合法解要求每个位置变量恰好出现一次，即项为：\( x_1 x_2 x_3 x_4 x_5 x_6 \)，该项的系数即为解的个数。
对于 \( n=3 \)，存在合法解，例如序列：312132。