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 "2017 AIME II Problems/Problem 8"

(→‎Solution 1)
m (→‎Solution 2)
Line 7: Line 7:
 
==Solution 2==
 
==Solution 2==
 
Taking out the <math>1+n</math> part of the expression and writing the remaining terms under a common denominator, we get <math>\frac{1}{720}(n^6+6n^5+30n^4+120n^3+360n^2)</math>. Therefore the expression <math>n^6+6n^5+30n^4+120n^3+360n^2</math> must equal <math>720m</math> for some positive integer <math>m</math>.
 
Taking out the <math>1+n</math> part of the expression and writing the remaining terms under a common denominator, we get <math>\frac{1}{720}(n^6+6n^5+30n^4+120n^3+360n^2)</math>. Therefore the expression <math>n^6+6n^5+30n^4+120n^3+360n^2</math> must equal <math>720m</math> for some positive integer <math>m</math>.
−
Taking both sides mod <math>2</math>, the result is <math>n^6\equiv0(\text{mod }2)</math>. Therefore <math>n</math> must be even. If <math>n</math> is even, that means <math>n</math> can be written in the form <math>2a</math> where <math>a</math> is a positive integer. Replacing <math>n</math> with <math>2a</math> in the expression, <math>64a^6+192a^5+480a^4+960a^3+1440a^2</math> is divisible by <math>16</math> because each coefficient is divisible by <math>16</math>. Therefore, if <math>n</math> is even, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> is divisible by <math>16</math>.
+
Taking both sides mod <math>2</math>, the result is <math>n^6 \equiv 0 \pmod{2}</math>. Therefore <math>n</math> must be even. If <math>n</math> is even, that means <math>n</math> can be written in the form <math>2a</math> where <math>a</math> is a positive integer. Replacing <math>n</math> with <math>2a</math> in the expression, <math>64a^6+192a^5+480a^4+960a^3+1440a^2</math> is divisible by <math>16</math> because each coefficient is divisible by <math>16</math>. Therefore, if <math>n</math> is even, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> is divisible by <math>16</math>.
  
−
Taking the equation <math>n^6+6n^5+30n^4+120n^3+360n^2=720m</math> mod <math>3</math>, the result is <math>n^6\equiv0(\text{mod }3)</math>. Therefore <math>n</math> must be a multiple of <math>3</math>. If <math>n</math> is a multiple of three, that means <math>n</math> can be written in the form <math>3b</math> where <math>b</math> is a positive integer. Replacing <math>n</math> with <math>3b</math> in the expression, <math>729b^6+1458b^5+2430b^4+3240b^3+3240b^2</math> is divisible by <math>9</math> because each coefficient is divisible by <math>9</math>. Therefore, if <math>n</math> is a multiple of <math>3</math>, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> is divisibly by <math>9</math>.
+
Taking the equation <math>n^6+6n^5+30n^4+120n^3+360n^2=720m</math> mod <math>3</math>, the result is <math>n^6 \equiv 0 \pmod{3}</math>. Therefore <math>n</math> must be a multiple of <math>3</math>. If <math>n</math> is a multiple of three, that means <math>n</math> can be written in the form <math>3b</math> where <math>b</math> is a positive integer. Replacing <math>n</math> with <math>3b</math> in the expression, <math>729b^6+1458b^5+2430b^4+3240b^3+3240b^2</math> is divisible by <math>9</math> because each coefficient is divisible by <math>9</math>. Therefore, if <math>n</math> is a multiple of <math>3</math>, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> is divisibly by <math>9</math>.
  
−
Taking the equation <math>n^6+6n^5+30n^4+120n^3+360n^2=720m</math> mod <math>5</math>, the result is <math>n^6+n^5\equiv0(\text{mod }3)</math>. The only values of <math>n (\text{mod }5)</math> that satisfy the equation are <math>n\equiv0(\text{mod }5)</math> and <math>n\equiv4(\text{mod }5)</math>. Therefore if <math>n</math> is <math>0</math> or <math>4</math> mod <math>5</math>, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> will be a multiple of <math>5</math>.
+
Taking the equation <math>n^6+6n^5+30n^4+120n^3+360n^2=720m</math> mod <math>5</math>, the result is <math>n^6+n^5 \equiv 0 \pmod{5}</math>. The only values of <math>n (\text{mod }5)</math> that satisfy the equation are <math>n\equiv0(\text{mod }5)</math> and <math>n\equiv4(\text{mod }5)</math>. Therefore if <math>n</math> is <math>0</math> or <math>4</math> mod <math>5</math>, <math>n^6+6n^5+30n^4+120n^3+360n^2</math> will be a multiple of <math>5</math>.
  
−
The only way to get the expression <math>n^6+6n^5+30n^4+120n^3+360n^2</math> to be divisible by <math>720=16\times9\times5</math> is to have <math>n\equiv0(\text{mod }2)</math>, <math>n\equiv0(\text{mod }3)</math>, and <math>n\equiv0\text{ or }4(\text{mod }5)</math>. By the Chinese Remainder Theorem or simple guessing and checking, we see <math>n\equiv0,24(\text{mod }30)</math>. Because no numbers between <math>2011</math> and <math>2017</math> are equivalent to <math>0</math> or <math>24</math> mod <math>30</math>, the answer is <math>\frac{2010}{30}\times2=\boxed{134}</math>.
+
The only way to get the expression <math>n^6+6n^5+30n^4+120n^3+360n^2</math> to be divisible by <math>720=16 \cdot 9 \cdot 5</math> is to have <math>n \equiv 0 \pmod{2}</math>, <math>n \equiv 0 \pmod{3}</math>, and <math>n \equiv 0 \text{ or } 4 \pmod{5}</math>. By the Chinese Remainder Theorem or simple guessing and checking, we see <math>n\equiv0,24(\text{mod }30)</math>. Because no numbers between <math>2011</math> and <math>2017</math> are equivalent to <math>0</math> or <math>24</math> mod <math>30</math>, the answer is <math>\frac{2010}{30}\times2=\boxed{134}</math>.
  
 
=See Also=
 
=See Also=
 
{{AIME box|year=2017|n=II|num-b=7|num-a=9}}
 
{{AIME box|year=2017|n=II|num-b=7|num-a=9}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 17:32, 23 March 2017

Problem

Find the number of positive integers $n$ less than $2017$ such that \[1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}\] is an integer.

Solution 1

The denominator contains $2,3,5$. Therefore, one possibility is that $n|30$. This yields the numbers $30,60,90,120,\cdots,2010$. There are a total of ${67}$ numbers in the sequence. We express the last two terms as $\frac{6n^5+n^6}{720} \implies \frac{n^5(6+n)}{720}$ This yields that $n \equiv 0, 24 \pmod{30}$. Therefore, we get the final answer of $67 + 67 = \boxed{134}$.

Solution 2

Taking out the $1+n$ part of the expression and writing the remaining terms under a common denominator, we get $\frac{1}{720}(n^6+6n^5+30n^4+120n^3+360n^2)$. Therefore the expression $n^6+6n^5+30n^4+120n^3+360n^2$ must equal $720m$ for some positive integer $m$. Taking both sides mod $2$, the result is $n^6 \equiv 0 \pmod{2}$. Therefore $n$ must be even. If $n$ is even, that means $n$ can be written in the form $2a$ where $a$ is a positive integer. Replacing $n$ with $2a$ in the expression, $64a^6+192a^5+480a^4+960a^3+1440a^2$ is divisible by $16$ because each coefficient is divisible by $16$. Therefore, if $n$ is even, $n^6+6n^5+30n^4+120n^3+360n^2$ is divisible by $16$.

Taking the equation $n^6+6n^5+30n^4+120n^3+360n^2=720m$ mod $3$, the result is $n^6 \equiv 0 \pmod{3}$. Therefore $n$ must be a multiple of $3$. If $n$ is a multiple of three, that means $n$ can be written in the form $3b$ where $b$ is a positive integer. Replacing $n$ with $3b$ in the expression, $729b^6+1458b^5+2430b^4+3240b^3+3240b^2$ is divisible by $9$ because each coefficient is divisible by $9$. Therefore, if $n$ is a multiple of $3$, $n^6+6n^5+30n^4+120n^3+360n^2$ is divisibly by $9$.

Taking the equation $n^6+6n^5+30n^4+120n^3+360n^2=720m$ mod $5$, the result is $n^6+n^5 \equiv 0 \pmod{5}$. The only values of $n (\text{mod }5)$ that satisfy the equation are $n\equiv0(\text{mod }5)$ and $n\equiv4(\text{mod }5)$. Therefore if $n$ is $0$ or $4$ mod $5$, $n^6+6n^5+30n^4+120n^3+360n^2$ will be a multiple of $5$.

The only way to get the expression $n^6+6n^5+30n^4+120n^3+360n^2$ to be divisible by $720=16 \cdot 9 \cdot 5$ is to have $n \equiv 0 \pmod{2}$, $n \equiv 0 \pmod{3}$, and $n \equiv 0 \text{ or } 4 \pmod{5}$. By the Chinese Remainder Theorem or simple guessing and checking, we see $n\equiv0,24(\text{mod }30)$. Because no numbers between $2011$ and $2017$ are equivalent to $0$ or $24$ mod $30$, the answer is $\frac{2010}{30}\times2=\boxed{134}$.

See Also

2017 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 7 		Followed by
Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_8&oldid=84971"