Maths Olympiad Prep

Library / IRL ABooklet /27 of 191

IRL ABooklet

Number theory Difficulty 5.0 AIME, harder Prove it Ireland

You are given a positive integer. Prove that you can append digits to the given number so that the resulting number is a perfect square.

For example, the given integer 12341234 can be extended to 12341169=3513212341169 = 3513^2.

Solutions — 2

Solution 1

Let pp be the given number and suppose we extend it by nn digits. The value of nn is still to be determined. The smallest such extension is p⋅10np \cdot 10^n and the largest is (p+1)⋅10n−1(p+1) \cdot 10^n - 1.
It is possible to complete the number pp to a perfect square by appending nn digits if there exists an integer mm such that
p⋅10n≤m2<(p+1)⋅10n, i.e.  p \cdot 10^n \leq m^2 < (p+1) \cdot 10^n, \quad \text{ i.e. }
p⋅10n2≤m<p+1⋅10n2. \sqrt{p} \cdot 10^{\frac{n}{2}} \leq m < \sqrt{p+1} \cdot 10^{\frac{n}{2}}.
Because p+1−p>0\sqrt{p+1} - \sqrt{p} > 0, for nn large enough we have (p+1−p)⋅10n2>1(\sqrt{p+1} - \sqrt{p}) \cdot 10^{\frac{n}{2}} > 1. Hence, there is an integer between p⋅10n2\sqrt{p} \cdot 10^{\frac{n}{2}} and p+1⋅10n2\sqrt{p+1} \cdot 10^{\frac{n}{2}}.

Solution 2

Let the given number pp have less than kk digits, i.e. p<10kp < 10^k. Let NN be the largest integer for which N2≤p⋅10k+1N^2 \leq p \cdot 10^{k+1}, i.e.
N2≤p⋅10k+1<(N+1)2. N^2 \leq p \cdot 10^{k+1} < (N+1)^2.
Combining N2≤p⋅10k+1N^2 \leq p \cdot 10^{k+1} with p<10kp < 10^k we get N2<102k+1N^2 < 10^{2k+1}, and so N<10⋅10kN < \sqrt{10} \cdot 10^k. Using 1+210<101 + 2\sqrt{10} < 10, which follows from 40=(210)2<9240 = (2\sqrt{10})^2 < 9^2, we obtain
2N+1<210⋅10k+1<(1+210)10k<10k+1. 2N + 1 < 2\sqrt{10} \cdot 10^k + 1 < (1 + 2\sqrt{10}) 10^k < 10^{k+1}.
We then get
0<p⋅10k+1<(N+1)2=N2+(2N+1)<p⋅10k+1+10k+1=(p+1)⋅10k+1. 0 < p \cdot 10^{k+1} < (N+1)^2 = N^2 + (2N+1) < p \cdot 10^{k+1} + 10^{k+1} = (p+1) \cdot 10^{k+1}.
This means that the number (N+1)2(N + 1)^2 is obtained from the number pp by appending k+1k + 1 digits.

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.