HMMT November

Combinatorics Difficulty 5.0 AIME Find the answer

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

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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\}$ and $\{4,5,6,7,8,9\}$ . The next largest possible sum is 77 (the entire set except 1). If $k \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, \ldots, 12\}$ into equal subsets.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.