UOJ Logo ljt12138的博客

博客

一个有趣的问题和其扩展

2019-06-03 20:18:09 By ljt12138

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

之后为了应付某图论应用技术报告我考虑了一个简化的问题,如果在 $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$ 总是有解的。

评论

qmqmqm
因此 i 号学校至多是人数第三多的学校,从而其人数不超过 n/3这个结论完全错误吧,例如n=m=3,三个学校各有三个人,则第三多的超过了n/3=1
mcfxmcfx
对于 xi=2 的问题,当 n=4,a=[6,5,5] 时似乎是没有解的? n>=8 的情况有一个(可能是对的)的证明:https://mcfx.us/archives/265/

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。