Prove that from any set containing 2047 positive integers, one can always select 1024 positive integers such that the sum of these 1024 positive integers is divisible by 1024.
Solution
Suppose , where is a positive integer. We will prove by mathematical induction that from any set containing positive integers, one can always select integers such that the sum of these integers is divisible by . When , this is exactly what the problem asks.
1. When , , . Among any three positive integers, there must be two numbers with the same parity, and their sum is divisible by 2.
2. Suppose the statement holds when . Consider . Since , by the induction hypothesis, there exist positive integers such that their sum is divisible by . Furthermore, , so by the induction hypothesis, there exist positive integers such that their sum is divisible by . Also, , so by the induction hypothesis, there exist positive integers such that their sum is divisible by . Denote the sums of these three groups of positive integers by respectively. Among these three numbers , at least two must have the same parity; without loss of generality, suppose . Then these two groups of numbers together consist of numbers, and their sum is
which is divisible by .