На доске написаны числа от 1 до 99. За один ход можно выбрать любые два числа и заменить их одним — их наибольшим общим делителем. Ходы делаются до тех пор, пока не останется одно число. Каким может быть это число?
Правильный ответ
Последнее число всегда равно 1. Инвариант: НОД всех оставшихся чисел. При замене $a$ и $b$ на НОД$(a,b)$ НОД всего набора не изменяется (так как НОД(НОД$(a,b)$, остальные) = НОД(a, b, остальные)). Начальный НОД(1, 2, 3, …, $99 = 1$). Значит на каждом шаге НОД всех чисел равен 1, и последнее число равно 1.
💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!