Предмет: Математика,
автор: evge6300
Из чисел 1,2,3,...,1799 выбран набор из 1200 попарно различных чисел. Какое наибольшее количество пар (a,b) таких, что a делится на b, всегда можно из них составить (найденные пары могут иметь общее число)?
Ответы
Автор ответа:
0
Ответ: 300.
Оценка.
Рассмотрим наибольший нечётный делитель каждого числа. Всего возможных делителей 1800/2 = 900, выбрано 1200 чисел, значит, есть не меньше 300 пар чисел, у которых наибольшие нечётные делители совпадают. Если у двух чисел этот делитель равен d, то числа равны 2^n * d, 2^m * d, и то число, у которого степень двойки меньше, делит то, у которого она больше, и из них можно составить пару.
Пример.
Из чисел 600, 601, ..., 1799 можно составить 300 пар: (600, 1200), (601, 1202), ..., (899, 1798).
Оценка.
Рассмотрим наибольший нечётный делитель каждого числа. Всего возможных делителей 1800/2 = 900, выбрано 1200 чисел, значит, есть не меньше 300 пар чисел, у которых наибольшие нечётные делители совпадают. Если у двух чисел этот делитель равен d, то числа равны 2^n * d, 2^m * d, и то число, у которого степень двойки меньше, делит то, у которого она больше, и из них можно составить пару.
Пример.
Из чисел 600, 601, ..., 1799 можно составить 300 пар: (600, 1200), (601, 1202), ..., (899, 1798).
Похожие вопросы
Предмет: Химия,
автор: mamreh08
Предмет: Алгебра,
автор: Аноним
Предмет: Алгебра,
автор: Аноним
Предмет: Информатика,
автор: Аноним
Предмет: Алгебра,
автор: locer