Maths Olympiad Prep

Library / Hong Kong competition problems /22 of 42

Hong Kong competition problems, 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 m−1m-1 numbers more after applying each operation. Initially, there is only one number. Therefore, it is the same as finding those m∈Z+m \in \mathbb{Z}^+ such that m−1∣2011−1=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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