Difference between revisions of "2000 AIME II Problems/Problem 14"

(solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
Note that <math>1+\sum_{k=1}^{n} {k\cdot k!} = 1+\sum_{k=1}^{n} {(k+1)\cdot k!- k!} = 1+\sum_{k=1}^{n} {(k+1)!- k!} = (n+1)!</math>
+
Note that <math>1+\sum_{k=1}^{n-1} {k\cdot k!} = 1+\sum_{k=1}^{n-1} {(k+1)\cdot k!- k!} = 1+\sum_{k=1}^{n-1} {(k+1)!- k!} = n!</math>
  
The answer is <math>\boxed{495}</math>.
+
Thus for all <math>m\in\mathbb{N}</math>,
  
{{incomplete|solution}}
+
<math>(32m+16)!-(32m)! = \left(1+\sum_{k=1}^{32m+15} {k\cdot k!}\right)-\left(1+\sum_{k=1}^{32m-1} {k\cdot k!}\right) = \sum_{k=32m}^{32m+15}k\cdot k!.</math>
 +
 
 +
So now,
 +
 
 +
<math>
 +
\begin{align*}
 +
16!-32!+48!-64!+\cdots+1968!-1984!+2000!&=16!+(48!-32!)+(80!-64!)\cdots+(2000!-1984!)\\
 +
&=16! +\sum_{m=1}^{62}(32m+16)!-(32m)!\\
 +
&=16! +\sum_{m=1}^{62}\sum_{k=32m}^{32m+15}k\cdot k!
 +
\end{align*}
 +
</math>
 +
 
 +
Therefore we have <math>f_{16} = 1</math>, <math>f_k=k</math> if <math>32m\le k \le 32m+15</math> for some <math>m=1,2,\ldots,62</math>, and <math>f_k = 0</math> for all other <math>k</math>.
 +
 
 +
Therefore we have:
 +
 
 +
<math>
 +
\begin{align*}
 +
f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j &= (-1)^{17}\cdot 1 + \sum_{m=1}^{62}\sum_{k=32m}^{32m+15}(-1)^{k+1}k\\
 +
&= -1 + \sum_{m=1}^{62}\left[\sum_{j=16m}^{16m+7}(-1)^{2j+1}2j+\sum_{j=16m}^{16m+7}(-1)^{2j+2}(2j+1)\right]\\
 +
&= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}[(-1)^{2j+1}2j+(-1)^{2j+2}(2j+1)]\\
 +
&= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}[-2j+(2j+1)]\\
 +
&= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}1\\
 +
&= -1 + \sum_{m=1}^{62}8\\
 +
&= -1 + 8\cdot 62\\
 +
&= \boxed{495}
 +
\end{align*}
 +
</math>
  
 
{{AIME box|year=2000|n=II|num-b=13|num-a=15}}
 
{{AIME box|year=2000|n=II|num-b=13|num-a=15}}

Revision as of 22:43, 5 May 2008

Problem

Every positive integer $k$ has a unique factorial base expansion $(f_1,f_2,f_3,\ldots,f_m)$, meaning that $k=1!\cdot f_1+2!\cdot f_2+3!\cdot f_3+\cdots+m!\cdot f_m$, where each $f_i$ is an integer, $0\le f_i\le i$, and $0<f_m$. Given that $(f_1,f_2,f_3,\ldots,f_j)$ is the factorial base expansion of $16!-32!+48!-64!+\cdots+1968!-1984!+2000!$, find the value of $f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j$.

Solution

Note that $1+\sum_{k=1}^{n-1} {k\cdot k!} = 1+\sum_{k=1}^{n-1} {(k+1)\cdot k!- k!} = 1+\sum_{k=1}^{n-1} {(k+1)!- k!} = n!$

Thus for all $m\in\mathbb{N}$,

$(32m+16)!-(32m)! = \left(1+\sum_{k=1}^{32m+15} {k\cdot k!}\right)-\left(1+\sum_{k=1}^{32m-1} {k\cdot k!}\right) = \sum_{k=32m}^{32m+15}k\cdot k!.$

So now,

$\begin{align*} 16!-32!+48!-64!+\cdots+1968!-1984!+2000!&=16!+(48!-32!)+(80!-64!)\cdots+(2000!-1984!)\\ &=16! +\sum_{m=1}^{62}(32m+16)!-(32m)!\\ &=16! +\sum_{m=1}^{62}\sum_{k=32m}^{32m+15}k\cdot k! \end{align*}$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.)

Therefore we have $f_{16} = 1$, $f_k=k$ if $32m\le k \le 32m+15$ for some $m=1,2,\ldots,62$, and $f_k = 0$ for all other $k$.

Therefore we have:

$\begin{align*} f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j &= (-1)^{17}\cdot 1 + \sum_{m=1}^{62}\sum_{k=32m}^{32m+15}(-1)^{k+1}k\\ &= -1 + \sum_{m=1}^{62}\left[\sum_{j=16m}^{16m+7}(-1)^{2j+1}2j+\sum_{j=16m}^{16m+7}(-1)^{2j+2}(2j+1)\right]\\ &= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}[(-1)^{2j+1}2j+(-1)^{2j+2}(2j+1)]\\ &= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}[-2j+(2j+1)]\\ &= -1 + \sum_{m=1}^{62}\sum_{j=16m}^{16m+7}1\\ &= -1 + \sum_{m=1}^{62}8\\ &= -1 + 8\cdot 62\\ &= \boxed{495} \end{align*}$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.)

2000 AIME II (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