2017 AIME II Problem 8

Below is the professionally curated solution for Problem 8 of the 2017 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2017 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:divisibilitymodular arithmeticfactorialcasework

Difficulty rating: 2840

8.

Find the number of positive integers nn less than 20172017 such that 1+n+n22!+n33!+n44!+n55!+n66!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:

Multiplying by 6!=720,6! = 720, the sum is an integer exactly when 720n6+6n5+30n4+120n3+360n2.720 \mid n^6 + 6n^5 + 30n^4 + 120n^3 + 360n^2. If nn were odd, every term except n6n^6 would be even, making the total odd. If 3n,3 \nmid n, then modulo 33 every term except n6n^6 vanishes while n61(mod3).n^6 \equiv 1 \pmod 3. So nn must be a multiple of 6.6.

Write n=6k.n = 6k. Then 30n4=72054k4,30n^4 = 720 \cdot 54k^4, 120n3=72036k3,120n^3 = 720 \cdot 36k^3, and 360n2=72018k2360n^2 = 720 \cdot 18k^2 are all divisible by 720,720, while n6+6n5=66k5(k+1).n^6 + 6n^5 = 6^6 k^5(k + 1). Since 66=26366^6 = 2^6 3^6 supplies the factors 242^4 and 323^2 of 720=24325,720 = 2^4 \cdot 3^2 \cdot 5, the condition reduces to 5k(k+1),5 \mid k(k + 1), that is, k0k \equiv 0 or 4(mod5).4 \pmod 5.

For n=6k<2017n = 6k \lt 2017 we need 1k336.1 \le k \le 336. That range contains 6767 multiples of 55 and 6767 values with k4(mod5),k \equiv 4 \pmod 5, so there are 67+67=13467 + 67 = 134 such n.n.

← Problem 7Full ExamProblem 9

Problem 8 in Other Years