Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Added solution)
 
 
(4 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}</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 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

Problem

For any nonempty set $S$ of real numbers, let $\sigma(S)$ denote the sum of the elements of $S$. Given a set $A$ of $n$ positive integers, consider the collection of all distinct sums $\sigma(S)$ as $S$ ranges over the nonempty subsets of $A$. Prove that this collection of sums can be partitioned into $n$ classes so that in each class, the ratio of the largest sum to the smallest sum does not exceed 2.

Solution 1

Let set $A$ consist of the integers $a_1\le a_2\le a_3\le\dots\le a_n$. For $k\ge 2$, call $a_k$ greedy if $\sum_{i=1}^{k-1}a_i < a_k$. Also call $a_1$ greedy. Now put all elements of $A$ into groups of consecutive terms in such a way that each group $G$ begins with a greedy term, call it $a_p$, and ends on the term $a_{q-1}$ just before the next greedy term after $a_p$. (If $a_p$ is the last greedy term, let $q-1=n$.) We introduce some more terminology. A sum $\sigma(S)$ is said to "belong to" a group $G$ if $\max(S)\in G$. Denote by $\mathcal{S}(G)$ the set of all sums belonging to $G$.

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

\begin{align*} \max{\mathcal{S}}&=\sum_{i=1}^{q-1}a_i \\ &=a_{q-1}+\sum_{i=1}^{q-2}a_i \\ &\le 2\sum_{i=1}^{q-2}a_i\\ &\le 2^2\sum_{i=1}^{q-3}a_i\\ &\vdots\\ &\le 2^{q-p-1}\sum_{i=1}^{p}a_i\\ &= 2^{q-p-1}(\sum_{i=1}^{p-1}a_i + a_p)\\ &<2^{q-p-1}(2a_p)\\ &=2^{q-p}\min\mathcal{S} \end{align*}

where the inequalities after the ellipses result from the fact that $a_p$ is a greedy number (which implies by definition that $\sum_{i=1}^{p-1}a_i<a_p$). This proves the desired inequality. Now we can prove the result in bold above. Divide $\mathcal{S}(G)$ into $|G|=q-p$ classes by taking those terms in $[a_p,2a_p)$ and placing them in the first class, taking those terms in $[2a_p,2^2a_p)$ and placing them in another, and so on, until we reach $[2^{q-p-1}a_p,2^{q-p}a_p)$. The inequality we proved above shows that all of the sums in $\mathcal{S}(G)$ will fall in one of these classes, as the intervals into which the classes fall form a continuous range bounded by $\min\mathcal{S}(G)=a_p$ on the bottom and $2^{q-p}a_p>\max\mathcal{S}(G)$ 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 $n$ classes, because every term $a_i$ belongs to a group and for each group $G$, there are as many classes for $\mathcal{S}(G)$ as there are terms in $G$.

Solution 2

We proceed to solve this problem by induction. Our base case is when $A$ has 1 integer - there is 1 class: itself.

Let $A$ now have $n$ elements, and assume it works for this case. We add $k$, another element, to the set. WLOG, let $k$ be the maximum element. Note that $\sigma(A)$ has to be the maximum element of a class.

We always get a new class that works: $\sigma(A+\{k\})$ being the maximum element. This way all elements including $k$ will be in that class if $k>\sigma(A)$. When $k<\sigma(A)$ it also works since $k$ 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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1996_USAMO_Problems/Problem_2&oldid=110051"