Олимпиадная задача: Докажите, что квадраты встречаются в последовательности чисел
Задача
На доску последовательно выписываются числа a1 = 1, a2, a3, ... по следующим правилам: an+1 = an – 2, если число an – 2 – натуральное и еще не выписано на доску, в противном случае an+1 = an + 3. Докажите, что все квадраты натуральных чисел появятся в этой последовательности при прибавлении 3 к предыдущему числу.
Решение
Докажем по индукции, что при n = 5m все числа от 1 до n выписаны на доску, причём a5m–4 = 5m – 4, a5m–3 = 5m – 1, a5m–2 = 5m – 3, a5m–1 = 5m,
a5m = 5m – 2.
База: 1 → 4 → 2 → 5 → 3.
Шаг индукции. Так как при n = 5m все числа от 1 до 5m уже выписаны и a5m = 5m – 2, то следующие пять чисел выглядят так: a5m+1 = 5m + 1,
a5m+2 = 5m + 4, a5m + 3 = 5m + 2, a5m + 4 = 5m + 5, a5m + 5 = 5m + 3.
Таким образом, числа, дающие при делении на 5 остатки 4, 1 и 0, появляются на доске после увеличения предыдущего числа на 3. Но только такие остатки и могут давать при делении на 5 квадраты натуральных чисел.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь