Question

Есть калькулятор, на котором можно делать с числом только две операции:

1) Умножить это число на 3 (получить 3*x)

2) Отнять это число от 2 (получить 2-x)

Например, если с числом 2 сделать последовательность операций 12, то мы сначала должны умножить его на 3 и получить 6, а потом отнять получившееся от 2, и в ответе мы получим -4. Напишите длину самой короткой последовательности, которая из числа 1 получает 231.

В ответ запишите число.

Answer 1

Ответ:

7

Объяснение:

Заметим, что две операции типа 2 не меняют число: если было число x, то после первого вычитания получим 2 - x, после второго 2 - (2 - x) = x.

Значит, в самой короткой последовательности, которая получает 231 из числа 1, нет двух операций типа 2 подряд.

Рассмотрим самую короткую последовательность, получающую 231. Идем с конца:

• 231 делится на 3. Если бы последней операцией было вычитание, то на предыдущем шаге было бы -229, это число не делилось бы на 3, и получилось бы, что в последовательности два вычитания подряд, чего быть не должно. Значит, последняя операция - умножение, число на предыдущем шаге - 231 / 3 = 77
• 77 не делится на 3, единственный вариант для предыдущего шага - получить из -75 путем вычитания
• -75 делится на 3, аналогично первому рассуждению это результат умножения числа -25 на 3
• -25 не делится на 3, оно получено из 27 путем вычитания
• 27 делится на 3, аналогично, получено из 9 умножением
• 9 делится на 3, аналогично, получено из 3 умножением
• 3 могло получиться из 1 за один шаг умножением на 3.

Итак, всё происходило так:

(1) 1 * 3 = 3

(1) 3 * 3 = 9

(1) 9 * 3 = 27

(2) 2 - 27 = -25

(1) -25 * 3 = -75

(2) 2 - (-75) = 77

(1) 77 * 3 = 231