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 "2003 AIME I Problems/Problem 3"

m (→‎See also)
(→‎Solution)
 
(6 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Let the set <math> \mathcal{S} = \{8, 5, 1, 13, 34, 3, 21, 2\}. </math> Susan makes a list as follows: for each two-element subset of <math> \mathcal{S}, </math> she writes on her list the greater of the set's two elements. Find the sum of the numbers on the list.
+
Let the [[set]] <math> \mathcal{S} = \{8, 5, 1, 13, 34, 3, 21, 2\}. </math> Susan makes a list as follows: for each two-element subset of <math> \mathcal{S}, </math> she writes on her list the greater of the set's two elements. Find the sum of the numbers on the list.
  
 
== Solution ==
 
== Solution ==
 +
Order the numbers in the set from greatest to least to reduce error: <math>\{34, 21, 13, 8, 5, 3, 2, 1\}.</math>
 
Each [[element]] of the [[set]] will appear in <math>7</math> two-element [[subset]]s, once with each other number.
 
Each [[element]] of the [[set]] will appear in <math>7</math> two-element [[subset]]s, once with each other number.
  
−
<math>34</math> will be the greater number in <math>7</math> subsets.  
+
*<math>34</math> will be the greater number in <math>7</math> subsets.
 +
*<math>21</math> will be the greater number in <math>6</math> subsets.
 +
*<math>13</math> will be the greater number in <math>5</math> subsets.
 +
*<math>8</math> will be the greater number in <math>4</math> subsets.
 +
*<math>5</math> will be the greater number in <math>3</math> subsets.
 +
*<math>3</math> will be the greater number in <math>2</math> subsets.
 +
*<math>2</math> will be the greater number in <math>1</math> subsets.
 +
*<math>1</math> will be the greater number in <math>0</math> subsets.  
  
−
<math>21</math> will be the greater number in <math>6</math> subsets.  
+
Therefore the desired sum is <math>34\cdot7+21\cdot6+13\cdot5+8\cdot4+5\cdot3+3 \cdot2+2\cdot1+1\cdot0=\boxed{484}</math>.
  
−
<math>13</math> will be the greater number in <math>5</math> subsets.  
+
Note: Note that <math>7+6+5+4+3+2+1=\binom{8}{2}</math>, so we have counted all the possible cases.
  
−
<math>8</math> will be the greater number in <math>4</math> subsets.
+
~Yiyj1
  
−
<math>5</math> will be the greater number in <math>3</math> subsets.
+
== Solution ==
−
 
+
Thinking of this problem algorithmically, one can "sort" the array to give:
−
<math>3</math> will be the greater number in <math>2</math> subsets.
+
<cmath>{1, 2, 3, 5, 8, 13, 21, 34}</cmath>
  
−
<math>2</math> will be the greater number in <math>1</math> subsets.
+
Now, notice that when we consider different pairs, we are only going to fixate one element and look at the all of the next elements in the array, basically the whole <math>j = i + 1</math> shebang. Then, we see that if we set the sum of the whole array to <math>x,</math> we get out answer to be
  
−
<math>1</math> will be the greater number in <math>0</math> subsets.
+
<cmath>(x-1) + (x-3) + (x-6) + (x-11) + (x-19) + (x-32) + (x-53) = 7x - 125</cmath>
  
−
Therefore the desired sum is:
+
Finding <math>7x</math> isn't hard, and we see that it is equal to <math>609</math>:
  
−
<math> \displaystyle 34\cdot7+21\cdot6+13\cdot5+8\cdot4+5\cdot3+3 \cdot2+2\cdot1+1\cdot0=484</math>
+
<cmath>609 - 125 = \boxed{484}</cmath>
  
 
== See also ==
 
== See also ==
−
* [[2003 AIME I Problems]]
+
{{AIME box|year=2003|n=I|num-b=2|num-a=4}}
  
 
[[Category:Introductory Combinatorics Problems]]
 
[[Category:Introductory Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 23:09, 8 January 2024

Problem

Let the set $\mathcal{S} = \{8, 5, 1, 13, 34, 3, 21, 2\}.$ Susan makes a list as follows: for each two-element subset of $\mathcal{S},$ she writes on her list the greater of the set's two elements. Find the sum of the numbers on the list.

Solution

Order the numbers in the set from greatest to least to reduce error: $\{34, 21, 13, 8, 5, 3, 2, 1\}.$ Each element of the set will appear in $7$ two-element subsets, once with each other number.

  • $34$ will be the greater number in $7$ subsets.
  • $21$ will be the greater number in $6$ subsets.
  • $13$ will be the greater number in $5$ subsets.
  • $8$ will be the greater number in $4$ subsets.
  • $5$ will be the greater number in $3$ subsets.
  • $3$ will be the greater number in $2$ subsets.
  • $2$ will be the greater number in $1$ subsets.
  • $1$ will be the greater number in $0$ subsets.

Therefore the desired sum is $34\cdot7+21\cdot6+13\cdot5+8\cdot4+5\cdot3+3 \cdot2+2\cdot1+1\cdot0=\boxed{484}$.

Note: Note that $7+6+5+4+3+2+1=\binom{8}{2}$, so we have counted all the possible cases.

~Yiyj1

Solution

Thinking of this problem algorithmically, one can "sort" the array to give: \[{1, 2, 3, 5, 8, 13, 21, 34}\]

Now, notice that when we consider different pairs, we are only going to fixate one element and look at the all of the next elements in the array, basically the whole $j = i + 1$ shebang. Then, we see that if we set the sum of the whole array to $x,$ we get out answer to be

\[(x-1) + (x-3) + (x-6) + (x-11) + (x-19) + (x-32) + (x-53) = 7x - 125\]

Finding $7x$ isn't hard, and we see that it is equal to $609$:

\[609 - 125 = \boxed{484}\]

See also

2003 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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=2003_AIME_I_Problems/Problem_3&oldid=210310"