一、鸽巢原理简单形式示例 4

假设有 $3$ 个 $7$ 位二进制数 ,

$A:a_1{a}_2{a}_3{a}_4{a}_5{a}_6{a}_7$
$B:b_1{b}_2{b}_3{b}_4{b}_5{b}_6{b}_7$
$C:c_1{c}_2{c}_3{c}_4{c}_5{c}_6{c}_7$

证明存在整数 $i$ 和 $j$ , $1\le i\le j\le 7$ , 使得下列之一一定成立 :

$a_i=a_j=b_i=b_j$
$a_i=a_j=c_i=c_j$
$b_i=b_j=c_i=c_j$

证明 :

二进制数 , 取值只能是 $0$ 或 $1$ ;

使用表格图形表示 $ABC$ 三个二进制数的 $7$ 位 : 使用二进制数 $0,1$ 填写这些位 ;

上图中 :

• 第 $1$ 行是 二进制数字 $A$ 的 $7$ 位 ;
• 第 $2$ 行是 二进制数字 $B$ 的 $7$ 位 ;
• 第 $3$ 行是 二进制数字 $C$ 的 $7$ 位 ;

使用二进制数 $0,1$ 填写表格中的这些位 ;

总结出以下模式 : 以列为单位 , 总结出一定的模式 , 下面的模式中每一列的第 $1\sim 3$ 行取值为某数 ;

• ① $1-2-0$ : 某列 第 $1$ 行 , 第 $2$ 行 , 取值为 $0$ , 第 $3$ 行取值随意 ;
  

• ② $1-2-1$ : 某列 第 $1$ 行 , 第 $2$ 行 , 取值为 $1$ , 第 $3$ 行取值随意 ;
  

• ③ $1-3-0$ : 某列 第 $1$ 行 , 第 $3$ 行 , 取值为 $0$ , 第 $2$ 行取值随意 ;
  

• ④ $1-3-1$ : 某列 第 $1$ 行 , 第 $3$ 行 , 取值为 $1$ , 第 $2$ 行取值随意 ;
  

• ⑤ $2-3-0$ : 某列 第 $2$ 行 , 第 $3$ 行 , 取值为 $0$ , 第 $1$ 行取值随意 ;
  

• ⑥ $2-3-1$ : 某列 第 $2$ 行 , 第 $3$ 行 , 取值为 $1$ , 第 $1$ 行取值随意 ;

有以上 $6$ 种可能的模式 , 但是二进制数有 $7$ 位 ;

可以等价理解为鸽巢原理的 : 将 $7$ 个物体放到 $6$ 个盒子中 , 则 至少有一个盒子中有 $2$ 个 或 $2$ 个以上的物体 ;

因此至少有 $2$ 列或 $2$ 列以上的模式相同 ;

模式相同的两列中 , 还有四角数字相同的矩形 , 四角方格数字满足相同的要求 ;

因此 , 必定存在整数 $i$ 和 $j$ , $1\le i\le j\le 7$ , 使得下列之一一定成立 :

$a_i=a_j=b_i=b_j$
$a_i=a_j=c_i=c_j$
$b_i=b_j=c_i=c_j$

二、鸽巢原理简单形式示例 5

证明 : $1$ 到 $2n$ 的正整数中 , 任取 $n+1$ 个数 , 至少有一对数 , 其中一个数是另外一个数的倍数 ;

使用如下形式表示 $1$ 到 $2n$ 的正整数 ;

上述数字每个数字 , 除以 $2^{{\alpha }_i}$ , 会得到一个奇数 $r_i$ ;

使用 $a_i=2^{{\alpha }_i}{r}_i$ , $i=1,2,\cdots ,n+1$ 形式表示上述 $1$ 到 $2n$ 的正整数 ;

$1$ 到 $2n$ 的正整数表示说明 : ( 仅做参考 )

• 表示奇数 : 奇数 $r_i$ 就等于表示的正整数值 , $2^{{\alpha }_i}=1$ , 即 ${\alpha }_i=0$ ;
• 表示偶数 : 如果是偶数 , 至少能除以一个 $2$ , $2^{{\alpha }_i}\ge 2$ , 即 ${\alpha }_i\ge 1$ ;

$1$ 到 $2n$ 的正整数 中 , 有 $n$ 个奇数 , 是 $1,3,5,7,9,\cdots ,2n-1$ ;

每个数 $a_i=2^{{\alpha }_i}{r}_i$ 右侧的 $r_i$ 奇数 取值只有 $n$ 种 , 偶数部分的右侧的 $r_i$ 奇数也包含在其中 ;

现在要从 $1$ 到 $2n$ 的正整数 中 取 $n+1$ 个数 , 如果其中有奇数 , 肯定只有 $n$ 种取值 ;

将取值看做盒子 , 每个数的右边的 $r_i$ 看做物体 , 奇数的个数是 $n+1$ 个 , 但是奇数的个数只有 $n$ 种取值 , 因此有两个数字的 奇数部分 $r_i$ 是相等 ;

假设这两个数分别是第 $i$ 个数 , 和第 $j$ 个数 : $r_i=r_j$ , 并且 $i<j$ ;

• 第 $i$ 个数 : $a_i=2^{{\alpha }_i}{r}_i$ , $i=1,2,\cdots ,n+1$
• 第 $j$ 个数 : $a_j=2^{{\alpha }_j}{r}_j$ , $j=1,2,\cdots ,n+1$

如果 $r_i=r_j$ , 那么 $2^{{\alpha }_j}$ 肯定是 $2^{{\alpha }_i}$ 的倍数 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109105928