Maths Olympiad Prep

Library / /232 of 348

Combinatorics Difficulty 5.0 AIME Find the answer

Let SS be a subset of {1,2,3,,12}\{1,2,3, \ldots, 12\} such that it is impossible to partition SS into kk disjoint subsets, each of whose elements sum to the same value, for any integer k2k \geq 2. Find the maximum possible sum of the elements of SS.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We note that the maximum possible sum is 78 (the entire set). However, this could be partitioned into 2 subsets with sum 39: {1,2,3,10,11,12}\{1,2,3,10,11,12\} and {4,5,6,7,8,9}\{4,5,6,7,8,9\}. The next largest possible sum is 77 (the entire set except 1). If k2k \geq 2 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 {2,,12}\{2, \ldots, 12\} 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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.