Latest revision as of 10:29, 18 October 2022

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

We start with the last two terms of the polynomial $1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}$ , which are $\frac{n^5}{5!}+\frac{n^6}{6!}$ . This can simplify to $\frac{6n^5+n^6}{720}$ , which can further simplify to $\frac{n^5(6+n)}{720}$ . Notice that the prime factorization of $720$ is $5\cdot3\cdot3\cdot2\cdot2\cdot2\cdot2$ . In order for $\frac{n^5(6+n)}{720}$ to be an integer, one of the parts must divide $5, 3$ , and $2$ . Thus, one of the parts must be a multiple of $5, 3$ , and $2$ , and the LCM of these three numbers is $30$ . This means $n^5 \equiv 0\pmod{30}$ or $6+n \equiv 0\pmod{30}$ Thus, we can see that $n$ must equal $0\pmod{30}$ or $-6\pmod{30}$ . Note that as long as we satisfy $\frac{6n^5+n^6}{720}$ , $2!, 3!$ , and $4!$ will all divide into integers, as their prime factorizations will be fulfilled with the LCM being 30. E.g. $4! = 2\cdot2\cdot2\cdot2\cdot3$ , and this will be divisible by $2^4\cdot3^4\cdot5^4$ . Now, since we know that $n$ must equal $0\pmod{30}$ or $-6\pmod{30}$ in order for the polynomial to be an integer, $n\equiv0, 24\pmod{30}$ . To find how many integers fulfill the equation and are $<2017$ , we take $\left \lfloor\frac{2017}{30} \right \rfloor$ and multiply it by $2$ . Thus, we get $67\cdot2=\boxed{134}$ .

~Solution by IronicNinja~

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 \pmod{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}$ .

Solution 3

Note that $1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}$ will have a denominator that divides $5!$ . Therefore, for the expression to be an integer, $\frac{n^6}{6!}$ must have a denominator that divides $5!$ . Thus, $6\mid n^6$ , and $6\mid n$ . Let $n=6m$ . Substituting gives $1+6m+\frac{6^2m^2}{2!}+\frac{6^3m^3}{3!}+\frac{6^4m^4}{4!}+\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}$ . Note that the first $5$ terms are integers, so it suffices for $\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}$ to be an integer. This simplifies to $\frac{6^5}{5!}m^5(m+1)=\frac{324}{5}m^5(m+1)$ . It follows that $5\mid m^5(m+1)$ . Therefore, $m$ is either $0$ or $4$ modulo $5$ . However, we seek the number of $n$ , and $n=6m$ . By CRT, $n$ is either $0$ or $24$ modulo $30$ , and the answer is $67+67=\boxed{134}$ .

-TheUltimate123

Step Solution

Clearly $1+n$ is an integer. The part we need to verify as an integer is, upon common denominator, $\frac{360n^2+120n^3+30n^4+6n^5+n^6}{720}$ . Clearly, the numerator must be even for the fraction to be an integer. Therefore, $n^6$ is even and n is even, aka $n=2k$ for some integer $k$ . Then, we can substitute $n=2k$ and see that $\frac{n^2}{2}$ is trivially integral. Then, substitute for the rest of the non-confirmed-integral terms and get $\frac{60k^3+30k^4+12k^5+4k^6}{45}$ . It is also clear that for this to be an integer, which it needs to be, the numerator has to be divisible by 3. The only term we worry about is the $4k^6$ , and we see that $k=3b$ for some integer $b$ . From there we now know that $n=6b$ . If we substitute again, we see that all parts except the last two fractions are trivially integral. In order for the last two fractions to sum to an integer we see that $n^5(6n+1) \equiv 0 \pmod5$ , so combining with divisibility by 6, $n$ is $24$ or $0\pmod{30}$ . There are $67$ cases for each, hence the answer $\boxed{134}$ .

@@ Line 2: / Line 2: @@
 Find the number of positive integers <math>n</math> less than <math>2017</math> such that <cmath>1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}</cmath> is an integer.
