Задача
На доске написано n натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.
а) Докажите, что можно провести только конечное число операций.
б) Финальный результат независимо от порядка действий будет одним и тем же. Например:
(4, 6, 9) → (2, 12, 9) → (2, 3, 36) → (1, 6, 36),
(4, 6, 9) → (4, 3, 18) → (1, 12, 18) → (1, 6, 36).
Решение
а) Назовём пару чисел правильной, если одно из них делится на другое. заметим, что при каждой операции число правильных пар увеличивается. Когда все пары станут правильными, процесс прекратится. б) Пусть a1, ..., an – исходные числа. Нетрудно проверить, что при указанной операции ни одно из чисел b1 = (a1, ..., an),
b2 = ([a1, a2], [a1, a3], ..., [an–1, an]), b3 = ([a1, a2, a3], [a1, a2, a4], ..., [an–2, an–1, an]), ..., bn = [a1, a2, ..., an] не меняется.
Пусть в конце получились числа A1 ≤ ... ≤ An. Согласно а) каждое из этих чисел делится на предыдущее. Но тогда соответствующие числа B1 = b1, ..., bn = Bn совпадают с A1, ..., An.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь