三题组合数学（有关鸽笼原理)(1)A是{1,2,3,...,2n}是任意n+1个数,试证A中至少存在一对a,b.使得a|b(2)A是{1,2,3,...,2n}是任意n+1个数,试证A中至少存在一对a,b.使得a与b互素(3)n是大于等于3的奇数,则下列

Question

三题组合数学（有关鸽笼原理)
(1)A是{1,2,3,...,2n}是任意n+1个数,试证A中至少存在一对a,b.使得
a|b
(2)A是{1,2,3,...,2n}是任意n+1个数,试证A中至少存在一对a,b.使得
a与b互素
(3)n是大于等于3的奇数,则下列数的集合：
{2-1,2^2-1,...,2^(n-1)-1}
是存在一数b使得
n|b;

Answer 1

1.n+1到2n,分成n个抽屉
对于1到n中的k,存在某个最小的i,使得k*2^i>n,那么k将分到k*2^i的抽屉里
一个抽屉中的数都是由某个最小的k,以及其2的幂的倍数组成,
所以在里面任意取两个,大数都能被小数整除
取n+1个数时,总有一个抽屉取了两个,所以结论成立
2.n个抽屉为(1,2),(3,4),...,(2n-1,2n),
总有一个抽屉取了两个,所以这两个数互质
3.2和n的最大公约数为1
2^0,2^1,...2^(n-1)这n个数里面,mod n的余数只能是1到n-1
所以存在0