📄 3_9.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§9 鸽巢原理之二</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="../style.css"></head><body><p align="center"><font size="5"><b>§9 鸽巢原理之二</b></font></p><p> <b>鸽巢原理二 m<sub>1</sub> , m<sub>2</sub> , … , m<sub>n</sub>都是正整数， 并有m<sub>1</sub> + m<sub>2</sub> +… +m<sub>n</sub>－n + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢 中至少有m<sub>i</sub>个鸽子，i = 1 , 2 , … , n．</b><br> 上一小节的鸽巢原理一是这一原理的特殊情况，即<br> m<sub>1</sub> = m<sub>2</sub> = … = m<sub>n</sub>= 2，<br> m<sub>1</sub> + m<sub>2</sub> +… +m<sub>n</sub>－n + 1 = n + 1<br>如若不然，则对任一 i， 都有第 i 个巢中的鸽子数≤m<sub>i</sub>－1 则 鸽子总数≤ m<sub>1</sub> + m<sub>2</sub> +… +m<sub>n</sub>－n ，与假设相矛盾</p><p><b>[推论１]</b> m只鸽子进n个巢，至少有一个巢里有<imgsrc="3_9_1.gif" align="middle" width="33" height="45">只鸽子．</p><p><b>[推论２]</b> n(m－1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子．</p><p><b>[推论３]</b> 若m<sub>1</sub> , m<sub>2</sub> , … , m<sub>n</sub>是正整数，且<imgsrc="3_9_2.gif" align="middle" width="122" height="42">, 则 m<sub>1</sub>,… , m<sub>n</sub>至少有一个不小于r </p><p><b>例</b> 设A= a<sub>1</sub>a<sub>2</sub>···a<sub>20</sub>是10个0和10个1 组成的 ２进制数．B=b<sub>1</sub>b<sub>2</sub>···b<sub>20</sub>是任意的２进制数．<br>C = b<sub>1</sub>b<sub>2</sub>···b<sub>20</sub> b<sub>1</sub>b<sub>2</sub>···b<sub>20 </sub>= C<sub>1</sub>C<sub>2</sub>···C<sub>40</sub>，<br>则 存在某个i ，1≤ i ≤20，使得<br>C<sub>i</sub>C<sub>i+1</sub>···C<sub>i+19</sub>与a<sub>1</sub>a<sub>2</sub>···a<sub>20</sub>至少有10位对应相等．<br><img src="3_9_3.gif" width="565" height="198"><br><b>证</b> 在C = C<sub>1</sub>C<sub>2</sub>···C<sub>40</sub>中，当 i 遍历1 , 2 , … , 20时，每一个b<sub>j</sub>历遍 a<sub>1</sub> , a<sub>2</sub> , … , a<sub>20</sub>．因A中 有10个0和10个1，每一个b<sub>j</sub>都有10位次对应相等．从而当 i历遍1 , … , 20时，共有 10 · 20=200位次对应相等．故对每个 i平均 有200／20 = 10位相等，因而对某个 i 至少 有10位对应相等． </p><p><b>定理</b> 若序列S ={ a<sub>1</sub> , a<sub>2</sub> , … , a<sub>mn+1</sub>}中的各 数是不等的．m , n 是正整数，则 S有一长 度为m+1的严格增子序列或长度为n+1的减 子序列，而且 S有一长度为m+1的减子序列 或长度为n+1的增子序列．<br><b>[证１]</b> 由S中的每个 a<sub>i</sub> 向后选取最长增子序列，设其长度为<i>l</i><sub>i</sub> ，从而得序列 L = { <i>l</i><sub>1</sub> , <i>l</i><sub>2</sub> , … , <i>l</i><sub>mn+1</sub> }．若存在 <i>l</i><sub>k</sub>≥m+1 则结论成立．<br>否则所有的 <i>l</i><sub>i</sub> ∈[ 1 , m]，其中必有<br><img src="3_9_4.gif" width="413" height="172"></p><p><b>[证２]</b> 从a<sub>i</sub> 向后取最长增子列及减子列，设 其长度分别为 l<sub>i</sub> ，l<sup>’</sup><sub>i</sub> . 若任意 i ，都有l<sub>i</sub> ∈[ 1，m], l<sup>’</sup><sub>i</sub>∈［１，n］, 不超过mn种对．则<br> 存在 j ＜k，( l<sub>j</sub> , l<sup>’</sup><sub>j</sub> ) = ( l<sub>k</sub> , l<sup>’</sup><sub>k</sub> ) <br>若a<sub>j</sub>＜a<sub>k</sub>，则 l<sub>j</sub> >l<sub>k</sub>， <br>若a<sub>j</sub>＞a<sub>k</sub>，则 l<sup>’</sup><sub>j</sub> >l<sup>’</sup><sub>k</sub> ，矛盾． </p><p><b>[例]</b> 将[ 1 , 65 ]划分为４个子集，必有一个子集中有一数是同子集中的两数之差．<br><b>[证]</b> 用反证法．<br>设此命题不真．即<br>存在划分P<sub>1</sub>∪P<sub>2</sub>∪P<sub>3</sub>∪P<sub>4</sub>＝[ 1，65 ]，P<sub>i</sub> 中不存在一个数是P<sub>i</sub>中两数之差，i=1,2,3,4 因<img src="3_9_5.gif"align="middle" width="69" height="45">，故有一子集，其中至少有17 个数，设这17个数从小到大为a<sub>1</sub> , … , a<sub>17</sub> ． 不妨设 A={a<sub>1</sub> , … , a<sub>17</sub> }<img src="3_9_6.gif" align="middle" width="18"height="17">P<sub>1</sub>。<br>令b<sub>i－1</sub>= a<sub>i</sub>－a<sub>1</sub>，i = 2，···，17。<br>设 B＝｛b<sub>1</sub>, ··· , b<sub>16</sub>}，B<imgsrc="3_9_7.gif" align="middle" width="18" height="14">[ 1 , 65 ]。<br>由反证法假设B∩P<sub>1</sub> = ф。因而<br>B<img src="3_9_7.gif" align="middle" width="18" height="14">( P<sub>2</sub>∪P<sub>3</sub>∪P<sub>4</sub> )。<br>因为<img src="3_9_8.gif" align="middle" width="61" height="45">，不妨设{b<sub>1</sub> , ··· , b<sub>6</sub>}<img src="3_9_6.gif" align="middle" width="18"height="17">P<sub>2</sub> ， <br>令C<sub>i－1</sub>=b<sub>i</sub>－b<sub>1</sub>，i = 2， ···，6.<br>设C＝{ C<sub>1</sub> , ··· , C<sub>5</sub> }，C<imgsrc="3_9_7.gif" align="middle" width="18" height="14">[ 1 , 65 ]<br>由反证法假设C∩( P<sub>1</sub>∪P<sub>2</sub> ) =ф，故有<br>C<img src="3_9_7.gif" align="middle" width="18" height="14">(P<sub>3</sub>∪P<sub>4</sub> )<br>因为<img src="3_9_9.gif" align="middle" width="53" height="45">，不妨设{C<sub>1</sub> , C<sub>2</sub> , C<sub>3</sub> }<img src="3_9_7.gif" align="middle" width="18"height="14">P<sub>3</sub><br>令 d<sub>i－1</sub>= C<sub>i</sub>－C<sub>1</sub>，i = 2 , 3．<br>设 D＝{ d<sub>1</sub> , d<sub>2</sub> } , D<img src="3_9_7.gif" align="middle"width="18" height="14">[ 1 , 65]。<br>由反证法假设 D∩( P<sub>1</sub>∪P<sub>2</sub>∪P<sub>3</sub> )=ф，因而<br> D<img src="3_9_7.gif" align="middle" width="18" height="14">P<sub>4</sub> 。<br>由反证法假设<br>d<sub>2</sub>－d<sub>1</sub><img src="3_9_10.gif" align="middle" width="14" height="18">P<sub>1</sub>∪P<sub>2</sub>∪P<sub>3</sub> 且d<sub>2</sub>－d<sub>1</sub><img src="3_9_10.gif" align="middle" width="14"height="18">P<sub>4</sub> ，<br>故 d<sub>2</sub>－d<sub>1</sub><img src="3_9_10.gif" align="middle" width="14"height="18">[ 1 , 65 ]，但显然<br>d<sub>2</sub>－d<sub>1</sub> ∈ [ 1 , 65 ]，<br>矛盾。 </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -