Maths Olympiad Prep

Library / /22 of 25

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Russia

Initially, a positive integer NN is written on the board. At each moment, Misha may choose a number a>1a > 1 on the board, remove it, and write down all its positive divisors except aa instead. After some time it happened that the board contains N2N^2 numbers. Determine all values of NN for which this can happen. (M. Fadin, K. Kovalenko)

Изначально на доске написано положительное целое число NN. В каждый момент Миша может выбрать на доске число a>1a > 1, стереть его и вместо него записать все его положительные делители, кроме aa. Через некоторое время оказалось, что на доске N2N^2 чисел. Для каких NN это возможно? (М. Фадин, К. Коваленко)

Solution

Answer: N=1N = 1.

Recall that
122+132++1n2<1. \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} < 1.
for all n>1n > 1. Using this inequality, show by induction on NN that the board may get at most N2N^2 numbers, with equality achieved only for N=1N = 1.

Lemma. For any natural n>1n > 1, the inequality
122+132++1n2<1 \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} < 1
holds.

Proof. Clearly, for t>1t > 1,
1t2<1t(t1)=1t11t. \frac{1}{t^2} < \frac{1}{t(t-1)} = \frac{1}{t-1} - \frac{1}{t}.
Summing such inequalities for t=2,3,,nt = 2, 3, \dots, n, we get
122+132++1n2<112+12+13++1n11n=11n<1, \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{n^2} < 1 - \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n-1} - \frac{1}{n} = 1 - \frac{1}{n} < 1, \quad \square
which is what was required.

Let us prove by induction on NN that for any natural NN, the board can contain at most N2N^2 numbers, and exactly N2N^2 numbers can appear only for N=1N = 1. This will yield the answer to the problem.

The base case N=1N = 1 is obvious. For the induction step, suppose N>1N > 1. Let 1=d1<d2<<dk<dk+1=N1 = d_1 < d_2 < \dots < d_k < d_{k+1} = N be all divisors of NN. After the first replacement, the numbers d1,d2,,dkd_1, d_2, \dots, d_k will be on the board. Mentally divide the board into kk parts so that the number djd_j is in the jj-th part. At each subsequent replacement, write the successors of a number in the same part where the number itself was. By the induction hypothesis, in the jj-th part of the board there can be at most dj2d_j^2 numbers. Therefore, the total number of numbers on the board cannot exceed d12+d22++dk2d_1^2 + d_2^2 + \dots + d_k^2.

Now note that the numbers N/d1>N/d2>>N/dk>N/dk+1N/d_1 > N/d_2 > \dots > N/d_k > N/d_{k+1} are also divisors of NN. Therefore, they are equal to dk+1,dk,,d2,d1d_{k+1}, d_k, \dots, d_2, d_1 respectively. Taking the lemma into account, we get that the total number of numbers on the board does not exceed:
d12+d22++dk2=N2dk+12+N2dk2++N2d22==N2(1d22+1d32++1dk+12)N2(122+132++1N2)<N21=N2, \begin{aligned} d_1^2 + d_2^2 + \dots + d_k^2 &= \frac{N^2}{d_{k+1}^2} + \frac{N^2}{d_k^2} + \dots + \frac{N^2}{d_2^2} = \\ &= N^2 \left( \frac{1}{d_2^2} + \frac{1}{d_3^2} + \dots + \frac{1}{d_{k+1}^2} \right) \le \\ &\le N^2 \left( \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{N^2} \right) < N^2 \cdot 1 = N^2, \end{aligned}
with strict inequality for N>1N > 1.

Therefore, the only possible value is N=1N = 1.

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 and solution reproduced as published; topic and difficulty added by this site.