题目
证明在任意给出的n+2个正整数中必有两个数,它们的差或它们的和能被2n整除
证明在任意给出的n+2个正整数中必有两个数,它们的差或它们的和能被2n整除
题目解答
答案
被2n除余0(整除)的为第1类
被2n除余1的为第2类
被2n除余2的为第3类
被2n除余3的为第4类
.
被2n除余2n-1的为第2n-1类
任意一类中的两个数之差可以被2n整除
而分别来自第k类和第n-k类(称为互补类)中的两个数之和可以被2n整除
如果n+2个正整数没有两个来自于同一类必然有两个数来自于互补类
得证
解析
步骤 1:定义余数类
将正整数按照被2n除的余数进行分类。具体来说,对于任意正整数a,存在唯一的整数q和r,使得a = 2nq + r,其中0 ≤ r < 2n。因此,我们可以将正整数分为2n类,每类对应一个余数r,即第r类。
步骤 2:确定互补类
对于第k类(0 ≤ k < 2n),其互补类为第(2n-k)类。如果两个数分别属于第k类和第(2n-k)类,则它们的和可以被2n整除。例如,如果一个数属于第1类,另一个数属于第(2n-1)类,则它们的和可以被2n整除。
步骤 3:应用鸽巢原理
根据鸽巢原理,如果有n+2个正整数,而只有2n个余数类,那么至少有两个数属于同一类或属于互补类。如果两个数属于同一类,则它们的差可以被2n整除;如果两个数属于互补类,则它们的和可以被2n整除。
将正整数按照被2n除的余数进行分类。具体来说,对于任意正整数a,存在唯一的整数q和r,使得a = 2nq + r,其中0 ≤ r < 2n。因此,我们可以将正整数分为2n类,每类对应一个余数r,即第r类。
步骤 2:确定互补类
对于第k类(0 ≤ k < 2n),其互补类为第(2n-k)类。如果两个数分别属于第k类和第(2n-k)类,则它们的和可以被2n整除。例如,如果一个数属于第1类,另一个数属于第(2n-1)类,则它们的和可以被2n整除。
步骤 3:应用鸽巢原理
根据鸽巢原理,如果有n+2个正整数,而只有2n个余数类,那么至少有两个数属于同一类或属于互补类。如果两个数属于同一类,则它们的差可以被2n整除;如果两个数属于互补类,则它们的和可以被2n整除。