# 2009 AIME I Problems/Problem 14

## 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}$.