2011 AIME I Problem 7

Below is the professionally curated solution for Problem 7 of the 2011 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2011 AIME I 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:modular arithmeticfactor counting

Difficulty rating: 2710

7.

Find the number of positive integers mm for which there exist nonnegative integers x0,x1,,x2011,x_0, x_1, \ldots, x_{2011}, such that mx0=k=12011mxk.m^{x_0} = \sum_{k=1}^{2011} m^{x_k}.

Solution:

The value m=1m = 1 fails, since the right side would be 20112011 while the left side is 1.1. For m2,m \ge 2, reduce mod m1:m - 1: every power of mm is 1,\equiv 1, so the equation forces 12011(modm1),1 \equiv 2011 \pmod{m - 1}, that is, m1m - 1 divides 2010.2010.

Conversely, suppose 2010=(m1)n.2010 = (m - 1)n. Take x0=n,x_0 = n, let mm of the xkx_k equal 0,0, and for each r=1,2,,n1r = 1, 2, \ldots, n - 1 let m1m - 1 of the xkx_k equal r.r. This uses m+(m1)(n1)=n(m1)+1=2011m + (m - 1)(n - 1) = n(m - 1) + 1 = 2011 terms, and the sum telescopes: m+(m1)(m+m2++mn1)=m+(mnm)=mn=mx0.m + (m - 1)(m + m^2 + \cdots + m^{n-1}) = m + (m^n - m) = m^n = m^{x_0}.

So the equation is solvable exactly when m1m - 1 divides 2010=23567,2010 = 2 \cdot 3 \cdot 5 \cdot 67, which has 24=162^4 = 16 divisors. There are 1616 such m.m.

← Problem 6Full ExamProblem 8

Problem 7 in Other Years