Question

【題目】設均為大于1的整數.證明：存在個不被整除的整數，若將它們任意分成兩組，則總有一組有若干個數的和被整除.

Answer 1

【答案】見解析

【解析】

先考慮為2的冪的情形.

設.則.取3個及個1，顯然，這些數均不被整除.將這個數任意分成兩組，則總有一組中含2個，其和為且被整除.

設不是2的冪，取個數為.

因為不是2的冪，所以，上述個數均不被整除.

若可將這些數分成兩組，使得每一組中任意若干個數的和均不被整除.不妨設1在第一組，由被整除，故兩個必須在第二組；又被整除，故2在第一組，進而，推出在第二組.

現歸納假設均在第一組，而均在第二組.

由被整除，故在第一組，從而，在第二組.

故由數學歸納法，知在第一組，在第二組.

最后，由于被整除，故在第一組.因此，均在第一組.由正整數的二進制表示，知每一個不超過的正整數均可表示為中若干個數的和，特別地，因為，所以，第一組中有若干個數的和為，當然被整除，矛盾.

因此，將前述個整數任意分成兩組，總有一組中有若干個數之和被整除.