📄 3_8.htm
字号:
<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><title>§8 鸽巢原理之一</title><meta name="GENERATOR" content="Microsoft FrontPage 3.0"><link rel="stylesheet" href="../style.css"></head><body><p align="center"><font size="5"><b>§8 鸽巢原理之一</b></font></p><p> 鸽巢原理是组合数学中最简单也是最基本的原理，也叫<b> 抽屉原理</b>。即<br><b>“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。” </b></p><p><b>例１</b> 367人中至少有２人的生日相同。<br><b>例２</b> 10双手套中任取11只，其中至少有两只是完整配对的。<br><b>例３</b> 参加一会议的人中至少有２人认识的别的参加者的人数相等。</p><p><b>例４</b> 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数， 其中一个是另一个的倍数。<br><b>证</b> 设n+1个数是 a<sub>1</sub> , a<sub>2</sub> , ··· , a<sub>n+1</sub>。每个数去掉一切2的因子， 直至剩下一个奇数为止。组成序列 r<sub>1</sub> , r<sub>2</sub>, ··· , r<sub>n+1</sub>。这n+1个数仍在 ［1 , 2n]中，且都是奇数。而[1 , 2n]中只有n个奇数 . 故必有 r<sub>i</sub> = r<sub>j</sub> = r , 则<imgsrc="3_8_1.gif" align="middle" width="144" height="30">,若α<sub>i</sub>＞α<sub>j</sub> ，则 a<sub>i</sub> 是 a<sub>j</sub> 的倍数。</p><p><b>例5</b> 设 a<sub>1</sub> , a<sub>2</sub> , ··· , a<sub>m</sub>是正整数序列，则至少存在k和 <i>l</i> , 1≤k≤<i> l</i> ≤m， 使得和 a<sub>k</sub> + a<sub>k+1</sub> + ··· + a<sub><i>l</i></sub> 是m的倍数。<br><b>证</b> 设<img src="3_8_2.gif" align="middle" width="70" height="45">,S<sub>h</sub>≡ r<sub>h</sub> mod m , 0≤r<sub>h</sub>≤m-1，h = 1 , 2 , ··· , m . 若存在<i>l</i> , S<sub><i>l</i></sub>≡0 mod m 则命题成立．否则，1≤r<sub>h</sub>≤m-1．但h = 1 , 2 , ··· , m．由鸽巢原理，故存在 r<sub>k</sub> = r<sub>h</sub> , 即<br>S<sub>k</sub>≡ S<sub>h</sub>，不妨设 h ＞k．则<br>S<sub>h</sub>－S<sub>k</sub> = a<sub>k+1</sub> + a<sub>k+2</sub> +… + a<sub>h</sub> ≡0 mod m </p><p><b>例６</b> 设 a<sub>1</sub> , a<sub>2</sub> , a<sub>3</sub>为任意３个整数，b<sub>1</sub>b<sub>2</sub>b<sub>3</sub>为a<sub>1</sub> , a<sub>2</sub> , a<sub>3</sub>的任一排列， 则 a<sub>1</sub>－b<sub>1</sub> , a<sub>2</sub>－b<sub>2</sub> , a<sub>3</sub>－b<sub>3</sub>中至少有一个是偶数．</p><p><b>证</b> 由鸽巢原理， a<sub>1</sub> , a<sub>2</sub> , a<sub>3</sub>必有两个同奇偶．设这３个数被２除的余数为 xxy， 于是b<sub>1</sub> , b<sub>2</sub> , b<sub>3</sub>中被２除的余数有２个x，一个y．这样a<sub>1</sub>－b<sub>1</sub> , a<sub>2</sub>－b<sub>2</sub> , a<sub>3</sub>－b<sub>3</sub> 被２除的余数必有一个为０．</p><p><b>例７</b> 设a<sub>1</sub> , a<sub>2</sub> , ··· , a<sub>100</sub>是由 1和２组成的序列 , 已知从其任一数开始的顺序10个数的 和不超过16．即<br>a<sub>i</sub> + a<sub>i+1</sub> +… + a<sub>i+9</sub> ≤16，1≤ i ≤91<br>则至少存在 h 和 k ，k > h，使得<br> a<sub>h</sub> + a<sub>h+1</sub> +… + a<sub>k</sub> = 39<br><b>证</b> 令<img src="3_8_3.gif" align="middle" width="70" height="45">，j =1 , 2 , … ,100 显然S<sub>1</sub>＜S<sub>2</sub>＜…＜S<sub>100</sub>，且 S<sub>100</sub>=(a<sub>1</sub> + … +a<sub>10</sub>)+(a<sub>11</sub> + … +a<sub>20</sub>)+…+(a<sub>91</sub> + … +a<sub>100</sub>) 根据假定有<br> S<sub>100</sub>≤10×16=160，<br>作序列S<sub>1</sub>, S<sub>2</sub> , … , S<sub>100</sub> , S<sub>1</sub> +39, … , S<sub>100</sub>+39 .共200项．其中最大项 S<sub>100</sub>+39≤160+39由鸽巢原理，必有两项相等． 而且必是前段中某项与后段中某项相等．设 S<sub>k</sub>=S<sub>h</sub> + 39，k＞h, S<sub>k</sub>－S<sub>h</sub> =39 即 a<sub>h</sub> + a<sub>h+1</sub> +… + a<sub>k</sub> = 39 </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -