Maths Olympiad Prep

Library / /87 of 397

Combinatorics Difficulty 5.2 AIME, harder Prove it Taiwan

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 n=2kn = 2^k, where kk is a positive integer. We will prove by mathematical induction that from any set containing 2n12n - 1 positive integers, one can always select nn integers such that the sum of these nn integers is divisible by nn. When k=10k = 10, this is exactly what the problem asks.

1. When k=1k=1, n=2n=2, 2n1=32n - 1 = 3. 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 n=2kn = 2^k. Consider n=2k+1n = 2^{k+1}. Since 2n1=2k+21>2k+112n - 1 = 2^{k+2} - 1 > 2^{k+1} - 1, by the induction hypothesis, there exist 2k2^k positive integers such that their sum is divisible by 2k2^k. Furthermore, 2k+212k=3×2k1>2k+112^{k+2} - 1 - 2^k = 3 \times 2^k - 1 > 2^{k+1} - 1, so by the induction hypothesis, there exist 2k2^k positive integers such that their sum is divisible by 2k2^k. Also, 3×2k12k=2k+113 \times 2^k - 1 - 2^k = 2^{k+1} - 1, so by the induction hypothesis, there exist 2k2^k positive integers such that their sum is divisible by 2k2^k. Denote the sums of these three groups of positive integers by 2ka,2kb,2kc2^k a, 2^k b, 2^k c respectively. Among these three numbers a,b,ca, b, c, at least two must have the same parity; without loss of generality, suppose a+b=2ma + b = 2m. Then these two groups of numbers together consist of 2k+2k=2k+12^k + 2^k = 2^{k+1} numbers, and their sum is
2ka+2kb=2k(a+b)=2k×2m=2k+1m, 2^k a + 2^k b = 2^k (a + b) = 2^k \times 2m = 2^{k+1}m,
which is divisible by 2k+12^{k+1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.