На доске написано число 1. За один ход можно взять любое число x, имеющееся на доске, и записать на доску одно из чисел 3x + 1 или x+6. Найдите наибольшее число, не превосходящее 300, которое может быть записано на доске.
Arnfinn изменил статус на опубликованный
1 Ответ
Решение:
Докажем, что любое записанное на доску число даёт остаток 1 при делении на 3. Действительно, изначальное число 1 удовлетворяет утверждению. Пусть на доске находятся несколько чисел, каждое из которых даёт остаток 1. Поскольку 3x и 6 делятся на 3, то 3x + 1 даёт остаток 1 при делении на 3, а x+6 — такой же остаток, что число x, то есть снова 1.
Таким образом, на доске не могли появиться числа 300 = 3 · 100 и 299 = 3 · 99 + 2. Покажем, как получить 298:
1→3·1+1=4→4+6=10→…→4+6·49=298.
Ответ: 298
Arnfinn изменил статус на опубликованный