Question

【题目】设均为大于1的整数.证明：存在个不被整除的整数，若将它们任意分成两组，则总有一组有若干个数的和被整除.

Answer 1

【答案】见解析

【解析】

先考虑为2的幂的情形.

设.则.取3个及个1，显然，这些数均不被整除.将这个数任意分成两组，则总有一组中含2个，其和为且被整除.

设不是2的幂，取个数为.

因为不是2的幂，所以，上述个数均不被整除.

若可将这些数分成两组，使得每一组中任意若干个数的和均不被整除.不妨设1在第一组，由被整除，故两个必须在第二组；又被整除，故2在第一组，进而，推出在第二组.

现归纳假设均在第一组，而均在第二组.

由被整除，故在第一组，从而，在第二组.

故由数学归纳法，知在第一组，在第二组.

最后，由于被整除，故在第一组.因此，均在第一组.由正整数的二进制表示，知每一个不超过的正整数均可表示为中若干个数的和，特别地，因为，所以，第一组中有若干个数的和为，当然被整除，矛盾.

因此，将前述个整数任意分成两组，总有一组中有若干个数之和被整除.