Difference between revisions of "1996 USAMO Problems/Problem 2"
m (→Solution) |
Kevinmathz (talk | contribs) |
||
(3 intermediate revisions by 2 users not shown) | |||
Line 2: | Line 2: | ||
For any nonempty set <math>S</math> of real numbers, let <math>\sigma(S)</math> denote the sum of the elements of <math>S</math>. Given a set <math>A</math> of <math>n</math> positive integers, consider the collection of all distinct sums <math>\sigma(S)</math> as <math>S</math> ranges over the nonempty subsets of <math>A</math>. Prove that this collection of sums can be partitioned into <math>n</math> classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2. | For any nonempty set <math>S</math> of real numbers, let <math>\sigma(S)</math> denote the sum of the elements of <math>S</math>. Given a set <math>A</math> of <math>n</math> positive integers, consider the collection of all distinct sums <math>\sigma(S)</math> as <math>S</math> ranges over the nonempty subsets of <math>A</math>. Prove that this collection of sums can be partitioned into <math>n</math> classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2. | ||
− | ==Solution== | + | ==Solution 1== |
Let set <math>A</math> consist of the integers <math>a_1\le a_2\le a_3\le\dots\le a_n</math>. For <math>k\ge 2</math>, call <math>a_k</math> greedy if <math>\sum_{i=1}^{k-1}a_i < a_k</math>. Also call <math>a_1</math> greedy. Now put all elements of <math>A</math> into groups of consecutive terms in such a way that each group <math>G</math> begins with a greedy term, call it <math>a_p</math>, and ends on the term <math>a_{q-1}</math> just before the next greedy term after <math>a_p</math>. (If <math>a_p</math> is the last greedy term, let <math>q-1=n</math>.) We introduce some more terminology. A sum <math>\sigma(S)</math> is said to "belong to" a group <math>G</math> if <math>\max(S)\in G</math>. Denote by <math>\mathcal{S}(G)</math> the set of all sums belonging to <math>G</math>. | Let set <math>A</math> consist of the integers <math>a_1\le a_2\le a_3\le\dots\le a_n</math>. For <math>k\ge 2</math>, call <math>a_k</math> greedy if <math>\sum_{i=1}^{k-1}a_i < a_k</math>. Also call <math>a_1</math> greedy. Now put all elements of <math>A</math> into groups of consecutive terms in such a way that each group <math>G</math> begins with a greedy term, call it <math>a_p</math>, and ends on the term <math>a_{q-1}</math> just before the next greedy term after <math>a_p</math>. (If <math>a_p</math> is the last greedy term, let <math>q-1=n</math>.) We introduce some more terminology. A sum <math>\sigma(S)</math> is said to "belong to" a group <math>G</math> if <math>\max(S)\in G</math>. Denote by <math>\mathcal{S}(G)</math> the set of all sums belonging to <math>G</math>. | ||
Line 23: | Line 23: | ||
where the inequalities after the ellipses result from the fact that <math>a_p</math> is a greedy number (which implies by definition that <math>\sum_{i=1}^{p-1}a_i<a_p</math>). This proves the desired inequality. Now we can prove the result in bold above. Divide <math>\mathcal{S}(G)</math> into <math>|G|=q-p</math> classes by taking those terms in <math>[a_p,2a_p)</math> and placing them in the first class, taking those terms in <math>[2a_p,2^2a_p)</math> and placing them in another, and so on, until we reach <math>[2^{q-p-1}a_p,2^{q-p}a_p)</math>. The inequality we proved above shows that all of the sums in <math>\mathcal{S}(G)</math> will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by <math>\min\mathcal{S}(G)=a_p</math> on the bottom and <math>2^{q-p}a_p>\max\mathcal{S}(G)</math> on the top. This proves the result in bold. | where the inequalities after the ellipses result from the fact that <math>a_p</math> is a greedy number (which implies by definition that <math>\sum_{i=1}^{p-1}a_i<a_p</math>). This proves the desired inequality. Now we can prove the result in bold above. Divide <math>\mathcal{S}(G)</math> into <math>|G|=q-p</math> classes by taking those terms in <math>[a_p,2a_p)</math> and placing them in the first class, taking those terms in <math>[2a_p,2^2a_p)</math> and placing them in another, and so on, until we reach <math>[2^{q-p-1}a_p,2^{q-p}a_p)</math>. The inequality we proved above shows that all of the sums in <math>\mathcal{S}(G)</math> will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by <math>\min\mathcal{S}(G)=a_p</math> on the bottom and <math>2^{q-p}a_p>\max\mathcal{S}(G)</math> on the top. This proves the result in bold. | ||
− | However, that clearly implies the desired conclusion, as every sum belongs to a group, and every sum belonging to a group is a member of a class. Moreover, there will be precisely <math>n</math> classes, because every term <math>a_i</math> belongs to a group and | + | However, that clearly implies the desired conclusion, as every sum belongs to a group, and every sum belonging to a group is a member of a class. Moreover, there will be precisely <math>n</math> classes, because every term <math>a_i</math> belongs to a group and for each group <math>G</math>, there are as many classes for <math>\mathcal{S}(G)</math> as there are terms in <math>G</math>. |
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We proceed to solve this problem by induction. Our base case is when <math>A</math> has 1 integer - there is 1 class: itself. | ||
+ | |||
+ | Let <math>A</math> now have <math>n</math> elements, and assume it works for this case. We add <math>k</math>, another element, to the set. WLOG, let <math>k</math> be the maximum element. Note that <math>\sigma(A)</math> has to be the maximum element of a class. | ||
+ | |||
+ | We always get a new class that works: <math>\sigma(A+\{k\})</math> being the maximum element. This way all elements including <math>k</math> will be in that class if <math>k>\sigma(A)</math>. When <math>k<\sigma(A)</math> it also works since <math>k</math> must be the maximum element from our WLOG condition above, so our induction step is done. | ||
+ | |||
+ | == See Also == | ||
+ | {{USAMO newbox|year=1996|num-b=1|num-a=3}} | ||
+ | {{MAA Notice}} | ||
+ | [[Category:Olympiad Combinatorics Problems]] |
Latest revision as of 10:40, 29 September 2019
Contents
Problem
For any nonempty set of real numbers, let denote the sum of the elements of . Given a set of positive integers, consider the collection of all distinct sums as ranges over the nonempty subsets of . Prove that this collection of sums can be partitioned into classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.
Solution 1
Let set consist of the integers . For , call greedy if . Also call greedy. Now put all elements of into groups of consecutive terms in such a way that each group begins with a greedy term, call it , and ends on the term just before the next greedy term after . (If is the last greedy term, let .) We introduce some more terminology. A sum is said to "belong to" a group if . Denote by the set of all sums belonging to .
We now show that we can divide into (the cardinality of ) classes in such a way that the maximum and minimum sum belonging to each class differ by no more than a factor of 2. Using the previous notation, we first prove that . Note that and Taking note of that fact that are not greedy numbers, we write:
where the inequalities after the ellipses result from the fact that is a greedy number (which implies by definition that ). This proves the desired inequality. Now we can prove the result in bold above. Divide into classes by taking those terms in and placing them in the first class, taking those terms in and placing them in another, and so on, until we reach . The inequality we proved above shows that all of the sums in will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by on the bottom and on the top. This proves the result in bold.
However, that clearly implies the desired conclusion, as every sum belongs to a group, and every sum belonging to a group is a member of a class. Moreover, there will be precisely classes, because every term belongs to a group and for each group , there are as many classes for as there are terms in .
Solution 2
We proceed to solve this problem by induction. Our base case is when has 1 integer - there is 1 class: itself.
Let now have elements, and assume it works for this case. We add , another element, to the set. WLOG, let be the maximum element. Note that has to be the maximum element of a class.
We always get a new class that works: being the maximum element. This way all elements including will be in that class if . When it also works since must be the maximum element from our WLOG condition above, so our induction step is done.
See Also
1996 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.