抽屉原理我们从小学就开始接触，直到大学还在学习，其中虽然简单，但也有许多复杂的推广，不乏精妙的数学思想。
本文简单介绍抽屉原理的基本形式及其推广内容，并通过具体例子介绍其使用方法。
一 抽屉原理
简单形式 n+1个物体放进n个抽屉里，则至少有一个抽屉有不少于两个物体。
例1：367个人中，至少两个人生日相同。
事实上，23个人中至少两个人生日相同的概率已经大于50%，60个人则大于99%。
例2：任意n个正整数，总能找出其中若干个，其和为n的倍数。
证明：事实上有以下更强的结论，能找到一段连续的序列，其和为n的倍数。不妨设正整数序列为a1,a2,…,an。构造新序列si=a1+a2+…+ai，把si对n取模：
- 若存在sk%n==0，则a1+a2+…+ak为n的倍数
- 否则，任意sk模n均不为0，则si这n个数模n的值在1~(n-1)的n-1个数中，于是必存在k1、k2(k1<k2)，sk1、sk2模n的余数相同。则sk2-sk1为n的倍数，即a(k1+1)+…+a(k2)为n的倍数
例3：任意六个人中，一定可以找到三个人，其互相认识，或者互不认识。
证明：问题等价于，六个点，两两连线并涂上红色或蓝色，证明存在同色三角形。
任取一点A，其引出五条线，则必存在三条线颜色相同(不妨设为红色)，令其对应的顶点为B、C、D。对于这三点，
- 若有两点连线为红色，则这两点与A组成同色三角形。
- 否则，每两个点的连线均为蓝色，则B、C、D三点组成同色三角形。
加强形式 把q1+q2+…+qn-n+1个物体放进n个抽屉里，则要么第一个抽屉至少有q1个物体，要么第二个抽屉至少有q2个物体，…，要么第n个抽屉至少有qn个物体。
可以看到，简单形式的抽屉原理是q1=q2=…=qn=2的特殊情形。
例4：任意长为n^2+1的实数序列，要么含有长为n+1的递增子序列，要么含有长为n+1的递减子序列。
证明：不妨设原序列为a1, a2, …, an^2+1。
假设不存在长为n+1的递增子序列，令mk表示ak开始的最长递增子序列的长度，则mk<=n。
又显然有mk>=1，于是m1, m2, …, mn^2+1这n^2+1个数落在1到n中，根据抽屉原理，其中至少有n+1个数相等，令其为
mk1 = mk2 = … = m(kn+1) 1 <= k1 <= k2 <= .. <= kn + 1 <= n^2+1
考察这n+1个数，假设有某个i满足aki<aki+1，于是把aki加到aki+1的最长递增子序列的前面可以得到一个以aki开始的递增子序列，即mki>mki+1，与上式矛盾。
于是aki>=aki+1，即ak1 >= ak2 >= … >= akn+1，即存在长度为n+1的递减子序列。得证。
Note：子串是连续的，子序列不一定连续。
Read full article from 抽屉原理 » NoAlGo博客
No comments:
Post a Comment