№ 1. У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1; 2. умножь на 3. Первая из них увеличивает число на экране на 1, вторая — утраивает его. Программа для Утроителя — это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 16? Ответ обоснуйте.

Обозначим команду «прибавь 1» буквой А, а команду «умножь на 3» — буквой У.

1. Число 16 не делится на 3, поэтому последняя команда не может быть умножением на 3: перед ней пришлось бы получить число, равное 16/3.
2. Значит, последняя команда — А. До неё число должно быть 15.
3. Чтобы получить 15 из 3, последней командой на этом участке должно быть умножение на 3: перед ним нужно иметь 5. Число 5 из 3 можно получить только двумя прибавлениями: 3 → 4 → 5.

Единственная программа: А, А, У, А, У, А, то есть «прибавь 1», «прибавь 1», «умножь на 3», «прибавь 1», «умножь на 3», «прибавь 1».

Проверка: 3 → 4 → 5 → 15 → 16.

Ответ: 1 программа.