-==Solution==
+==Solution 1==
-The denominator contains <math>2,3,5</math>. Therefore, <math>n|30</math>. This yields the numbers, <math>30,60,90,120,\cdots,2010</math>. There are a total of <math>\boxed{67}</math> numbers in the sequence.
+We start with the last two terms of the polynomial <math>1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}+\frac{n^6}{6!}</math>, which are <math>\frac{n^5}{5!}+\frac{n^6}{6!}</math>. This can simplify to <math>\frac{6n^5+n^6}{720}</math>, which can further simplify to <math>\frac{n^5(6+n)}{720}</math>. Notice that the prime factorization of <math>720</math> is <math>5\cdot3\cdot3\cdot2\cdot2\cdot2\cdot2</math>. In order for <math>\frac{n^5(6+n)}{720}</math> to be an integer, one of the parts must divide <math>5, 3</math>, and <math>2</math>. Thus, one of the parts must be a multiple of <math>5, 3</math>, and <math>2</math>, and the LCM  of these three numbers is <math>30</math>. This means <cmath>n^5 \equiv 0\pmod{30}</cmath> or <cmath>6+n \equiv 0\pmod{30}</cmath> Thus, we can see that <math>n</math> must equal <math>0\pmod{30}</math> or <math>-6\pmod{30}</math>. Note that as long as we satisfy <math>\frac{6n^5+n^6}{720}</math>, <math>2!, 3!</math>, and <math>4!</math> will all divide into integers, as their prime factorizations will be fulfilled with the LCM being 30. E.g. <math>4! = 2\cdot2\cdot2\cdot2\cdot3</math>, and this will be divisible by <math>2^4\cdot3^4\cdot5^4</math>. Now, since we know that <math>n</math> must equal <math>0\pmod{30}</math> or <math>-6\pmod{30}</math> in order for the polynomial to be an integer, <math>n\equiv0, 24\pmod{30}</math>. To find how many integers fulfill the equation and are <math><2017</math>, we take <math>\left \lfloor\frac{2017}{30} \right \rfloor</math> and multiply it by <math>2</math>. Thus, we get <math>67\cdot2=\boxed{134}</math>.
+~Solution by IronicNinja~
+==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 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 \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 \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 \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 \pmod{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>.
+==Solution 3==
+Note that <math>1+n+\frac{n^2}{2!}+\frac{n^3}{3!}+\frac{n^4}{4!}+\frac{n^5}{5!}</math> will have a denominator that divides <math>5!</math>. Therefore, for the expression to be an integer, <math>\frac{n^6}{6!}</math> must have a denominator that divides <math>5!</math>. Thus, <math>6\mid n^6</math>, and <math>6\mid n</math>. Let <math>n=6m</math>. Substituting gives <math>1+6m+\frac{6^2m^2}{2!}+\frac{6^3m^3}{3!}+\frac{6^4m^4}{4!}+\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}</math>. Note that the first <math>5</math> terms are integers, so it suffices for <math>\frac{6^5m^5}{5!}+\frac{6^6m^6}{6!}</math> to be an integer. This simplifies to <math>\frac{6^5}{5!}m^5(m+1)=\frac{324}{5}m^5(m+1)</math>. It follows that <math>5\mid m^5(m+1)</math>. Therefore, <math>m</math> is either <math>0</math> or <math>4</math> modulo <math>5</math>. However, we seek the number of <math>n</math>, and <math>n=6m</math>. By CRT, <math>n</math> is either <math>0</math> or <math>24</math> modulo <math>30</math>, and the answer is <math>67+67=\boxed{134}</math>.
+-TheUltimate123
+==Step Solution==
+Clearly <math>1+n</math> is an integer. The part we need to verify as an integer is, upon common denominator, <math>\frac{360n^2+120n^3+30n^4+6n^5+n^6}{720}</math>. Clearly, the numerator must be even for the fraction to be an integer. Therefore, <math>n^6</math> is even and n is even, aka <math>n=2k</math> for some integer <math>k</math>. Then, we can substitute <math>n=2k</math> and see that <math>\frac{n^2}{2}</math> is trivially integral. Then, substitute for the rest of the non-confirmed-integral terms and get <math>\frac{60k^3+30k^4+12k^5+4k^6}{45}</math>. It is also clear that for this to be an integer, which it needs to be, the numerator has to be divisible by 3. The only term we worry about is the <math>4k^6</math>, and we see that <math>k=3b</math> for some integer <math>b</math>. From there we now know that <math>n=6b</math>. If we substitute again, we see that all parts except the last two fractions are trivially integral. In order for the last two fractions to sum to an integer we see that <math>n^5(6n+1) \equiv 0 \pmod5</math>, so combining with divisibility by 6, <math>n</math> is <math>24</math> or <math>0\pmod{30}</math>. There are <math>67</math> cases for each, hence the answer <math>\boxed{134}</math>.
 =See Also=
 {{AIME box|year=2017|n=II|num-b=7|num-a=9}}
 {{MAA Notice}}

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

Page

Toolbox

Search

Difference between revisions of "2017 AIME II Problems/Problem 8"