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 14:38, 20 March 2009
Problem
For 
, define 
, where 
. If 
and 
, find the minimum possible value for 
.
Solution
Because the order of the 
s doesn't matter, we simply need to find the number of 
s 
s 
s and 
s that minimize . So let 
and 
represent the number of s, s, s, and s respectively. Then we can write three equations based on these variables. Since there are a total of 
s, we know that 
. We also know that 
and 
. We can now solve these down to two variables:
![\[w = 350 - x - y - z\]](http://latex.artofproblemsolving.com/2/e/f/2efaf625d834188161eb8a033fba648bb0286a80.png)
Substituting this into the second and third equations, we get
![\[x + 2y + 3z = 163\]](http://latex.artofproblemsolving.com/3/b/e/3be0445083f31b8826ca1c819f412b6f54e00edd.png)
and
![\[15x + 80y + 255z = 4395.\]](http://latex.artofproblemsolving.com/d/1/7/d1712bbcb227a1dd16ff28d3dc7f3e3db6258e50.png)
The second of these can be reduced to
![\[3x + 16y + 51z = 879.\]](http://latex.artofproblemsolving.com/b/a/a/baa1f5c639194187ddad1036d6b4bb3d4ada662b.png)
Now we substitute 
from the first new equation into the other new equation.
![\[x = 163 - 2y - 3z\]](http://latex.artofproblemsolving.com/0/2/3/023202aff61bf26fad87e3cfba65d67327eb934d.png)
![\[3(163 - 2y - 3z) + 16y + 51z = 879\]](http://latex.artofproblemsolving.com/b/8/f/b8f72cfe7798221c814ad09dbd829b75c55fc731.png)
![\[489 + 10y + 42z = 879\]](http://latex.artofproblemsolving.com/3/0/4/30478cb0ed3a311ffd40ef087fea203d48f1382b.png)
![\[5y + 21z = 195\]](http://latex.artofproblemsolving.com/e/6/0/e607b9dbd6db04ee38bfc295f50ddcbdc88908f2.png)
Since 
and are integers, the two solutions to this are 
or 
.
If you plug both these solutions in to it is apparent that the second one returns a smaller value. It turns out that 
, 
, 
, and 
, so 
.
See also
| 2009 AIME I (Problems • Answer Key • Resources) | ||
| 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 | ||
