动机
计数论证有时能保证某个对象存在,而不必求出所有安排的总数。十三名学生各选一个月份,必有两人选中同一月份。我们不需要逐一列举选择,只需观察:如果每个月至多被一人选中,那么十二个月容纳不了十三人。
真正有用的抽屉原理论证,难点往往在于决定什么应当成为“抽屉”。研究整除时,我们将用前缀和的余数作为抽屉;研究有序数列时,我们将用以某个位置结尾的两种子序列长度作为抽屉。这些记录保留了能够随着新元素而延伸的信息。记录发生碰撞,就能导出想要的数学对象。
我们还要问保证是否尖锐。如果证明某个配置在达到一个门槛时必然出现,最好同时构造一个只比门槛少一项、却没有该配置的例子。这样的构造说明定理究竟保证到什么程度。
定义
定义 2.6.1
(对象、抽屉与占用量)
设 是由 个带标号对象组成的有限集, 是整数。把对象分配到 个抽屉,就是给出函数 。第 个抽屉的占用量为 。这些纤维把 分成互不相交的部分,因此
允许空抽屉。上取整 是不小于实数 的最小整数。
抽屉不一定是实体容器,也可以是余数类、区间、颜色,或一对整数标记的可能取值。使用上述求和等式时,每个对象必须恰好属于一个抽屉。互相重叠的区域不自动构成划分;需要交代边界归属,或给出确定的分配规则。
定义 2.6.2
(连续段与子序列)
对数列 ,非空连续段所占的位置是 ,其中 。子序列所占的位置为 ,不要求相邻。若 ,称其严格递增;若不等号全部反向,称其严格递减。只有一项的子序列同时满足两种定义。
如果某个保证在一个整数门槛处成立,但在比它少一项时可以失败,就称这个门槛是尖锐的。这是对最坏情形的保证;某些更短的数列或更小的分配,可能早已包含所要求的配置。
定理/命题
定理 2.6.3
(尖锐的广义抽屉原理)
把 个对象放入 个抽屉,至少一个抽屉有不少于 个对象。对每一组 ,这个界都不能提高。
更一般地,设 是非负整数容量。如果 ,则存在抽屉 满足 。
第二个结论允许各个抽屉有不同的限制。如果希望某个抽屉 达到其指定的正整数目标 ,只需对象数超过 。等于该总数还不够:让第 个抽屉恰有 个对象,便没有一个达到自己的目标。
定理 2.6.4
(存在可整除的连续段之和)
设 是整数。对任意整数 ,存在一个非空连续段,其和能被 整除。
各项可以为零或负数。整除的意思是该和等于某个整数 与 的乘积 ,并不要求这个和为正或非零。
定理 2.6.5
(尖锐的单调子序列保证)
设 是整数。每个由 个两两不同的实数组成的数列,都有长度为 的严格递增子序列,或长度为 的严格递减子序列。对每一组 ,都能构造长度为 、却没有这两类子序列的数列。
这里的“或”允许两个结论同时成立。定理没有断言这样的子序列很多,也没有断言其各项相邻,更没有断言整个原数列单调。
证明思路
把结论失败转化为容量限制
证明
(最大占用量、均衡分配与不同容量)
设 是最大的占用量。因为每个 都有 ,求和得 ,于是 。再利用 是整数,得到 。当 时所有抽屉为空,论证仍成立。
为证明界不能提高,对 作带余除法:写成 ,其中整数 ,。在 个抽屉中各放 个对象,其余抽屉各放 个。如果 ,最大占用量为 ;否则为 。两种情形都恰等于 。当 时,,构造同样适用。
对于不同容量,反设每个 都有 。求和便得 ,与假设的严格不等式矛盾。这也解释了为什么对象数必须超过总容量,仅仅达到总容量并不够。
记录前缀,让相减产生连续段
证明
(两个余数相同的前缀)
定义前缀和
连同空前缀在内,共有 个带索引的前缀。把前缀索引 放入由 模 的唯一余数所标记的抽屉;余数取自 。即使有负的前缀和,抽屉仍恰有 个。抽屉原理保证两个不同索引有相同余数。把它们按大小记为 ,则
由 知道这个段非空;由两个前缀相减知道这个段连续。这是结论中的两个独立要求,两者都依赖于所选的对象,而非仅靠“抽屉原理”四个字。当 时,两个前缀给出唯一的一项段,其整数和当然能被 整除。
标记每个位置能结束多长的子序列
对长度为 的数列,令 表示以位置 结尾的严格递增子序列的最大长度, 表示相应的严格递减最大长度。最大值确实存在:以 结尾的子序列只有有限多个,且至少可以选择只含该项的子序列。因此 。
证明
(互异终点标记对落入 矩形)
取两个位置 。如果 ,就在一个以 结尾的最长递增子序列后添加 。索引仍严格增加,因此 。如果 ,对递减子序列做同样的延伸,就有 。
两两不同的条件保证这两种情形必有一种发生。因此 :至少有一个坐标严格增加,尽管另一个坐标未必增加。
现在反设两类所需的子序列都不存在,则每个终点标记对都属于
这个集合只有 个元素。然而 个终点标记对互不相同,相当于将 个对象放入 个抽屉而没有发生碰撞,与抽屉原理矛盾。所以至少一类所需的子序列存在。
证明透视
两两不同与项数 rs+1 在哪里用到
这个证明分开处理三件事。第一件是每个位置都带有的记录:由于只含一项的子序列总是可用,两个最大值都至少是 ,标记对 因而有定义。第二件是映射 的单射性,这是唯一用到两两不同的步骤。对 , 与 的比较必须严格偏向一方,而每个结果都使一个指定的坐标增加。若允许 ,两种延伸都不合法,记录便可能重合:在 中每个标记对都是 。
第三件是把结论的否定转化为取值范围。若某个 至少为 ,以 结尾的最长递增子序列的最后 项已经是被排除的对象;所以“没有长度为 的递增子序列”恰好表示对每个 都有 ,同理 。项数 只在这里出现,用的是抽屉原理最弱的形式: 个位置不能单射到只有 个元素的集合。论证以矛盾收尾,并没有指出哪一种结论成立;构造例子之后描述的递推才给出明确的见证。
注意,证明并没有断言标记对按每个坐标同时递增。较后位置的递增长度可能较小,而递减长度较大。证明只需要标记对互不相同。
构造达到界限的例子
证明
(依次连接的递减块)
为证明尖锐性,依次连接 个块,每块长 。对 ,第 块为
每块内部递减,但较后块的每个数都大于较前块的每个数。递增子序列因而在每块中至多取一项,长度至多为 。递减子序列不能从较前块进入较后块,只能留在一个块内,长度至多为 。这两个限制证明长度 时两种结论都可能失败,也覆盖了 或 。
终点证明还给出寻找见证的有限过程。对每个位置 ,检查所有更早的位置。令 等于满足 且 的各个 的最大值再加一;没有这样的 时,用零作为该最大值。用条件 同样计算 。对于每个非零最大值,保存一个达到它的更早索引。递推是精确的:从任何较长子序列中删除末项,会留下一个合格的更早终点;反过来,在达到最大值的较早子序列后添加末项,确实取得递推给出的长度。当某个标记达到目标时,沿保存的索引向前追溯,再把结果反序即可。追溯中的索引严格减小,所以一定终止。直接方法至多比较 对数值;存在性定理本身不需要对任意实数表示法作计算效率保证。
例题详解
例题 2.6.6
(含负数时的前缀碰撞)
取 ,数列为 。前缀和是 ,模 的余数是 。
索引 与 的余数相等,给出 。相应连续段为 。索引 与 的相同余数也给出整个数列,其和为 。可以同时有多个合法答案,证明只需要一次碰撞。
如果只比较原数列各项的余数,就得不到这个论证。两项的余数相同,说明它们的差可整除;这里想要的却是连续若干项之和。
例题 2.6.7
(正方形中的五个点)
在 中任意放置五个点,允许落在边界上。把每个坐标区间分为 和 。它们的四个笛卡尔积(Cartesian product)构成互不相交的抽屉,所以每个点恰有一个归属。至少两点位于同一抽屉。
这两点的两个坐标差的绝对值均不超过 ,欧氏距离(Euclidean distance)因此不超过
这保证有一对近点,但没有识别最近的一对。四点不足以保证同一个距离界:取四个顶点,任意两点的距离均至少为 。因此五点这个数量门槛尖锐;这里并没有声称在所有五点论证中,该距离常数也是最优的。
例题 2.6.8
(读懂终点长度标记)
对数列 ,终点长度为
例如 ,因为 递增,但更早的两个长度为 的递增子序列都不能接上 。此外 ,可由 或 达到。最后一个递增长度为 ,见证为 或 。
此时 ,所以五个不同的数必有长度为 的单调子序列。长度为四的 说明门槛尖锐:递增子序列在每个递减数对中至多取一项,而递减子序列只能留在某个数对内。第一个数列中的 是子序列,并不是连续段。
常见错误
反例模式
严格性与重复值
“严格递增或严格递减”的定理不能删去两两不同的条件。数列 连长度为 的严格单调子序列都没有,更不用说长度为 。
允许重复值时,有一个实用的替代结论:每个长度为 的实数数列,都有长度为 的非递减子序列,或长度为 的严格递减子序列。把第一个终点标记改为非递减子序列的最大长度。对于 ,若 ,就能延伸第一个标记;否则 ,能延伸递减标记。标记对互异的证明因而完全适用。等号情形必须归到其中一边,它不能延伸严格递增或严格递减子序列。
常见错误
(平均值不是每个抽屉的下界)
平均占用量不是每个抽屉的下界。二十九个对象放入六个抽屉,保证某个抽屉至少有五个,但也可能全部二十九个都在同一抽屉。同样,一次碰撞不保证见证唯一。存在性证明不能悄悄变成唯一性结论,或精确的解数公式。
常见错误
(被 整除不等于每个余数都出现)
连续和定理保证的是被定理中的 整除,并不保证每个指定余数都能作为某个连续段之和的余数。例如,当 时,全零数列没有任何段和模 余 。
总结
有效的抽屉原理论证,先描述结论失败会怎样限制可能的记录。占用量界限制每个纤维;前缀余数让碰撞相减成为连续和;终点长度则保证,除非已有长单调子序列,否则所有标记对互异。每次都应核对记录的数量、分配规则,以及碰撞究竟能推出什么。最后用尖锐例子检验哪个门槛必不可少,哪些更强结论并不受保证。
练习
快速检查
(二十九个带标号对象放入六个抽屉。求总能保证的最大占用量下界,并构造最大占用量恰好达到该界的安排。是否必有两个抽屉各有至少五个对象?)
解答 · 答案
保证为 。占用量 的总数是 ,最大值为 ,所以不能保证更大的最大值。但不一定有两个抽屉各有至少 个对象: 中只有一个这样的抽屉。这是不同的极值问题;均衡安排只回答最大占用量最小能是多少。
快速检查
(三个抽屉各自的目标占用量分别为 。求至少需要多少个对象,才能保证至少一个抽屉达到自己的目标,并证明少一个对象不够。)
解答 · 答案
若所有目标都未达到,占用量至多分别为 ,总数至多为 。因此 个对象必使某个目标达到。只有 个时,向量 没有达到任何目标。所以最少需要 个。用统一目标取平均会丢失各个容量不同的信息。
快速检查
(对每个 ,证明任意 个整数中,有两个的差能被 整除。说明它与连续和定理有什么不同。对于 ,说明 项不足以保证存在被 整除的非空连续段之和。)
解答
把 个带索引整数放入它们模 的 个余数类。有两个索引位于同一抽屉,相应整数值相减就是 的倍数。原整数不必互异,差可以是零。
这里的对象是原整数;连续和定理中的对象则是由 项构成的 个前缀和。两个前缀之差通过消去共同项成为连续段。两个构造证明的是不同结论。为说明项数门槛的尖锐性,取 项全部为 。每个非空段和都在 与 之间,不能被 整除。该例适用于 ;当 时,空数列同样没有非空段。
快速检查
(证明 中任意七个点必有两点距离不超过 。给出一个安排,说明不能对所有七点安排保证更小的距离。)
解答
把 分成五个区间 ,其中 ,以及最后一个区间 。这是六个互不相交、直径均不超过 的抽屉。七个带索引点中有两个落在同一抽屉,故距离至多为 。
为证明不能提高,取 。任意两个不同位置之间的最小距离为 ,所以任何严格小于 的统一距离界,都会被这个安排否定。
快速检查
(对十三个两两不同的实数,取 、 时,单调子序列定理保证什么?构造十二个不同的数,使两种结论都不成立,并分别解释两种限制。)
解答
因为 ,定理保证长度为 的递增子序列,或长度为 的递减子序列。长度为 时,取
递增子序列在每个递减三元组中至多取一项,因此长度至多为 。递减子序列不能进入较后三元组,因为其中各项都更大,所以长度至多为 。两个结论均失败。仅仅写出这个安排还没有完成尖锐性证明,还必须给出这两个限制的理由。
快速检查
(解释反例模块中允许重复值的替代定理为何在 或 时仍成立。当 时,它说的是什么?)
解答 · 答案
证明只用到终点标记的正整数范围,所以其中一个范围只有一个值时仍适用。若 ,则要么有两项按原顺序非递减,要么每个较早项都严格大于每个较后项;后一种情况下,整个长 的数列都递减。若 ,则要么某个较早项大于某个较后项,要么所有较早项都不大于较后项;后一种情况下,整个长 的数列都非递减。当 时,结论是任意两个实数项要么非递减,要么严格递减,恰好对应 与 两种情形。