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


Solution

Let set $B$ be the good subset of $A$ which have the maximum number of elements. We can easily see that the number 1 does not belong to $B$ since 1 divides all natural numbers. Based on the property of divisibility, we know that $x$ divides the sum of the remaining numbers if and only if $x$ divides the sum of all numbers in the set $B$. If $B$ has exactly 62 elements, than $B=\{2,3,4, \ldots, 62\}$, but this set can't be good since the sum of its elements is 2015 which is divisible by 5 . Therefore $B$ has at most 61 elements. Now we are looking for the set, whose elements does not divide their sum, so the best way to do that is making a sum of elements be a prime number. $2+3+4+\ldots+63=2015$ and if we remove the number 4, we will obtain the prime number 2011. Hence the set $B=\{2,3,5,6,7, \ldots, 63\}$ is a good one. We conclude that our number is 61 .
