HMMT 十一月 2013 · 冲刺赛 · 第 22 题

HMMT November 2013 — Guts Round — Problem 22

[ 12 ] Let S be a subset of { 1 , 2 , 3 , . . . , 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 ≥ 2. Find the maximum possible sum of the elements of S .

解析

[ 12 ] Let S be a subset of { 1 , 2 , 3 , . . . , 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 ≥ 2. Find the maximum possible sum of the elements of S . Answer: 77 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 ≥ 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 } into equal subsets.