Задача
С числом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.
Решение
Мы будем доказывать утверждение задачи для любого числа $\overline{a_1\dots a_n}$. Докажем для этого, что любое число можно уменьшить за несколько операций. Сначала докажем это для чисел, не меньших десяти. Рассмотрим первые две цифры $\overline{ab}$этого числа. Если $\overline{ab}$≠ 19, то число можно уменьшить заменой первых двух цифр на число a+ 2b. Если же $\overline{ab}$= 19, то число можно уменьшить последовательностью действий 19$\mapsto$29$\mapsto$20$\mapsto$2. Итак, любое число, не меньшее десяти, можно уменьшить. Осталось доказать, что из любого числа от двух до девяти можно получить единицу. Мы покажем, как последовательностью разрешённых операций из любого однозначного числа получить либо единицу, либо число, из которого мы уже умеем получать единицу. 5$\mapsto$10$\mapsto$1; 6$\mapsto$12$\mapsto$5; 3$\mapsto$6; 9$\mapsto$18$\mapsto$17$\mapsto$15$\mapsto$11$\mapsto$3; 7$\mapsto$14$\mapsto$9; 8$\mapsto$16$\mapsto$13$\mapsto$7; 4$\mapsto$8; 2$\mapsto$4.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь