Задача 73675

Темы:    [ Десятичная система счисления ] [ Процессы и операции ] [ Обратный ход ] [ Полуинварианты ] [ Метод спуска ]

Сложность: 5+ Классы: 8,9,10

Условие

Автор: Толпыго А.К.

С натуральным числом (записываемым в десятичной системе) разрешено проделывать следующие операции:

А) приписать на конце цифру 4;

Б) приписать на конце цифру 0;

В) разделить на 2 (если число чётно).

Например, если с числом 4 проделаем последовательно операции В, В, А и Б, то получим число 140.

а) Из числа 4 получите число 1972.

б)* Докажите, что из числа 4 можно получить любое натуральное число.

Решение

a) Вместо того чтобы получить с помощью операций А, Б, В из числа 4 число 1972 , мы попробуем получить из числа 1972 число 4 с помощью обратных операций:

А ' ) вычеркивание цифры 4 в конце;

Б ' ) вычеркивание цифры 0 в конце;

В ' ) умножение числа на 2 .

При этом мы будем каждый раз, как только это возможно, применять операцию А ' или Б ' , чтобы по возможности на каждом шаге уменьшать наше число. Получим:

Ясно, что прочитав эту последовательность от конца к началу, мы получим нужный результат. (Операция Б ' здесь не используется.)

б) Докажем, что если с каждым числом N поступать так же, как мы поступали с числом 1972 (применять операцию А ' или Б ' , а если это не возможно– В ' ), то через несколько шагов мы придем к числу 4 .

Для этого достаточно доказать, что в получающейся мри этом последовательности каждое число через несколько шагов превратится в меньшее число (или в число 4 ). Отсюда будет следовать, что в конце концов мы обязательно придем к числу 4 , поскольку нельзя построить бесконечной последовательности натуральных чисел, в которой за каждым числом встречается меньшее.

Итак, убедимся, что каждое число за несколько операций А ' , Б ' , В ' можно уменьшить (или прийти из него к 4 ; этот последний случай мы дальше особо не оговариваем).

Если последняя цифра числа 0 или 4 , то после применения А ' или Б ' оно уменьшается по крайней мере в 10 раз.

Пусть последняя цифра числа отлична от 0 и 4 . В табл.1 показано, как меняется последняя цифра при применении В ' (операция В ' , т.е. увеличение числа в 2 раза, обозначена черной стрелкой, возможность применения А ' или Б ' – красной стрелкой):

Таблица1

Из этой таблицы видно, что если число N оканчивается на любую цифру, кроме 9 , то после не более чем трехкратного применения В ' , т.е. после увеличения не более, чем в 8 раз, к нему можно применить А ' или Б ' , т.е. уменьшить его по крайней мере в 10 раз. В итоге из N получится число, не превосходящее N<N .

Осталось рассмотреть лишь числа N , заканчивающиеся на 9 , которые до перехода к А ' увеличиваются в 16 раз. Заметим, что какой бы ни была предыдущая перед 9 цифра числа N , предпоследняя цифра числа

16N=16 (10a+9)=160a+144
всегда четна.

Если эта цифра не 8 , то 16N после А ' и не более чем двух операций В ' превратится снова в число с цифрой 0 или 4 на конце, которое мы можем уменьшить по крайней мере в 10 раз. В итоге из А ' получится число, не превосходящее

<N.

Остался случай, когда 16N оканчивается на 84 . Заметим, что какой бы ни была предыдущая перед 8 цифра этого числа, после операций

16N=... 84 10b+8 80b+64 8b+6
получим число, оканчивающееся на четную цифру.

Если эта цифра не 8 , то не более чем за две операции В мы получаем число с цифрой 0 или 4 на конце, отбрасываем ее и в итоге получаем из N число, не превосходящее N<N . Если же эта цифра– 8 , то за три операции В ' мы получаем число с четной предпоследней цифрой и из него (после А ' , не более чем трехкратного применения В ' и откидывания последней цифры)– число, не превосходящее

N=N<N.

Наше утверждение доказано, и задача решена.

Попробуйте, разобравшись в этом решении, перевести с помощью операций А, Б, В число 4 в 1249 (это одно из самых "неприятных" чисел).

Многие читатели, которые решали задачу M140 этим путем, не заметили или не до конца разобрали случай, когда число N оканчивается на 9 .

Значительно более короткое решение придумали А.Асташов (Львов), А.Арсасян (Камо), Г.Высоцкая (Красноярск). Они доказывают, что из любого четного числа можно с помощью операций А ' , Б ' , В ' получить меньшее четное число (ясно, что этого достаточно для решения задачи). Здесь достаточно рассмотреть 5 случаев:

1) 10k k ,

2) 10k+2 20k+4 2k ,

3) 10k+4 k 2k ,

4) 10k+6 20k+10+2 40k+20+4 4k+2 ,

5) 10k+8 20k+10+6 40k+30+2 80k+60+4 8k+6 .

Ниже мы публикуем список читателей, приславших нам правильные решения некоторых из задач M129-M140. По поводу задач M129, M130, M137, M140, условие которых состояло из нескольких пунктов, мы получили очень много писем с ответами на самые простые вопросы, но в список включены только те, кто решил задачи а) и б). (Впрочем, задачу M130б не решил никто.)

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

журнал
Название	"Квант"
год
Год	1972
выпуск
Номер	4
Задача
Номер	М140