Maths Olympiad Prep

Library / /26 of 48

, 2012

Number theory Difficulty 5.8 AIME, harder Prove it Hong Kong

Determine the number of positive integers mm for which there exist nonnegative integers x0,x1,x2,,x2011x_0, x_1, x_2, \dots, x_{2011} such that mx0=mx1+mx2++mx2011m^{x_0} = m^{x_1} + m^{x_2} + \dots + m^{x_{2011}}.

Solution

There are 16 such positive integers mm.
Let ak=mka_k = m^k. We would like to represent ax0a_{x_0} as a sum of 2011 numbers of the form axja_{x_j}. To get such a representation, we can do in the following way. Starting from the number ax0a_{x_0}, each time we choose a number ak+1a_{k+1} and break it into mm numbers aka_k, so that the sum of all numbers remains ax0a_{x_0}.

In view of the base mm representation of the numbers, if we can write
ax0=ax1+ax2++ax2011, a_{x_0} = a_{x_1} + a_{x_2} + \cdots + a_{x_{2011}},
then we are able to obtain the numbers on the right by using the above operation repeatedly. Conversely, if we can obtain these numbers after some operations, then clearly their sum is ax0a_{x_0} by construction. Therefore, it remains to check for which mm we can apply finitely many operations so that we can generate exactly 2011 numbers.

Note that there are m1m-1 numbers more after applying each operation. Initially, there is only one number. Therefore, it is the same as finding those mZ+m \in \mathbb{Z}^+ such that m120111=2010m - 1 \mid 2011 - 1 = 2010. As 2010=2×3×5×672010 = 2 \times 3 \times 5 \times 67, there are d(2010)=16d(2010) = 16 solutions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.