Действия с числом 9, как решить без перебора?

[Ktina]

К числу 9 применили (в некотором порядке) четыре операции: умножили на 3, разделили на 3, отняли 3 и прибавили 3. Какое наибольшее число могло при этом получиться?

Можно, разумеется, пребрать все 24 варианта, не так уж и долго.
Но ведь наверняка существует и эвристическое решение, как к нему притти?

[slavav]

Подряд складывать вычитать или делить умножать бесполезно. Общий результат всего выражения будет снова девяткой. Значит остаются восемь выражений.

-- 24.09.2017, 10:42 --

Пусть '-' крайняя операция. Тогда остальные группируются в '/+*' или '*+/'. Первая тройка даёт функцию $x + 9$. Вторая - $x + 1$. Лучший вариант для всего выражения $x + 6$.
Пусть '+' крайняя операция.Тогда остальные группируются в '/-*' или '*-/'. Первая тройка даёт функцию $x - 9$. Вторая - $x - 1$. Лучший вариант для всего выражения $x + 2$.
Побеждает 15 для '-/+*' или '/+*-'.

[CMTV]

Можно сократить количество вычислений с 24 вариантов до 12 (8 - с учтем эквивалентных операций), составив таблицу приоритета для 2 последовательных операций.

Таблица приоритета

Рассмотрим попарно все данные операции: сложение ($+$), вычитание ($-$), умножение ($\cdot$) и деление ($/$).

Пусть $a$ - исходная переменная (9), а $b$ и $c$ - переменные, которые используются в действиях (в нашем случае это 3).

$+$ и $\cdot$

$$ (a+b)\cdot c \ ? \ ac + b $$

Делим обе части на $c$ и получаем:

$$ a + b > a + \frac{b}{c} \Rightarrow (a+b)\cdot c > ac + b $$

Итого, к большему результату всегда будет приводить последовательность $ + \rightarrow \cdot $

$+$ и $-$

Тут все очевидно. Никакой разницы в порядке операций нет: $+ \sim -$

$-$ и $\cdot$

$$ (a-b)\cdot c \ ? \ ac - b $$

Делим обе части на $c$ и получаем:

$$ a - b < a - \frac{b}{c} \Rightarrow (a+b)\cdot c < ac - b $$

Итого, к большему результату всегда будет приводить последовательность $ \cdot \rightarrow - $

Деление

С делением для всех операций стрелки просто меняют направление.

Таблица

$$ \begin{matrix} + \rightarrow \cdot \\ \cdot \rightarrow - \\ + \sim - \\ \cdot \sim / \\ / \rightarrow + \\ - \rightarrow / \end{matrix} $$

Решение

Теперь мы можем предсказать наибольший результат сразу двух последовательных операций. Применим к исходным данным все шесть вариантов таблицы:

$$ \begin{matrix} + \rightarrow \cdot & 36 \\ \cdot \rightarrow - & 24 \\ + \sim - & 9 \\ \cdot \sim / & 9 \\ / \rightarrow + & 6 \\ - \rightarrow / & 2 \end{matrix} $$

Две операции уже исчерпаны. Осталось еще две и единственный правильный вариант последовательности их применения:

$$ \begin{matrix} + \rightarrow \cdot & 36 & - \rightarrow / & 11 \\ \cdot \rightarrow - & 24 & / \rightarrow + & 11 \\ + \sim - & 9 & \cdot \sim / & 9 \\ \cdot \sim / & 9 & +\sim - & 9 \\ / \rightarrow + & 6 & \cdot \rightarrow - & 15 \\ - \rightarrow / & 2 & + \rightarrow \cdot & 15 \end{matrix} $$

Получается, что наибольший результат: $15$.

В перспективе можно строить таблицы приоритета для большего количества операций...

-- 24.09.2017, 10:57 --

А вообще это интересная исследовательская задача. Максимально уменьшить число операций поиска наибольшего результата для исходного числа $a$, к которому $n$ раз последовательно применяются 4 разных действия...

[Ktina]

slavav
CMTV
Большое спасибо!

-- 24.09.2017, 11:07 --

CMTV в сообщении #1250216 писал(а):

-- 24.09.2017, 10:57 --

А вообще это интересная исследовательская задача. Максимально уменьшить число операций поиска наибольшего результата для исходного числа $a$, к которому $n$ раз последовательно применяются 4 разных действия...

И вправду, крайне интересная.

[deep down]

Делить нужно наименьшее число - иначе теряем часть от прибавления. Поэтому деление идёт сразу после вычитания.
Сложение и умножение увеличивают число, так что они будут после деления. Причём умножать выгоднее уже после сложения: $(x+3)\cdot 3$ против $3x+3$.
Получаем $(((9-3)/3)+3)\cdot 3 = 15$.

[grizzly]

deep down в сообщении #1250230 писал(а):

Делить нужно наименьшее число - иначе теряем часть от прибавления. Поэтому деление идёт сразу после вычитания.

По такой логике теряется одно из решений, упомянутых выше: $(9/3+3)\cdot 3-3= 15.$

[deep down]

Да, рассуждение только для поиска максимума. Плюс нужны дополнительные обоснования.

[Sinoid]

(Оффтоп)

Ktina в сообщении #1250196 писал(а):

притти?

прийти

[Ktina]

Sinoid в сообщении #1250294 писал(а):

(Оффтоп)

Ktina в сообщении #1250196 писал(а):

притти?

прийти

(Оффтоп)

У Достоевского - придти, у Тургенева - притти, у Толстого (а также современная форма) - прийти.

[arseniiv]

(Оффтоп)

And in English it’s pretty pretty.