Натуральное число из четырёх четвертей

[Ktina]

В записи

$$\frac{1}{4}\quad\frac{1}{4}\quad\frac{1}{4}\quad\frac{1}{4}\quad$$

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

Найти наименьшее натуральное число, которое нельзя получить вышеописанным способом.

[gris]

То есть без радикалов, факториалов, целых частей?
Я чего-то и 4 не могу получить.

[Ktina]

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

То есть без радикалов, факториалов, целых частей?
Я чего-то и 4 не могу получить.

Я тоже.
Первые три дались крайне легко:

$$\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}=1$$

$$\frac{1}{4}:\frac{1}{4}+\frac{1}{4}:\frac{1}{4}=2$$

$$\left(\frac{1}{4}+\frac{1}{4}+\frac{1}{4}\right):\frac{1}{4}=3$$

-- 11.05.2013, 14:41 --

Причём двойку можно получить ещё и вот так.

[arseniiv]

Никто не собирается доказывать, что 4 непредставимо?

Такие записи соответствуют бинарным деревьям из трёх узлов, которые могут быть одной из операций. Их $3\times 3^4 = 243$, руками не перебрать.

[Legioner93]

arseniiv в сообщении #722443 писал(а):

Никто не собирается доказывать, что 4 непредставимо?

Писал год назад программулину для подобной задачи (общего вида). Перебирает все комбинации в виде ОПН (так легче намного). Только она лишь с целыми числами работает, да ещё и без унарного минуса. Не стояла задача универсальности, хотел лишь потренироваться с ОПН и побаловаться с оптимизацией. Сейчас попробую модифицировать.

arseniiv в сообщении #722443 писал(а):

Такие записи соответствуют бинарным деревьям из трёх узлов, которые могут быть одной из операций. Их $3\times 3^4 = 243$, руками не перебрать.

Что-то я вообще не понял вашу формулу, как она получается?
Если я ничего не забыл, то всего 4 варианта расстановки метазнака: (Формулы в ОПН, легко перевести в граф)
$ab+c+d+$
$ab+cd+$
$abc++d+$
$abc+d++$
Для каждой вариации каждый из трёх пустых знаков может принимать четыре значение. Итого $4\cdot 4^3$.

Это без унарного минуса, а с ним ещё больше.

[arseniiv]

Я думал, унарный минус нельзя (в задании-то не написано). А вот вариантов не 3, и даже не 4, а $C_3 = 5$ (3-е число Каталана), и я виноват в том, что пытался представить деревья в уме — в результате недопредставил два дерева. (И с формулой действительно напутал, спасибо.) Пятый вариант в ОПН будет $abcd+++$. Выходит $5 \cdot 4^3$.

Legioner93 в сообщении #722508 писал(а):

$ab+cd+$

Забыли плюсик в конце.

[Legioner93]

arseniiv
Спасибо за исправления.

Для единицы 37 вариантов, для двойки 5, для тройки 3 варианта. Четверку получить нельзя.
Из натуральных ещё можно получить 5, 8 и 16 (2,2 и 5 вариантов соответственно).
Это всё без унарных минусов, только бинарные +,-,*,/

-- Вс май 12, 2013 00:30:56 --

Если вдруг кто ещё поиграться захочет, вот исполняемый файл (Linux).

[arseniiv]

Это вам спасибо за первые исправления!

[TR63]

Ktina,
очень интересная задача.

(Оффтоп)

Я как её увидела, то у меня сразу возникла пара аналогий по её интерпретации (первая-периодичность радикалов; вторая,-если условие немного изменить,- теорема Абеля о несуществовании общей формулы для решения уравнений степени выше четвёртой).

Интересно, можно ли доказать логически существование ответа к Вашей задаче, чтобы решение перебором было гарантированным, а не типа "орёл"-"решка". (У меня есть идея, но она основанна на гипотезе.) В моей задаче, аналогичной Вашей (аналогия к ней- построение правильных многоугольников), перебор очень проблемен.

[gris]

Интересно, что если взять пять однопятых, то гораздо больше натуральных чисел получить можно.