作业帮 > 数学 > 作业

有k+2个整数,证明所有数里有2个数的和或差可以被2k整除

来源:学生作业帮 编辑:拍题作业网作业帮 分类:数学作业 时间:2024/05/21 17:38:45
有k+2个整数,证明所有数里有2个数的和或差可以被2k整除
证明:
∵一个整数被2k除的余数有以下2k-1种可能
0,1,2,3,...,2k-1
将它们按照余数分成k+1组
{0},{1,2k-1},{2,2k-2},...,{k-1,k+1},{k}
∴根据抽屉原理,k+2个整数中,至少有2个数在上述k+1组中的同一组,不妨设为{n,2k-n}
(1) 若这2个数被2k除的余数同为n或同为2k-n
则这2个数的差可以被2k整除
(2) 若这2个数被2k除的余数分别为n和2k-n
则这2个数的和可以被2k整除
综上可知k+2个整数里至少有2个数的和或差可以被2k整除
证毕