鸽巢原理应用于一道十分有意思的题目

在组合数学中学习鸽巢原理。其中一道例题是这样的&＃xff1a;

从1,2,3,4,..., 200这200个整数中选取101个整数&＃xff0c;则一定存在两个数存在整除关系&＃xff1f;

解答&＃xff1a;

一个数对其按照2进行因式分解&＃xff0c;总可写成n &＃61; 2 ^ k * t(其中k >&＃61;0, t为奇数)。例如2 &＃61; 2 ^ 1 * 1; 3 &＃61; 2 ^ 0 * 3...

而1到200存在奇数1,3,5,7,..., 199一共100个奇数。我选取101个整数&＃xff0c;则说明存在两个整数i,j, 它们经过分解&＃xff0c;t是相等的。所以前面的k是不一样的。也就证明了i&＃xff0c;j存在整除关系。很简单是吗&＃xff1f;请看下面一道扩展题。

从1,2,3,4,..., 200这200个整数中选取100个整数&＃xff0c;其中只有一个数小于16&＃xff0c;证明一定存在两个数存在整除关系&＃xff1f;

我们这样想&＃xff1a;

    定义两个集合A &＃61;  {a[1], a[2], ..., a[100]}

                           B &＃61; {1, 3, 5, 7, ..., 199}

其中A是从200个整数中选取的100个整数&＃xff0c;而B[i]则是某个a[j]经过按2分解最后的奇数t。

经过思考&＃xff0c;若选取的100个数不存在整除关系&＃xff0c;则每个数一定映射到不同的奇数。若两个数经分解后得到相同的奇数&＃xff0c;则这两个数能够整除。

我们再来分情况讨论&＃xff0c;

        对于最小数15&＃xff0c;

        它映射到集合B的元素是15。假设映射到集合B为45的元素为M&＃xff0c;则M和15是什么关系呢&＃xff1f;一定整除&＃xff0c;对不对?所以存在整除。

       对于13&＃xff0c; 39

                11&＃xff0c; 33

                 9&＃xff0c;  27

                 7&＃xff0c; 21

                5&＃xff0c; 15

               3&＃xff0c; 9

              1不用说&＃xff0c;肯定存在整除关系。

关键是对于1到15之间的偶数&＃xff0c;如何处理&＃xff1f;

       对于14&＃xff0c; 14 &＃61; 2 * 7&＃xff08;k &＃61; 1&＃xff09;。 映射到B中的元素为7。

       我们接着考虑B的为7的倍数的元素{21, 35, 49, 63, 77, 91, 105,..., 189}

      我们知道105后面的映射到A就是它们本身&＃xff0c;因为A中每个数都小于200.

     接着我们随便来考虑一组数值<35, 105>.105是35的倍数&＃xff0c;为了使它们两者对应到A中的元素不存在整除&＃xff0c;则A中的元素一定是2 ^ k * 35(k > 0)。而这是A中的元素一定是14

的整倍数。所以要么是14的倍数&＃xff0c;要么是105和35对应的数存在整数倍关系。

      对于10,10 &＃61; 2 * 5(k &＃61; 1)处理方式和14一样。

       对于6&＃xff0c;处理方式和14一样。

接着我们来考虑12,8,4,2.

     先来考虑2吧。

     若A中存在元素2&＃xff0c;若不存在整数关系&＃xff0c;其它199个数都是奇数。我们知道&＃xff0c;这些奇数中肯定存在整除关系。

    再来考虑12吧。

    对于12&＃xff0c;12 &＃61; 2 ^ 2 * 3(k &＃61; 2, t &＃61; 3)

    奇数为3.我们来考虑B中的 sub_B&＃61;&＃xff5b;9, 15, 21, 27, ...99, 105, 111, 117, ..., 195&＃xff5d;

    这些都是3的倍数。

   为了不和12产生整除关系设定sub_B 到A中元素的映射关系为 2 ^ k * sub_B[i](其中一定是小于等于1的)

我们知道105以后的k一定是0.我们来看tri_pair<9, 27, 117>117是27的倍数&＃xff0c;27是9的倍数。为了是它们映射到A中元素不能整除&＃xff0c;所以2 ^ 1 * 27, 2 ^ 2 ^ 9。

  这个时候我们发现&＃xff0c;2 ^ 2 * 9 已经是12的倍数了。要么9, 27, 117对应于A中的数之间存在整除关系&＃xff0c;要么其中有些数是12的倍数&＃xff0c;总之&＃xff0c;存在整除关系。

   来考虑8和4。

  对于4 &＃61; 2 ^ 2 * 1(k &＃61; 2, t &＃61; 1)

  正如在对于12讨论的那样&＃xff0c;一定存在4的倍数。

   对于8 &＃61; 2 ^ 3 * 1&＃xff08;t &＃61; 1&＃xff09;对于3次方如何考虑呢&＃xff1f;

   还是按照原来的思路。

  我们取sub_B &＃61; {3, 9, 15, 21, ..., }

这样对于<3, 21, 63, 189>后面的在这里就不写了。

到现在&＃xff0c;我们已经将1,2,3,4,5,..., 15全部讨论完了。对于每个数都存在整除关系。