ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109683
Темы:    [ Алгоритм Евклида ]
[ Процессы и операции ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

На доске написаны два различных натуральных числа a и b. Меньшее из них стирают, и вместо него пишут число    (которое может уже оказаться нецелым). С полученной парой чисел делают ту же операцию и т.д. Докажите, что в некоторый момент на доске окажутся два равных натуральных числа.


Решение

Одновременно с операциями на доске будем вести запись в тетради. Но вместо каждого числа x, появляющегося на доске, будем писать в тетради число ab/x (a и b – исходные числа). Когда на доске пара чисел  (x, y),  где  x > y,  заменяется на пару     в тетради происходит замена     то есть, как в алгоритме Евклида, большее число заменяется на разность. Следовательно, на каком-то шаге мы запишем в тетрадь пару чисел, равных  (a, b).  В это же время оба числа на доске станут равными  

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 5
Класс
Класс 9
задача
Номер 98.5.9.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .