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 "2000 AIME II Problems/Problem 14"

(solution)
(less notation)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Every positive integer <math>k</math> has a unique factorial base expansion <math>(f_1,f_2,f_3,\ldots,f_m)</math>, meaning that <math>k=1!\cdot f_1+2!\cdot f_2+3!\cdot f_3+\cdots+m!\cdot f_m</math>, where each <math>f_i</math> is an integer, <math>0\le f_i\le i</math>, and <math>0<f_m</math>. Given that <math>(f_1,f_2,f_3,\ldots,f_j)</math> is the factorial base expansion of <math>16!-32!+48!-64!+\cdots+1968!-1984!+2000!</math>, find the value of <math>f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j</math>.
+
Every positive [[integer]] <math>k</math> has a unique factorial base expansion <math>(f_1,f_2,f_3,\ldots,f_m)</math>, meaning that <math>k=1!\cdot f_1+2!\cdot f_2+3!\cdot f_3+\cdots+m!\cdot f_m</math>, where each <math>f_i</math> is an integer, <math>0\le f_i\le i</math>, and <math>0<f_m</math>. Given that <math>(f_1,f_2,f_3,\ldots,f_j)</math> is the factorial base expansion of <math>16!-32!+48!-64!+\cdots+1968!-1984!+2000!</math>, find the value of <math>f_1-f_2+f_3-f_4+\cdots+(-1)^{j+1}f_j</math>.
  
 +
__TOC__
 
== Solution ==
 
== Solution ==
 +
=== Solution 1 ===
 
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>
 
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>
  
Line 36: Line 38:
 
</math>
 
</math>
  
 +
=== Solution 2 (less formality) ===
 +
Let <math>S = 16!-32!+\cdots-1984!+2000!</math>. Note that since <math>|S - 2000!| << 2000!</math> (or <math>|S - 2000!| = 1984! + \cdots</math> is significantly smaller than <math>2000!</math>), it follows that <math>1999! < S < 2000!</math>. Hence <math>f_{2000} = 0</math>. Then <math>2000! = 2000 \cdot 1999! = 1999 \cdot 1999! + 1999!</math>, and as <math>S - 2000! << 1999!</math>, it follows that <math>1999 \cdot 1999! < S < 2000 \cdot 1999!</math>. Hence <math>f_{1999} = 1999</math>, and we now need to find the factorial base expansion of
 +
 +
<cmath>S_2 = S - 1999 \cdot 1999! = 1999! - 1984! + 1962! - 1946! + \cdots + 16!</cmath>
 +
 +
Since <math>|S_2 - 1999!| << 1999!</math>, we can repeat the above argument recursively to yield <math>f_{1998} = 1998</math>, and so forth down to <math>f_{1985} = 1985</math>. Now <math>S_{16} = 1985! - 1984! + 1962! + \cdots = 1984 \cdot 1984! + 1962! + \cdots</math>, so <math>f_{1984} = 1984</math>.
 +
 +
The remaining sum is now just <math>1962! - 1946! + \cdots + 16!</math>. We can repeatedly apply the argument from the previous two paragraphs to find that <math>f_{16} = 1</math>, and <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>.
 +
 +
Now for each <math>m</math>, we have <math>-f_{32m} + f_{32m+1} - f_{32m+2} + \cdots + f_{32m + 31}</math> <math> = -32m + (32m + 1) - (32m + 2) + \cdots - (32m - 30) + (32 m + 31)</math> <math>= 1 + 1 + \cdots + 1 + 1</math> <math>= 8</math>. Thus, our answer is <math>-f_{16} + 8 \cdot 62 = \boxed{495}</math>.
 +
 +
== See also ==
 
{{AIME box|year=2000|n=II|num-b=13|num-a=15}}
 
{{AIME box|year=2000|n=II|num-b=13|num-a=15}}
 +
 +
[[Category:Intermediate Algebra Problems]]

Revision as of 13:25, 30 August 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

Solution 1

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. Unknown error_msg)

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. Unknown error_msg)

Solution 2 (less formality)

Let $S = 16!-32!+\cdots-1984!+2000!$. Note that since $|S - 2000!| << 2000!$ (or $|S - 2000!| = 1984! + \cdots$ is significantly smaller than $2000!$), it follows that $1999! < S < 2000!$. Hence $f_{2000} = 0$. Then $2000! = 2000 \cdot 1999! = 1999 \cdot 1999! + 1999!$, and as $S - 2000! << 1999!$, it follows that $1999 \cdot 1999! < S < 2000 \cdot 1999!$. Hence $f_{1999} = 1999$, and we now need to find the factorial base expansion of

\[S_2 = S - 1999 \cdot 1999! = 1999! - 1984! + 1962! - 1946! + \cdots + 16!\]

Since $|S_2 - 1999!| << 1999!$, we can repeat the above argument recursively to yield $f_{1998} = 1998$, and so forth down to $f_{1985} = 1985$. Now $S_{16} = 1985! - 1984! + 1962! + \cdots = 1984 \cdot 1984! + 1962! + \cdots$, so $f_{1984} = 1984$.

The remaining sum is now just $1962! - 1946! + \cdots + 16!$. We can repeatedly apply the argument from the previous two paragraphs to find that $f_{16} = 1$, and $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$.

Now for each $m$, we have $-f_{32m} + f_{32m+1} - f_{32m+2} + \cdots + f_{32m + 31}$ $= -32m + (32m + 1) - (32m + 2) + \cdots - (32m - 30) + (32 m + 31)$ $= 1 + 1 + \cdots + 1 + 1$ $= 8$. Thus, our answer is $-f_{16} + 8 \cdot 62 = \boxed{495}$.

See also

2000 AIME II (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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_AIME_II_Problems/Problem_14&oldid=27635"