提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【组合数学】鸽巢原理 ( 鸽巢原理简单形式示例 4、5 )

原理 简单 示例 组合 数学 形式
2023-06-13 09:17:48 时间

文章目录

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

假设有

3

个

7

位二进制数 ,

A : a_1a_2a_3a_4a_5a_6a_7
B : b_1b_2b_3b_4b_5b_6b_7
C : c_1c_2c_3c_4c_5c_6c_7

证明存在整数

i

和

j

,

1\leq i \leq j \leq 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\leq i \leq j \leq 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} \geq 2

, 即

\alpha_i \geq 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}

的倍数 ;

相关文章