鸽巢原理 :
将
个物体 放到
个盒子 中 , 则
一定存在一个盒子 中 至少 含有
个 或
个以上的物体 ;
鸽巢原理 实际上是 多对少的配置 ; 至少存在一个多对一的情况 ;
证明 : 在边长为
的正三角形中 , 有
个点 , 一定存在两个点的距离小于
;
将变成为
的正三角形 , 分为
个小的正三角形 , 每个边长为
; 如下图 :
在
个小正方形中 , 绘制
个点 ;
根据鸽巢原理 , 上述问题可以转为 将
个物体放入
个盒子中 , 至少有一个盒子中有
个 或
个以上的物体 ;
在一个正三角形格子中 , 如果绘制了两个点 , 其距离肯定小于
;
证明 :
的方格 , 使用黑色 , 白色 两种颜色进行涂色 , 必定存在两列相同的涂色方案 ;
先将可能的涂色方案枚举出来 : 一共只可能存在
种可能的涂色方案 ;
在
列方格中 , 使用
种模式进行涂色 ;
可以等价理解为鸽巢原理的 : 将
个物体放到
个盒子中 , 则 至少有一个盒子中有
个 或
个以上的物体 ;
因此至少有
列或
列以上的格子会被涂成一种颜色 ;
证明 : 空间中有
个格点 , 所有的两点连线的中点 , 有一个格点 ;
格点指的是整数点 ;
连线中点是格点的要求 : 空间坐标
与
有相同的奇偶性 , 即
同为奇数或偶数 ,
同为奇数或偶数 ,
同为奇数或偶数 ,
此时这两个空间坐标的连线中点就是 格点 , 即整数点 ;
下面分析三个坐标分别奇偶性相同时 , 中点是格点的原因 :
连线中点坐标公式为 :
当奇偶性相同的时候 , 连线中点的空间坐标的三个数都是整数 ;
空间坐标
与
的奇偶模式有
种 ; 分别是
个坐标
奇偶相同 / 不同 , 两种情况 ;
个坐标
奇偶相同 / 不同 , 两种情况 ;
个坐标
奇偶相同 / 不同 , 两种情况 ;
上述每个坐标有两种情况 , 三个坐标下来就是
种情况 , 这是乘法原则 ;
空间中
个格点 , 每个格点的奇偶模式有
种 ;
可以等价理解为鸽巢原理的 : 将
个物体放到
个盒子中 , 则 至少有一个盒子中有
个 或
个以上的物体 ;
因此至少有
个或
个以上的格点的奇偶模式是相同的 ;
因此 :
个奇偶模式相同的格点连接的中点 , 肯定是格点 ;