从1、2、3.、100中任选51个数,说明在选出的数中,至少有两个数,其中的一个数是另一个的倍数(抽屉原理)
问题描述:
从1、2、3.、100中任选51个数,说明在选出的数中,
至少有两个数,其中的一个数是另一个的倍数(抽屉原理)
答
一般我们构造抽屉的个数是比元素的个数少一 于是我们构造50个抽屉
我们可以按照2的幂来分类整数 并且可以把整数分光
我们构造
{1*2^0 1*2^1 1*2^2.}
{3*2^0 3*2^1 3*2^2...}
{5*2^0 5*2^1 5*2^2...}
{7*2^0 7*2^1 7*2^2...}
.
{49*2^0 49*2^1}
{51}
{53}
...
{97}
{99}
这里有50个抽屉 任意放入51个数至少2个数落在同一个抽屉 其中一个数另一个数的倍数