Четыре четвёрки
Четыре четверки — математическая головоломка по поиску простейшего математического выражения для каждого целого числа от 0 до некоторого максимума, используя лишь общие математические символы и четвёрки (никакие другие цифры не допускаются). Большинство версий «четырёх четверок» требует, чтобы каждое выражение содержало ровно четыре четверки, но некоторые вариации требуют, чтобы каждое выражение имело минимальное количество четверок.
Правила
Есть много вариаций этой головоломки. Их основное отличие в том, какие математические операции допускаются. Практически все вариации допускают по крайней мере сложение («+»), вычитание («−»), умножение («×»), деление («÷»), и скобки, а также объединения (например, запись «44» допускается). Большинство также позволяют факториал («!»), возведение в степень (например, «444»), десятичную точку («.») и квадратный корень («√»), хотя иногда квадратный корень специально исключен на том основании, что подразумевается «2» для квадратного корня. Другие операции разрешены в некоторых вариантах, включая субфакториал («!» перед числом: !4 равно 9), праймориал («#» после числа, например, 4# равно 6), «()» или же «черта над» (последовательность бесконечно повторяющихся цифр), корень любой степени, гамма-функции (Γ (), где Γ (х) = (х — 1)!) и процент («%»). Таким образом, 4/4% = 100 и Γ (4) = 6. Черта имеет такое значение:
Как правило, использование логарифмов не разрешается, поскольку существует тривиальный способ выразить любое число при его использовании. Пол Бурк, цитируя Бена Рудьяка-Гоулда, описал использование натуральных логарифмов (ln ()) для представления любого натурального числа n:
Возможны дополнительные варианты (как правило, с другим названием): с заменой набора цифр («4, 4, 4, 4») другим, скажем, годом рождения кого-то. Например, вариант с использованием «1975» потребует в выражении для каждого числа использовать только одну 1, одну 9, одну 7, и одну 5.
Решения
Вот набор решений из четырех четверок для чисел от 0 до 20 с использованием типовых правил. Некоторые альтернативные решения также перечислены здесь, хотя на самом деле существует еще много правильных решений.
0 = 4 ÷ 4 × 4 − 4 = 44 −44 1 = 4 ÷ 4 + 4 − 4 = 44 ÷44 2 = 4 −(4 + 4)÷ 4 = (44 + 4) ÷ 4! 3 = (4 × 4 − 4)÷ 4 = (4 + 4 + 4)÷ 4 4 = 4 + 4 ×(4 − 4) = −44 + 4! + 4! 5 = (4 × 4 + 4)÷ 4 = (44 − 4!)÷ 4 6 = 4 +(4 + 4)÷ 4 = 4.4 + 4 ×.4 7 = 4 + 4 − 4 ÷ 4 = 44 ÷ 4 − 4 8 = 4 ÷ 4 × 4 + 4 = 4.4 −.4 + 4 9 = 4 ÷ 4 + 4 + 4 = 44 ÷ 4 −√4 10 = 4 + 4 + 4 −√4 = (44 − 4) ÷ 4 11 = 4 ÷ 4 + 4 ÷.4 = 44 ÷√4 ÷√4 12 = 4 ×(4 − 4 ÷ 4) = (44 + 4) ÷ 4 13 = (4 −.4)÷.4 + 4 = 44 ÷ 4 +√4 14 = 4 ×(4 −.4)−.4 = 4 + 4 + 4 +√4 15 = 4 × 4 − 4 ÷ 4 = 44 ÷ 4 + 4 16 = 4 × 4 + 4 − 4 = (44 − 4) ×.4 17 = 4 × 4 + 4 ÷ 4 = (44 + 4!)÷ 4 18 = 4 × 4 + 4 −√4 = (44 ÷√4) − 4 19 = 4!− 4 −(4 ÷ 4) = (4 + 4 −.4) ÷.4 20 = 4 ×(4 + 4 ÷ 4) = (44 − 4) ÷√4
Есть также много других способов представления.
Следует обратить внимание на запись некоторых десятичных дробей. Так, «0.4», как правило, пишется как «.4». Это потому, что «0» — это цифра, а в этой головоломке могут быть использованы только цифры «4».
Заданное число, как правило, имеют несколько возможных решений, и любое решение, которое отвечает правилам, является приемлемым. Некоторые варианты предпочитают «наименьшее» число операций, или предпочитают некоторые операции другим. Другие просто предпочитают «интересные» решения, то есть удивительный способ достижения цели. Самое большое число, которое может быть записано с помощью только четырёх четвёрок, четырёх арифметических действий и степеней, равно 4444, которое примерно равно 1010154.
Некоторые числа, такие как 113 и 123, особенно трудно решить в рамках типичных правил. Для 113, Уилер предлагает Γ (Γ (4)) — (4 + 4!) / 4. Для 123, Уилер предполагает, выражение:
Использование процента («%») допускает решения для гораздо большего количества чисел, например, 113 = (√4 + (√4 + 4!)%) ÷ (√4)%. Поэтому не во всех вариантах он разрешён.
Впервые в печати описание головоломки даётся в книге «Математические эссе и развлечения» (У. У. Роуз Болл, 1892). В этой книге «четыре четвёрки» описываются как «традиционное развлечение».
Алгоритмические проблемы
Эта проблема и её обобщения (например, «пять пятерок» и «шесть шестерок», как показано ниже) может быть решена путём простого алгоритма. Для решения необходимо построение хеш-таблицы, которая отображает числа в строки. В этих таблицах ключи-числа могут быть представлены как некоторые допустимые комбинации операторов и символов d, обозначающих, например, четвёрку, и значения, являющиеся строками, которые содержат актуальные формулы. Существует одна таблица для каждого номера n вхождений d. Например, когда d = 4, хеш-таблицы для двух вхождений d будут содержать пары, вроде данной: ключ-значение 8 и строка 4 + 4, а для трёх вхождений — например, пары, вроде такой: ключ-значение 2 строку (4 +4) / 4 (строки выделены жирным шрифтом). Задача сводится при этом к рекурсивному вычислению этих хеш-таблиц с повышеием n, начиная с n = 1 и продолжая до, например, n = 4. Таблицы для n = 1 и n = 2 являются тривиальными, поскольку они содержат примитивные элементы. Например, при n = 1 получим:
T[4] := "4"; T[4/10] := ".4"; T[4/9] := ".(4)";
а при n = 2:
T[44] := "44";.
В настоящее время существует два способа, при которых новые записи могут быть сгенерированы как комбинации уже существующих, используя бинарные операторы, либо путём применения факториала или квадратного корня (которые не используют дополнительные экземпляры d). В первом случае рассматриваются и перебираются все пары подвыражений, которые используют в общей сложности случаи n d. Например, когда n=4, , мы хотели бы проверить (a, b) с a, содержащим один экземпляр d, и три b, или a, содержащий два экземпляра d и b с 2 d. Мы бы тогда смогли ввести a+b, a-b, b-a, a*b, a/b, b/a) в хеш-таблицу, включая скобки, для n=4. Тут множества A и B содержат соответственно a и b, вычисленные рекурсивно, на основе n=1 и n=2. Мемоизация используется для того, чтобы каждое значение хеш-таблицы вычисляется только один раз.
Во втором случае (факториалы и корни) обработка идёт с помощью вспомогательной функции, которая вызывается каждый раз, когда значение V записывается. Эта функция вычисляет вложенные факториалы и корни V до некоторой максимальной глубины, ограниченной числами.
Последний этап алгоритма заключается в итерации ключа от таблицы для требуемого значения n, а также получения и сортировки тех ключей, которые являются целыми числами. Этот алгоритм был использован для расчета примеров «пять пятерок» и «шесть шестерок», приведенных ниже. Каждый раз выбиралась более компактная формула (в смысле количества символов в соответствующие значения), когда ключ появлялся более одного раза.
Выписка из решения задачи с пятью пятерками
139 = ((((5+(5/5)))!/5)-5) 140 = (.5*(5+(5*55))) 141 = ((5)!+((5+(5+.5))/.5)) 142 = ((5)!+((55/.5)/5)) 143 = ((((5+(5/5)))!-5)/5) 144 = ((((55/5)-5))!/5) 145 = ((5*(5+(5*5)))-5) 146 = ((5)!+((5/5)+(5*5))) 147 = ((5)!+((.5*55)-.5)) 148 = ((5)!+(.5+(.5*55))) 149 = (5+(((5+(5/5)))!/5))
Выписка из решения задачи с шестью шестёрками
В приведенной ниже таблице, запись .6… представляет значение 6/9 или 2/3 (периодической дроби 6).
241 = ((.6+((6+6)*(6+6)))/.6) 242 = ((6*(6+(6*6)))-(6/.6)) 243 = (6+((6*(.6*66))-.6)) 244 = (.6...*(6+(6*(66-6)))) 245 = ((((6)!+((6)!+66))/6)-6) 246 = (66+(6*((6*6)-6))) 247 = (66+((6+((6)!/.6...))/6)) 248 = (6*(6+(6*(6-(.6.../6))))) 249 = (.6+(6*(6+((6*6)-.6)))) 250 = (((6*(6*6))-66)/.6) 251 = ((6*(6+(6*6)))-(6/6)) 252 = (66+(66+((6)!/6))) 253 = ((6/6)+(6*(6+(6*6)))) 254 = ((.6...*((6*66)-6))-6) 255 = ((((6*6)+66)/.6)/.6...) 256 = (6*(6*(6-(6/(.6-6))))) 257 = (6+(((6)!+((6)!+66))/6)) 258 = ((6)!-(66+(6*66))) 259 = ((((6*6)+((6)!/6))-.6)/.6) 260 = ((66+(((6)!/.6)/6))-6)