1986 AIME 第 12 题

先试着解答 1986 AIME 第 12 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 1986 AIME 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

12.

定义一组数的和为其中所有元素之和。设 SS 是一个正整数集合,其中每个数都不大于 1515。假设 SS 中任意两个不相交的子集都没有相同的和。具有这些性质的集合 SS 的最大可能元素和是多少?

Let the sum of a set of numbers be the sum of its elements. Let SS be a set of positive integers, none greater than 15.15. Suppose no two disjoint subsets of SS have the same sum. What is the largest sum a set SS with these properties can have?

答案:61
知识点:极端原理平均数子集
难度评级:3270
小提示:

SS 有六个元素,将其 6464 个子集和的方差与 6464 个连续整数的方差比较

If SS had six elements, compare the variance of its 6464 subset sums with that of 6464 consecutive integers

大提示:

限定 SS 的大小后,检查元素和超过候选值的五元子集

After bounding the size of S,S, inspect the five-element subsets whose sums exceed the candidate

解答:

首先,SS 至多有五个元素。若它有六个元素 s1,,s6s_1,\ldots,s_6,则其 6464 个子集和必须全都不同:如果两个子集和相等,消去它们的公共元素后,就会违反题设条件。

等概率随机选取一个子集,并令 XX 为其元素和。则 Var(X)=14i=16si214(102+112++152)=9554 \begin{gathered} \operatorname{Var}(X) =\frac14\sum_{i=1}^6s_i^2\\ {}\leq\frac14(10^2+11^2+\cdots+15^2)\\ {}=\frac{955}{4} \end{gathered}\text{。}另一方面,XX 等概率取 6464 个不同的整数。6464 个不同整数在它们连续时方差最小,该方差为 642112=13654 \frac{64^2-1}{12}=\frac{1365}{4}\text{,}矛盾。

至多含四个元素的集合,其元素和至多为 12+13+14+15=5412+13+14+15=54{1,,15}\{1,\ldots,15\} 中元素和至少为 6262 的五元子集只有七个。以下相等的和说明它们都不符合条件:

{8,12,13,14,15}\{8,12,13,14,15\}13+14=12+1513+14=12+15{9,11,13,14,15}\{9,11,13,14,15\}11+13=9+1511+13=9+15{9,12,13,14,15}\{9,12,13,14,15\}13+14=12+1513+14=12+15

{10,11,12,14,15}\{10,11,12,14,15\}11+14=10+1511+14=10+15{10,11,13,14,15}\{10,11,13,14,15\}11+13=10+1411+13=10+14

{10,12,13,14,15}\{10,12,13,14,15\}12+13=10+1512+13=10+15{11,12,13,14,15}\{11,12,13,14,15\}12+13=11+1412+13=11+14

因此答案至多为 6161

集合 {8,11,13,14,15}\{8,11,13,14,15\} 可达到 6161。它的 3232 个子集和依次为 0,8,11,13,14,15,19,21,22,23,24,25,26,27,28,29,32,33,34,35,36,37,38,39,40,42,46,47,48,50,53,61 \begin{gathered} 0,8,11,13,14,15,19,21,\\ 22,23,24,25,26,27,28,29,\\ 32,33,34,35,36,37,38,39,\\ 40,42,46,47,48,50,53,61 \end{gathered}\text{,}且全都不同。如果任意两个子集的和相等,删除它们的交集后,就会得到两个不相交且和相等的子集,因此这验证了所需性质。

First, SS has at most five elements. If it had six elements s1,,s6,s_1,\ldots,s_6, then its 6464 subset sums would all be distinct: equality between two subset sums, after cancelling their common elements, would violate the given condition.

Choose a subset uniformly at random and let XX be its sum. Then Var(X)=14i=16si214(102+112++152)=9554. \begin{gathered} \operatorname{Var}(X) =\frac14\sum_{i=1}^6s_i^2\\ {}\leq\frac14(10^2+11^2+\cdots+15^2)\\ {}=\frac{955}{4}. \end{gathered} On the other hand, XX is uniform on 6464 distinct integers. The least possible variance for 6464 distinct integers occurs when they are consecutive, and is 642112=13654, \frac{64^2-1}{12}=\frac{1365}{4}, a contradiction.

A set with at most four elements has sum at most 12+13+14+15=54.12+13+14+15=54. There are only seven five-element subsets of {1,,15}\{1,\ldots,15\} whose sums are at least 62.62. Each fails, as witnessed by the following equal sums:

{8,12,13,14,15}:\{8,12,13,14,15\}: 13+14=12+15.13+14=12+15. {9,11,13,14,15}:\{9,11,13,14,15\}: 11+13=9+15.11+13=9+15. {9,12,13,14,15}:\{9,12,13,14,15\}: 13+14=12+15.13+14=12+15.

{10,11,12,14,15}:\{10,11,12,14,15\}: 11+14=10+15.11+14=10+15. {10,11,13,14,15}:\{10,11,13,14,15\}: 11+13=10+14.11+13=10+14.

{10,12,13,14,15}:\{10,12,13,14,15\}: 12+13=10+15.12+13=10+15. {11,12,13,14,15}:\{11,12,13,14,15\}: 12+13=11+14.12+13=11+14.

Thus the answer is at most 61.61.

The set {8,11,13,14,15}\{8,11,13,14,15\} attains 61.61. Its 3232 subset sums, in order, are 0,8,11,13,14,15,19,21,22,23,24,25,26,27,28,29,32,33,34,35,36,37,38,39,40,42,46,47,48,50,53,61, \begin{gathered} 0,8,11,13,14,15,19,21,\\ 22,23,24,25,26,27,28,29,\\ 32,33,34,35,36,37,38,39,\\ 40,42,46,47,48,50,53,61, \end{gathered} all distinct. Equal sums from arbitrary subsets would, after deleting their intersection, give equal sums from disjoint subsets, so this verifies the required property.

← 第 11 题#11
完整试卷

其他年份的第 12 题