当前位置 :
三题组合数学(有关鸽笼原理)(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的奇数,则下列
1人问答
更新时间:2024-05-02 09:13:03
问题描述:

三题组合数学(有关鸽笼原理)

(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;

丁惠敏回答:
  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个数里面,modn的余数只能是1到n-1   所以存在0
数学推荐
最新更新
热门数学
PC端 | 移动端 | mip端
问答网(wenda2.com)汇总了汉语字典,新华字典,成语字典,组词,词语,在线查字典,中文字典,英汉字典,在线字典,康熙字典等等,是学生查询学习资料的好帮手,是老师教学的好助手。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。

邮箱:联系方式:

Copyright©2009-2021 问答网 wenda2.com 版权所有 闽ICP备2022000227号-1