Maths Olympiad Prep

Library / /280 of 377

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:
Call a positive integer in base 1010 kk-good if we can split it into two integers yy and zz, such that yy is all digits on the left and zz is all digits on the right, and such that y=kzy = k \cdot z. For example, 20102010 is 22-good because we can split it into 2020 and 1010 and 20=21020 = 2 \cdot 10. 2001020010 is also 22-good, because we can split it into 2020 and 010010. In addition, it is 2020-good, because we can split it into 200200 and 1010.
Show that there exists a 4848-good perfect square.

Solution

Solution:
We wish to find integers aa, zz such that 48z10a+z=z(4810a+1)48z \cdot 10^{a} + z = z\left(48 \cdot 10^{a} + 1\right) is a perfect square, where z<10az < 10^{a}. This would prove that there exists a 4848-good perfect square because we are pulling off the last aa digits of the number and get two integers 48z48z and zz.

To make zz small by keeping the product a perfect square, we'd like 4810a+148 \cdot 10^{a} + 1 to be divisible by some reasonably large square. Take a=42=φ(49)a = 42 = \varphi(49). By Euler's theorem, 10421(mod49)10^{42} \equiv 1 \pmod{49}, so 4810a+148 \cdot 10^{a} + 1 is a multiple of 4949.

Then we can take z=4810a+149z = \frac{48 \cdot 10^{a} + 1}{49}. (Clearly z<10az < 10^{a}, so we're fine.) Then we have
z(4810a+1)=(481042+17)2. z\left(48 \cdot 10^{a} + 1\right) = \left(\frac{48 \cdot 10^{42} + 1}{7}\right)^{2}.

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.