2011 AIME I Problem 7

Attempt Problem 7 of the 2011 AIME I below, then check your answer against the professionally curated solution 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 problems are used with official legal permission of the Mathematical Association of America (MAA).

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}.

Answer: 16
Concepts:modular arithmeticfactor counting
Difficulty rating: 2710
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)m + (m - 1)(n - 1) =n(m1)+1= n(m - 1) + 1 =2011= 2011 terms, and the sum telescopes: m+(m1)(m+m2++mn1)=m+(mnm)=mn=mx0. \begin{aligned} &m \\ &\quad {}+ (m - 1) \\ &\quad {}\cdot (m + m^2 + \cdots + m^{n-1}) \\ &\quad {}= m + (m^n - m) \\ &\quad {}= m^n = m^{x_0}. \end{aligned}

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 6#6
Full Exam

Problem 7 in Other Years