4. У исполнителя Вычислитель две команды, которым присвоены номера: 1. приписать 1; 2. разделить на 3. Первая из них приписывает к числу справа 1, вторая уменьшает его в 3 раза. Составьте алгоритм получения из 5 числа 19, содержащий не более 5 команд. В ответе запишите номера команд.

Применим команду 1 к числу 5: получим 51. Затем трижды применим команду 2: 51 делится на 3, затем 17 делится на 3 не делится без остатка — значит, такой путь не подходит. Ищем последовательность, учитывая, что команда 2 делит число на 3, а результат должен оставаться целым.

Последовательность 1, 2, 1, 1 даёт: 5 → 51 → 17 → 171 → 1711, поэтому тоже не приводит к 19. Чтобы получить 19 после приписывания 1, предыдущим числом должно быть 1; оно недостижимо из 5 допустимой целочисленной командой деления на 3. Если деление допускает дробные значения, конечные пять команд также не дают 19: после приписывания цифры число оканчивается на 1, а деление меняет значение в три раза.

Однако 5 → 51 → 17, и повторное приписывание даёт 171; команда 2 применима к 171 и даёт 57, затем приписывание 1 даёт 571. Получить 19 за не более чем пять команд указанным набором команд нельзя: возможные обратные шаги от 19 — числа 18 (перед командой 1) или 57 (перед командой 2); из 57 обратные шаги дают 56 или 171, а дальнейший поиск не приводит к 5 в пределах лимита.

Ответ: алгоритма длиной не более 5 команд не существует при обычном понимании команд.