Задача 78708

Темы:    [ Процессы и операции ] [ Десятичная система счисления ]

Сложность: 3+ Классы: 8

Условие

С числом 123456789101112...9989991000 производится следующая операция: зачёркиваются две соседние цифры a и b (a стоит перед b) и на их место вставляется число a + 2b (можно в качестве a взять нуль, ``стоящий'' перед числом, а в качестве b — первую цифру числа). С полученным числом производится такая же операция и т.д. (Например, из числа 118 307 можно на первом шаге получить числа 218 307, 38 307, 117 307, 111 407, 11 837, 118 314.) Доказать, что таким способом можно получить число 1.

Решение

Мы будем доказывать утверждение задачи для любого числа  . Докажем для этого, что любое число можно уменьшить за несколько операций. Сначала докажем это для чисел, не меньших десяти. Рассмотрим первые две цифры  этого числа. Если  ≠ 19, то число можно уменьшить заменой первых двух цифр на число a + 2b. Если же  = 19, то число можно уменьшить последовательностью действий 19 29 20 2. Итак, любое число, не меньшее десяти, можно уменьшить. Осталось доказать, что из любого числа от двух до девяти можно получить единицу. Мы покажем, как последовательностью разрешённых операций из любого однозначного числа получить либо единицу, либо число, из которого мы уже умеем получать единицу.
5 10 1;
6 12 5;
3 6;
9 18 17 15 11 3;
7 14 9;
8 16 13 7;
4 8;
2 4.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	32
Год	1969
вариант
Класс	7
Тур	2
задача
Номер	2
олимпиада
Название	Московская математическая олимпиада
год
Номер	32
Год	1969
вариант
Класс	8
Тур	2
задача
Номер	1