Ответ:

Обозначим команды: «+1» — прибавить 1, «×3» — умножить на 3.

Сжатое представление дерева результатов:

  • 0 команд: 0.
  • 1 команда: из 0: «+1» → 1, «×3» → 0.
  • 2 команды: из 1 получаем 2 и 3; из 0 получаем 1 и 0.
  • 3 команды: возможные результаты: 0, 1, 2, 3, 4, 6, 9.
  • 4 команды: возможные результаты: 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 18, 27.

Все числа, которые можно получить программами длиной не более четырёх команд:

\(\{0,1,2,3,4,5,6,7,9,10,12,18,27\}\).

На третьем уровне дерева, то есть после выполнения трёх команд, наибольшее значение получается при последовательности команд «×3, ×3, ×3»:

\(0\xrightarrow{\times3}0\xrightarrow{+1}1\xrightarrow{\times3}3\) — не даёт максимума, поэтому рассмотрим наибольшую выгодную последовательность:

\(0\xrightarrow{+1}1\xrightarrow{\times3}3\xrightarrow{\times3}9\).

Ответ: 9.