Maths Olympiad Prep

Library / /16 of 28

Number theory Difficulty 5.7 AIME, harder Prove it JBMO

Problem:
A set SS of natural numbers is called good, if for each element xSx \in S, xx does not divide the sum of the remaining numbers in SS. Find the maximal possible number of elements of a good set which is a subset of the set A={1,2,3,,63}A=\{1,2,3, \ldots, 63\}.

Solution

Solution:
Let set BB be the good subset of AA which has the maximum number of elements. We can easily see that the number 11 does not belong to BB since 11 divides all natural numbers. Based on the property of divisibility, we know that xx divides the sum of the remaining numbers if and only if xx divides the sum of all numbers in the set BB. If BB has exactly 6262 elements, then B={2,3,4,,63}B=\{2,3,4, \ldots, 63\}, but this set can't be good since the sum of its elements is 20152015 which is divisible by 55. Therefore BB has at most 6161 elements. Now we are looking for the set whose elements do not divide their sum, so the best way to do that is making the sum of elements be a prime number. 2+3+4++63=20152+3+4+\ldots+63=2015 and if we remove the number 44, we will obtain the prime number 20112011. Hence the set B={2,3,5,6,7,,63}B=\{2,3,5,6,7, \ldots, 63\} is a good one. We conclude that our number is 6161.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.