Olympiad Maths Prep

Library / /15 of 22

Number theory Difficulty 5.8 AIME, harder Prove it Ukraine

We call a natural number a *twin* if it has two natural divisors whose difference is equal to 22. Determine whether there are more twin numbers or the numbers that are not twin among the first 2011201220112012 natural numbers.

Solution

Let NN be the number of twin numbers that do not exceed MM. Then NN3+N4N12N \ge N_3 + N_4 - N_{12}, since all the numbers from M3M_3 and M4M_4 are twin, as they have divisors 1,31, 3 and 2,42, 4 respectively, and M2M_2 consists of all the numbers that belong to both M3M_3 and M4M_4. But there are also twin numbers that do not exceed MM and do not belong neither to M3M_3 nor to M4M_4, for example 35=5735 = 5 \cdot 7, and so we even have that N>N3+N4N12N > N_3 + N_4 - N_{12}. Since MM is divisible by 1212, we obtain:
N>M3+M4M12=M2, N > \frac{M}{3} + \frac{M}{4} - \frac{M}{12} = \frac{M}{2},
which precisely means that there are more twin numbers than the numbers that are not twin among the first M=20112012M = 20112012 natural numbers.

Looking for a route rather than 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.