Difference between revisions of "2009 AIME I Problems/Problem 14"

(New page: == Problem == For <math>t = 1, 2, 3, 4</math>, define <math>S_t = \sum_{i = 1}^{350}a_i^t</math>, where <math>a_i \in \{1,2,3,4\}</math>. If <math>S_1 = 513</math> and <math>S_4 = 4745</ma...)
 
(Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
Because the order of the <math>a</math>s doesn't matter, we simply need to find the number of <math>1</math>s <math>2</math>s <math>3</math>s and <math>4</math>s that minimize <math>S_2</math>. So let <math>w, x, y,</math> and <math>z</math> represent the number of <math>1</math>s, <math>2</math>s, <math>3</math>s, and <math>4</math>s respectively. Then we can write three equations based on these variables. Since there are a total of <math>350 a</math>s, we know that <math>w + x + y + z = 350</math>. We also know that <math>w + 2x + 3y + 4z = 513</math> and <math>w + 16x + 81y + 256z = 4745</math>.
+
Because the order of the <math>a</math>s doesn't matter, we simply need to find the number of <math>1</math>s <math>2</math>s <math>3</math>s and <math>4</math>s that minimize <math>S_2</math>. So let <math>w, x, y,</math> and <math>z</math> represent the number of <math>1</math>s, <math>2</math>s, <math>3</math>s, and <math>4</math>s respectively. Then we can write three equations based on these variables. Since there are a total of <math>350</math> <math>a</math>s, we know that <math>w + x + y + z = 350</math>. We also know that <math>w + 2x + 3y + 4z = 513</math> and <math>w + 16x + 81y + 256z = 4745</math>. We can now solve these down to two variables:
 +
<cmath>w = 350 - x - y - z</cmath>
 +
Substituting this into the second and third equations, we get
 +
<cmath>x + 2y + 3z = 163</cmath>
 +
and
 +
<cmath>15x + 80y + 255z = 4395.</cmath>
 +
The second of these can be reduced to
 +
<cmath>3x + 16y + 51z = 879.</cmath>
 +
Now we substitute <math>x</math> from the first new equation into the other new equation.
 +
<cmath>x = 163 - 2y - 3z</cmath>
 +
<cmath>3(163 - 2y - 3z) + 16y + 51z = 879</cmath>
 +
<cmath>489 + 10y + 42z = 879</cmath>
 +
<cmath>5y + 21z = 195</cmath>
 +
Since <math>y</math> and <math>z</math> are integers, the two solutions to this are <math>(y,z) = (39,0)</math> or <math>(18,5)</math>.
 +
If you plug both these solutions in to <math>S_2</math> it is apparent that the second one returns a smaller value. It turns out that <math>w = 215</math>, <math>x = 112</math>, <math>y = 18</math>, and <math>z = 5</math>, so <math>S_2 = 215 + 4*112 + 9*18 + 16*5 = 215 + 448 + 162 + 80 = \boxed{905}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2009|n=I|num-b=13|num-a=15}}
 
{{AIME box|year=2009|n=I|num-b=13|num-a=15}}

Revision as of 15:38, 20 March 2009

Problem

For $t = 1, 2, 3, 4$, define $S_t = \sum_{i = 1}^{350}a_i^t$, where $a_i \in \{1,2,3,4\}$. If $S_1 = 513$ and $S_4 = 4745$, find the minimum possible value for $S_2$.

Solution

Because the order of the $a$s doesn't matter, we simply need to find the number of $1$s $2$s $3$s and $4$s that minimize $S_2$. So let $w, x, y,$ and $z$ represent the number of $1$s, $2$s, $3$s, and $4$s respectively. Then we can write three equations based on these variables. Since there are a total of $350$ $a$s, we know that $w + x + y + z = 350$. We also know that $w + 2x + 3y + 4z = 513$ and $w + 16x + 81y + 256z = 4745$. We can now solve these down to two variables: \[w = 350 - x - y - z\] Substituting this into the second and third equations, we get \[x + 2y + 3z = 163\] and \[15x + 80y + 255z = 4395.\] The second of these can be reduced to \[3x + 16y + 51z = 879.\] Now we substitute $x$ from the first new equation into the other new equation. \[x = 163 - 2y - 3z\] \[3(163 - 2y - 3z) + 16y + 51z = 879\] \[489 + 10y + 42z = 879\] \[5y + 21z = 195\] Since $y$ and $z$ are integers, the two solutions to this are $(y,z) = (39,0)$ or $(18,5)$. If you plug both these solutions in to $S_2$ it is apparent that the second one returns a smaller value. It turns out that $w = 215$, $x = 112$, $y = 18$, and $z = 5$, so $S_2 = 215 + 4*112 + 9*18 + 16*5 = 215 + 448 + 162 + 80 = \boxed{905}$.

See also

2009 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 13
Followed by
Problem 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions
Invalid username
Login to AoPS