Из чисел 1,2,3,…,1799 выбран набор из 1200 попарно различных чисел. Какое наибольшее количество пар (a,b) таких, что a делится на b, всегда можно из них составить (найденные пары могут иметь общее число)?

Вопрос школьника по предмету Математика

Из чисел 1,2,3,…,1799 выбран набор из 1200 попарно различных чисел. Какое наибольшее количество пар (a,b) таких, что a делится на b, всегда можно из них составить (найденные пары могут иметь общее число)?

Ответ учителя по предмету Математика

Ответ: 300.

Оценка. 

Рассмотрим наибольши
й нечётный делитель каждого числа. Всего возможных делителей 1800/2 = 900, выбрано 1200 чисел, значит, есть не меньше 300 пар чисел, у которых наибольшие нечётные делители совпадают. Если у двух чисел этот делитель равен d, то числа равны 2^n * d, 2^m * d, и то число, у которого степень двойки меньше, делит то, у которого она больше, и из них можно составить пару.

Пример.

Из чисел 600, 601, …, 1799 можно составить 300 пар: (600, 1200), (601, 1202), …, (899, 1798).