2017 AIME II Problems/Problem 8

Revision as of 12:45, 29 November 2020 by Puffer13 (talk | contribs) (Solution 2 (Not Rigorous))

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 $0\pmod{30}-6$. 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 $0\pmod{30}-6$ 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 $\lfloor\frac{2017}{30}\rfloor$ and multiply it by $2$. Thus, we get $67\cdot2=\boxed{134}$.

Solution by IronicNinja~

Solution 3

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 4

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(\mod 5)$, so combining with divisibility by 6, $n$ is $24$ or $0$ (mod $30$). There are $67$ cases for each, hence the answer $\boxed{134}$.

See Also

2017 AIME II (ProblemsAnswer KeyResources)
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