Let be a subset of such that it is impossible to partition into disjoint subsets, each of whose elements sum to the same value, for any integer . Find the maximum possible sum of the elements of .
Solution
We note that the maximum possible sum is 78 (the entire set). However, this could be partitioned into 2 subsets with sum 39: and . The next largest possible sum is 77 (the entire set except 1). If subsets each had equal sum, then they would have to be 7 subsets with sum 11 each or 11 subsets with sum 7 each. However, the subset containing 12 will have sum greater than 11; hence there is no way to partition the subset into equal subsets.
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.