Из какого наименьшего числа цифр всегда можно получить 100?

[Ktina]

gris в сообщении #1144304 писал(а):

...
Вообще, предлагаю обобщить задачу: Найти наименьшее $n$ такое, что между любыми $n$ ненулевых цифрами всегда можно так расставить скобки и знаки, что получится $100$.

[Yadryara]

Уточнять условие надо. Какие операции допустимы? В каких позициях разрешено ставить знаки?

И грамматику поправить. Видимо, не "ненулевых цифрами", а "ненулевыми цифрами".

[iifat]

Скорее, в каких позициях можно не ставить знаки. А то я возьмусь получить сотню из трёх цифр безо всяких знаков.

[Yadryara]

iifat в сообщении #1144396 писал(а):

А то я возьмусь получить сотню из трёх цифр безо всяких знаков.

Это если конкатенацию разрешить.

[Sphinx Pinastri]

Условие уточнить надо.

$\frac{\pi}{\pi} + ... + \frac{\pi}{\pi} = 100$

[gris]

Я так понял, что разрешаются только $),\,(,\,+,\,-,\,\cdot,\,/$.
Сотню надо получить из любой из $9^n$ комбинаций. Впрочем, это надо уточнить у ТС.
Sphinx Pinastri, если цифры одинаковые, то можно обойтись и двадцатью двумя штуками.
При разрешении склеивания — пятью. Но цифры могут быть разными.
Можно и так: Доказать, что для любого $n$ существует строка из $n$ ненулевых цифр, из которой нельзя получить сотню.

[Yadryara]

gris в сообщении #1144404 писал(а):

Я так понял, что разрешаются только $),\,(,\,+,\,-,\,\cdot,\,/$.

Да. Разрешать склеивание, возведение в степень и пр. — упрощать задачу.

Сложнее всего, видимо, со строкой, состоящей из одних единиц.

gris в сообщении #1144404 писал(а):

Можно и так: Доказать, что для любого $n$ существует строка из $n$ ненулевых цифр, из которой нельзя получить сотню.

Если и можно это доказать, то только для маленьких $n$.

[gris]

Co строкой из единиц проще всего. Начиная с $n=14$, имеем $(1+1)\cdot(1+1)\cdot(1+...+1)\cdot(1+...+1)\cdot 1\cdot 1\cdot ...\cdot 1=100$

Но это не является контрпримером ни к одной постановке.

[Yadryara]

gris в сообщении #1144417 писал(а):

Co строкой из единиц проще всего. Начиная с $n=5$, имеем $(111-11)\cdot 1\cdot 1\cdot ...\cdot 1=100$

Так написал же, что склеивание не разрешать, дабы не упрощать задачу.

[gris]

Поправился. Я думаю, что можно попробовать получать два и пять. Если удастся доказать, что начиная с некоторой длины можно получить два и пять, то задача будет решена. Даже один. Хотя это будет путь не к минимальной длине, а просто к опровержению обратной постановки.
Да что нам эта сотня. Можно, например, ноль получать из строк. Очевидно, что сложения и вычитания тут не хватит. Надо добавить умножение и скобки.
$1\cdot 2-3-4+5+6-7-8+9=0$

[Sender]

gris в сообщении #1144419 писал(а):

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

Для простоты можно начать с рассмотрения аналогичной задачи для систем счисления с меньшим основанием. К примеру, в троичной системе единицу можно получить всего из двух ненулевых цифр (если считать, что можно ставить знак перед первой цифрой):
$1\cdot 1=1_3,$
$-1+2=1_3,$
$2-1=1_3,$
$2 \div 2=1_3.$

[gris]

Интуитивно кажется, что из достаточно длинной строки можно получить, что угодно. Проходя по ней, убрать с помощью вычитания и деления сначала девятки, потом восьмёрки и прийти только к единичкам. Вот как в предыдущем сообщении. Ну а единички можно складывать. Я даже представил себе этакий автомат, обрабатывающий строки.
То есть, для любого натурального числа существует минимальная длина, сверх которой это число можно получить из любой строки. Ну а находить её значение как-то тоскливо

[Yadryara]

gris в сообщении #1144465 писал(а):

То есть, для любого натурального числа существует минимальная длина, сверх которой это число можно получить из любой строки.

Об этом и говорил. Количество способов возрастает очень быстро.

gris в сообщении #1144465 писал(а):

Ну а находить её значение как-то тоскливо

В нашем случае эта минимальная длина, скорее всего, $14$.

$(1+1)\cdot(1+1)\cdot (1+1+1+1+1)\cdot(1+1+1+1+1)=100$
$2\div1\cdot(1+1)\cdot (1+1+1+1+1)\cdot(1+1+1+1+1)=100$

И так далее...

Хотя, может кто и придумает решение покороче. От единичек многое зависит.

Либо не требовать $9^n$ вариантов...

[sergey1]

(Оффтоп)

https://vk.com/tchisla здесь обсуждается игра Tchisla, в рамках которой проводятся конкурсы по представлению чисел в виде выражений, составленных из одинаковых цифр и знаков математических операций. К сожалению, игра пока разработана лишь для ios.