Maths Olympiad Prep

Library / /51 of 57

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

Peter chose several consecutive positive integers. He wrote down each of the chosen numbers either in red or in blue (both colors are present). Is it possible that the sum of the l.c.m. of the red numbers and the l.c.m. of the blue numbers is a power of 2? (O. Dmitriev, R. Zhenodarov)

Петя выбрал несколько последовательных положительных целых чисел. Он записал каждое из выбранных чисел либо красным, либо синим цветом (оба цвета присутствуют). Может ли сумма НОК красных чисел и НОК синих чисел быть степенью двойки? (О. Дмитриев, Р. Жендодаров)

Solution

Let 2k2^k be the maximal power of 22 dividing one of the chosen numbers; since the numbers are consecutive, 2k2^k divides exactly one of them. Then one of the two l.c.m.'s under consideration is divisible by 2k2^k, while the other is not.

Suppose the contrary. Consider the powers of 22 dividing the chosen numbers; let 2k2^k be the largest among them. If at least two of the chosen numbers are divisible by 2k2^k, then two consecutive such numbers will differ by 2k2^k. Therefore, one of them will be divisible by 2k+12^{k+1}, which is impossible by the choice of kk. Thus, among the chosen numbers, exactly one is divisible by 2k2^k.

The l.c.m. of the group containing this number will be divisible by 2k2^k, and the l.c.m. of the remaining group will not be. Therefore, the sum of these l.c.m.'s is not divisible by 2k2^k; on the other hand, this sum is greater than 2k2^k. Therefore, this sum cannot be a power of 22.

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.