16th Chinese 2001 Problem A2 Let X be the set {1, 2, 3, ... , 2001}. Find the smallest n so that given any subset of X with n elements we can always find an element which is a power of 2 or two elements whose sum is a power of 2. Solution
: 999. Suppose A is a subset of X which does not contain any power of 2 or any two elements whose sum is a power of 2. Then A cannot contain any of the 11 powers of 2 in X: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Also it must exclude at least one element of the following 992 pairs: 17 pairs (47, 2001), (48, 2000), ... , (63, 1985) 63 pairs (65, 1983), (66, 1982), ... , (127, 1921) 127 pairs (129, 1919), (130, 1918), ... , (255, 1793) 255 pairs (257, 1791), (258, 1790), ... , (511, 1537) 511 pairs (513, 1535), (514, 1534), ... , (1023, 1025) all with sum 2048 14 pairs (31, 33), (30, 34), ... , (18, 46) with sum 64 1 pair (15, 17) with sum 32 4 pairs (7, 9), (6, 10), (5, 11), (3, 13) with sum 16 So A can contain at most 2001 - 11 - 993 = 998 elements. On the other hand, the following set has 998 elements: 977 elements: 1025, 1026, ... , 2001 14 elements: 33, 34, ... , 46 7 elements: 9, 10, 11, 12, 13, 14, 17 It obviously contains no powers of 2. The sum of any two elements in the first row is between 2.1025 = 2050 and 2.2001 = 4002 and hence strictly between 2048 and 4096 which are consecutive powers of 2, so it is not a power of 2. The sum of an element in the first row and an element in the second or third row is at most 2047 (but more than 1024) so it is not a power of 2. The sum of two elements in the second row is between 66 and 92, so not a power of 2. The sum of an element in the second row and an element in the third row is between 9 + 33 = 42 and 17 + 46 = 63, so not a power of 2. Finally, the sum of two distinct elements in the third row is between 9 + 10 = 19 and 14 + 17 = 31, so is not a power of 2. Thus any set with 999 elements must have a power of 2 or two elements summing to a power of 2. On the other hand there is a set with 998 elements which does not have such elements. 16th Chinese 2001 © John Scholes jscholes@kalva.demon.co.uk 5 June 2002