# Difference between revisions of "1996 USAMO Problems/Problem 2"

(Added solution) |
m (→Solution) |
||

Line 3: | Line 3: | ||

==Solution== | ==Solution== | ||

− | 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}</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>. |

− | '''We now show that we can divide <math>\mathcal{S}</math> into <math>|G|</math> (the cardinality of <math>G</math>) 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 <math>\frac{\max{\mathcal{S}}}{\min{\mathcal{S}}}< 2^{|G|}=2^{q-p}</math>. Note that <cmath>\max{\mathcal{S}}=\sum_{i=1}^{q-1}a_i</cmath> and <cmath>\min{\mathcal{S}}=a_p.</cmath> Taking note of that fact that <math>a_{p+1},a_{p+2},\dots,a_{q-1}</math> are not greedy numbers, we write: | + | '''We now show that we can divide <math>\mathcal{S}(G)</math> into <math>|G|</math> (the cardinality of <math>G</math>) 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 <math>\frac{\max{\mathcal{S}(G)}}{\min{\mathcal{S}(G)}}< 2^{|G|}=2^{q-p}</math>. Note that <cmath>\max{\mathcal{S}(G)}=\sum_{i=1}^{q-1}a_i</cmath> and <cmath>\min{\mathcal{S}(G)}=a_p.</cmath> Taking note of that fact that <math>a_{p+1},a_{p+2},\dots,a_{q-1}</math> are not greedy numbers, we write: |

<cmath> | <cmath> | ||

Line 21: | Line 21: | ||

</cmath> | </cmath> | ||

− | 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}</math> into 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}</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}=a_p</math> on the bottom and <math>2^{q-p}a_p>\max\mathcal{S}</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 in each group, there are as many classes as there are terms. | 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 in each group, there are as many classes as there are terms. |

## Revision as of 01:53, 30 July 2013

## 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

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 in each group, there are as many classes as there are terms.