Среди n+1 чисел, меньших 2n+1, найдутся 2 числа, отношение которых есть степень 2 // Сергей Фролов / Математический мирок

Доказать, что среди любых n 1 натуральных чисел, не превышающих 2n, найдутся два числа, отношение которых есть степень числа 2. Для решения задачи заметим, что любое натуральное число k можно единственным образом представить в виде 2^p∙q, где p — неотрицательное целое число, а q — положительное нечётное число. Число q будем называть “базой“ числа k. Несложно доказать, что для того, чтобы отношение двух натуральных чисел представляло собой число 2, возведённое в целую степень, необходимо и достаточно, чтобы базы этих чисел были равны. Таким образом, задача сводится к доказательству того, что среди любых n 1 натуральных чисел, не превышающих 2n, найдутся два числа с равными базами. Доказательство этого факта уже не представляет из себя никаких сложностей. Первоначальное условие задачи взято из книги И.Л. Бабинской “Задачи математических олимпиад“. Издательство “Наука“, Москва, 1975.