在监考十二省联考的时候，我们发现排座位是一件非常麻烦的工作。由于主办单位需求的不同，例如成绩较好的靠前、同一学校的分开、成绩较好的分开、保证一定的随机性等等，我们需要用非常复杂的逻辑安排座位。事实上我们使用了一个简单的爬山，每次随机选择两个学生，如果交换可以使得代价函数降低就交换。

之后为了应付某图论应用技术报告我考虑了一个简化的问题，如果在 $n\times m$ 的网格图上分配座位，有 $n\times m$ 个选手来自 $k$ 个学校，其中第 $i$ 个学校有 $a_i$ 人，该如何分配座位使得任意相邻的两人都来自不同的学校。其中一个座位和其前后左右至多四个座位相邻。这个问题的证明是相对容易的，不过稍加改进便可以推广到任意维立方体的情景。

Theorem. 当且仅当 $\max\{a_i\}\le \lceil \frac{n\times m}{2} \rceil$，存在合法的座位安排方案。

Proof. $(\Leftarrow)$ 容易构造出使用尽可能多的 $1\times 2$ 的骨牌覆盖棋盘的方案，使得要么每个位置都被覆盖，要么仅存在一个单独的位置。整个棋盘被划分为了 $\lceil \frac{n\times m}{2} \rceil$ 组。如果一个学校人数超过一半，根据鸽巢原理，必然有一组中存在两个该学校的人，因而不存在合法的座位安排方案。

$(\Rightarrow)$ 我们希望说明一旦人数最多的学校人数不超过一半，就必然存在合法的座位安排方案。考虑直接构造。首先，若仅有两个学校，由于两者的人数都不超过 $\lceil \frac{n\times m}{2} \rceil$，因此他们必然分别具有 $\lceil \frac{n\times m}{2} \rceil$ 和 $\lfloor \frac{n\times m}{2} \rfloor$ 位选手。将棋盘黑白染色，我们可以将一个学校的人安排在黑色点，另一个学校的人安排在白色点，从而任意两个同校选手必然不相邻。

当学校个数超过 $2$ 时，我们先将所有选手分成人数相等（或差1）的两组，使得仅存在不超过一个学校，满足其选手被分到了两组中。若这样的学校不存在则证完了，否则不妨设这个学校编号为 $i$。由于我们可以将人数最多的学校分配到组 $A$，将人数第二多的学校分配到组 $B$，因此 $i$ 号学校至多是人数第三多的学校，从而其人数不超过 $nm/3$。另一方面，学校 $i$ 被分配到组 $A$ 的人数 $p$ 不超过 $nm/4$，被分配到组 $B$ 的人数 $q$ 也不超过 $nm/4$。

不妨设组 $A$ 有 $\lceil \frac{n\times m}{2}\rceil$ 人，组 $B$ 有 $\lfloor \frac{n\times m}{2} \rfloor$ 人，$(0,0)$ 是黑色点。我们只需将学校 $i$ 的 $p$ 人分配到黑色点，将另外 $q$ 人分配到白色点，使得任意两人不相邻，那么将 $A$ 中的其余人任意分配到黑色点上，$B$ 中的其余人任意分配到白色点上便完成了构造。

考虑这样的构造方案，我们首先从 $(0, 0)$ 开始，逐行逐列将 $p+q$ 人依次分配到黑色点中，然后将最后 $q$ 人向下移动一行。一旦满足：

$$ \frac{(n-1)m}{2} \ge p+q $$

这样的方案就一定可行。而这成立只需：

$$ \frac{(n-1)m}{2} \ge \frac{nm}{3} \iff n \ge 3 $$

根据对称性，一旦 $n\ge 3$ 或者 $m\ge 3$ 便立刻有合法的分组方案，因而也有构造方案。而 $n,m\le 2$ 的情景是平凡的，这就完成了证明。

Theorem. 当 $n\ge 144$ 或存在 $x_i\ge 3$ 时，对于 $x_1\times x_2\times x_3\times \dots \times x_n$ 的超立方体，存在合法的座位安排方案当且仅当：

$$ \max\{a_i\}\le \left\lceil \frac{\prod_i x_i}{2} \right\rceil $$

Proof. 稍加改进便可以知道，如果人数最多的学校人数超过一半仍然不存在方案，并且一旦某个 $x_i\ge 3$，之前的证明仍然成立。下面只需证明 $x_i = 2$ 的情况成立即可。

不妨将所有的位置映射到长度为 $n$ 的 $01$ 串，我们仍然希望将学校 $i$ 的 $p+q$ 个人合理安排，使得 $p$ 个人和另外 $q$ 个人不相邻。考虑这样的构造方案，将 $2^n$ 个不同的位置按照其中 $1$ 的个数分组，分为了大小分别为：

$$ {n\choose 0}, {n\choose 1}, \dots, {n\choose k}, \dots, {n\choose n} $$

的 $n+1$ 组。不失一般性我们设 $p\ge q$，于是前 $p$ 人从前向后选择具有偶数个 $1$ 的组，后 $q$ 人从后向前选择具有奇数个 $1$ 的组。我们只需说明，他们选择的组之中一定存在一个“分割”，保证他们不会选择相邻的组，从而更不会仅相差 $1$。下面用反证法。如若他们“触碰了”，即分配到 $A$ 组的 $p$ 个人占用了组：

$$ {n\choose 0}, {n\choose 2}, {n\choose 4}, \dots, {n\choose i} $$

而分配到 $B$ 组的 $q$ 个人占用了组：

$$ {n\choose i+1}, {n\choose i+3}, \dots {n\choose n-1} (or\ {n\choose n}) $$

那么一定有：

$$ \begin{align} \frac{2^n}{3}\ge p+q &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 4} + {n\choose i + 6} + \dots + {n\choose n-1}(or\ {n\choose n})\\ &\ge {n\choose 0} + {n\choose 2} + \dots + {n\choose i-1} + 1 + 1 + {n\choose i + 5} + {n\choose i + 7} + \dots + {n\choose n}(or\ 0)\\ &\ge 2^{n-1} - 2\times \frac{2^n}{\sqrt{n+1}} \end{align} $$

要有这一点至少有：

$$ \frac{2^n}{3}\ge 2^{n-1} - 2\times\frac{2^n}{\sqrt{n+1}}\iff n\le 143 $$

thx

lkmcfj 提供了第一个定理证明中构造放置方案的方法（另一种简单的构造方案只能给出$m\ge 6$的界），CommonAnts 指出了第二个定理证明中构造放置的方案的方法。

hack

程序似乎写错了，现在 $n\le 12$ 这样的方案不一定能保证有解，但是原问题对 $n\le 4$ 都是有解的。

似乎后一个问题的证明完全有问题...找时间修一下吧orz

fix: 现在只能保证 $n\ge 144$ 是没有问题的..所以还是不知道小的情景怎么说明。

feat: 使用计算机改进第二个定理对组合数的估计可以说明，$n\ge 91$ 总是有解的。