Решение головоломки Informatix.

Informatix – одна из интересных головоломок игры Puzzle Hunt Мельбурнского Университета 2013 года. Сюжет игры в том году был основан на персонажах комиксов про Астерикса и Обеликса, а каждая ее головоломка была связана с одним из жителей, населяющих деревню галлов. Informatix – один из этих жителей. Его головоломка была частью второго акта игры. Головоломке предшествовало изображение этого персонажа, а также его краткое описание: «Эксперт в области обработки и извлечения данных, Informatix всегда склонен слишком усложнять проблему».

Сама же головоломка представляла собой сеть, составленную из терминалов и принтеров. Первая страница задания содержала графическое представление этой сети. Вторая страница задания содержала таблицу, описывающую переходы между элементами сети. Каждая строка этой таблицы описывала работу одного из 14 терминалов. В таблице было 4 столбца. Первый столбец содержал названия терминалов. Второй — условие, которое следовало проверить для номера задания печати, когда оно поступало на терминал. Третий — операции над номером задания, которые следовало выполнить после проверки условия. Четвертый — элементы сети, в которые направлялось задание после обработки в терминале.

Помимо этого, вторая страница содержала описание работы сети при выполнении конкретной задачи.

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

    • из 14 уникальных заданий печати, инициированных через терминалы, 12 достигли принтера, и при этом их номер задания в итоге совпал с первоначальным;
    • оставшиеся 2 задания печати вернулись в свой исходный терминал, и снова номер задания в итоге совпал с первоначальным.
    • все (не возвращающие ошибку) операции маршрутизации были применены хотя бы один раз во время выполнения одного или нескольких заданий печати
    • номер задания печати всегда оставался целым числом от 1 до 99

Автором этой интересной головоломки является Эндрю Элви Прайс, который в 2013 году был Вице-Президентом, а затем и Президентом Сообщества Математики и Статистики Мельбурнского Университета (MUMS).

Очевидно, первоначальные номера заданий печати представляют собой просто ряд чисел от 1 до 14. Следовательно, для решения головоломки необходимо присвоить каждому из 14 терминалов уникальное число от 1 до 14 таким образом, чтобы результат работы сети совпал с описанным в задании. 

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

Для терминала SQUARE мы можем использовать только числа ряда, которые являются квадратами: 1, 4 и 9. При этом мы получим следующие результаты работы сети.

SQUARE(1), TRIANGULAR(1), ELECTRON(9), PRINTER(7), FAIL.
SQUARE(4), TRIANGULAR(2), PRINTER(11), FAIL.
SQUARE(9), TRIANGULAR(3), ELECTRON(11), PRINTER(9), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала SQUARE, это 9.

Для терминала PRONIC мы можем использовать только прямоугольные числа. В нашем ряду таковыми являются 2, 6 и 12.

PRONIC(2), 3MULTIPLE(20), #ERROR.

PRONIC(6), 3MULTIPLE(24), RESIDUE(8), 3MULTIPLE(18), RESIDUE(6), PRINTER(6), SUCCESS.

PRONIC(12), 3MULTIPLE(30), RESIDUE(10), HAPPY(3628800), FAIL.

Мы нашли единственный возможный номер задания печати для терминала PRONIC, это 6.

Для терминала 3MULTIPLE мы можем использовать только числа, кратные трем. Среди чисел ряда, которые мы еще не задействовали, таковыми являются 3 и 12.

3MULTIPLE(3), RESIDUE(1), HAPPY(1), SQUARE(4), TRIANGULAR(2), PRINTER(11), FAIL.

3MULTIPLE(12), RESIDUE(4), HAPPY(24), PRINTER(12), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала 3MULTIPLE, это 12.

Для терминала CATALAN мы можем использовать только числа Каталана. Таковыми в нашем ряду являются 1, 2, 5 и 14.

CATALAN(1), ABUNDANT(5), EVEN(35), PRINTER(10), FAIL.

CATALAN(2), ABUNDANT(6), EVEN(42), FACTORS(39), PRINTER(0), FAIL.

CATALAN(5), ABUNDANT(9), EVEN(63), PRINTER(2), FAIL.

CATALAN(14), ABUNDANT(18), PRONIC(72), 3MULTIPLE(90), RESIDUE(30), PRINTER(14), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала CATALAN, это 14.

Рассмотрим далее терминал TRIANGULAR, который проверяет, является ли число n треугольным. В случае невыполнения данного условия терминал прибавит к n 9 и передаст результат на PRINTER. Очевидно, в таком случае мы не получим первоначальное число, а это противоречит условиям задания. Значит, для этого терминала достаточно рассмотреть только треугольные числа ряда. Из оставшихся у нас чисел таковыми являются 1, 3 и 10.

TRIANGULAR(1), ELECTRON(9), PRINTER(7), FAIL.

TRIANGULAR(3), ELECTRON(11), PRINTER(9), FAIL.

TRIANGULAR(10), ELECTRON(18), DOUBLE(7), FACTORS(6), PRINTER(10), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала TRIANGULAR, это 10.

Рассмотрим теперь терминал HAPPY, который проверяет, подпадает ли число n под определение счастливого числа. При невыполнении условия терминал разделит n на 2 и передаст результат на PRINTER. Очевидно, при этом мы не получим первоначальное число. Значит, для этого терминала достаточно рассмотреть только имеющиеся у нас на данный момент счастливые числа: 1, 7 и 13.

HAPPY(1), SQUARE(4), TRIANGULAR(2), PRINTER(11), FAIL.

HAPPY(7), SQUARE(10), #ERROR.

HAPPY(13), SQUARE(16), TRIANGULAR(4), PRINTER(13), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала HAPPY, это 13.

Перейдем далее к терминалу EVEN, который проверяет, является ли число n четным. При невыполнении данного условия терминал найдет остаток от деления n на 9, прибавит к нему 2 и передаст результат на PRINTER. Очевидно, при этом мы не получим первоначальное число. Значит, для этого терминала достаточно рассмотреть только оставшиеся у нас четные числа: 2, 4 и 8. Легко установить, что число 2 не подходит для данного терминала.

EVEN(2), FACTORS(-1), FAIL.

Далее, оказывается, что последовательности для чисел 4 и 8 будут в определенный момент проходить через терминал REPDIGIT, и при этом n будет равно одному: REPDIGIT(1). Если предположить, что условие REPDIGIT при n = 1 не выполняется, то следующим этапом обеих последовательностей станет PRINTER(1), а значит для терминала EVEN не подходит ни одно из оставшихся чисел ряда, что противоречит условиям задания. Следовательно, условие термина REPDIGIT при n = 1 выполняется. А это возможно только в том случае, если номером задания печати для терминала REPDIGIT является 11.

REPDIGIT(11), PRINTER(11), SUCCESS.

Таким образом, мы нашли номер задания печати для терминала REPDIGIT, это 11. Теперь можно вернуться к терминалу EVEN.

EVEN(4), FACTORS(1), REPDIGIT(1), DOUBLE(4), FACTORS(3), CUBIC(4), EVEN(4), SUCCESS.

EVEN(8), FACTORS(5), CUBIC(6), EVEN(4), …, FAIL.

Мы нашли единственный возможный номер задания печати для терминала EVEN, это 4.

Рассмотрим далее терминал ELECTRON, который проверяет, соответствует ли число n количеству электронов в одной из оболочек атома. Если это условие не выполняется, то терминал отнимет от n 2 и передаст результат на PRINTER. Очевидно, в этом случае мы не получим первоначальное число. А значит, достаточно рассмотреть только те числа ряда, которые удовлетворяют условию терминала: 2 и 8.

ELECTRON(2), DOUBLE(2), FACTORS(1), REPDIGIT(1), DOUBLE(4), FACTORS(3), CUBIC(4), EVEN(4), …, FAIL.

ELECTRON(8), DOUBLE(8), FACTORS(7), CUBIC(8), DOUBLE(16), FACTORS(15), PRINTER(8), SUCCESS.

Мы нашли единственный возможный номер задания печати для терминала ELECTRON, это 8.

На данный момент у нас осталось 5 чисел ряда, которые мы еще не использовали: 1,2,3,5 и 7. Попробуем каждое из них для терминала ABUNDANT.

ABUNDANT(1), EVEN(7), PRINTER(9), FAIL.

ABUNDANT(2), EVEN(14), FACTORS(11), CUBIC(12), EVEN(12), FACTORS(9), PRINTER(2), SUCCESS.

ABUNDANT(3), EVEN(21), PRINTER(5), FAIL.

ABUNDANT(5), EVEN(35), PRINTER(10), FAIL.

ABUNDANT(7), EVEN(49), PRINTER(6), FAIL.

Мы нашли единственный возможный номер задания печати для терминала ABUNDANT, это 2.

У нас остались числа 1,3,5 и 7. Попробуем каждое из них для терминала FACTORS.

FACTORS(1), REPDIGIT(1), DOUBLE(4), PRINTER(1), SUCCESS.

FACTORS(3), CUBIC(4), EVEN(4), …, FAIL.

FACTORS(5), CUBIC(6), EVEN(4), …, FAIL.

FACTORS(7), CUBIC(8), DOUBLE(16), PRINTER(13), FAIL.

Мы нашли единственный возможный номер задания печати для терминала FACTORS, это 1.

У нас остались числа 3,5 и 7. Попробуем каждое из них для терминала RESIDUE. 

RESIDUE(3), PRINTER(5), FAIL.

RESIDUE(5), 3MULTIPLE(15), RESIDUE(5), SUCCESS.

RESIDUE(7), HAPPY(5040), FAIL.

Мы нашли единственный возможный номер задания печати для терминала RESIDUE, это 5.

У нас остались числа 3 и 7. Попробуем каждое из них для терминала DOUBLE.

DOUBLE(3), FACTORS(2), CUBIC(3), EVEN(1), PRINTER(3), SUCCESS.

DOUBLE(7), FACTORS(6), PRINTER(10), FAIL.

Мы нашли единственный возможный номер задания печати для терминала DOUBLE, это 3.

Теперь осталось только использовать число 7 для оставшегося терминала CUBIC. 

CUBIC(7), EVEN(5), RPINTER(7), SUCCESS.

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

FACTORS(1), REPDIGIT(1), DOUBLE(4), PRINTER(1).

ABUNDANT(2), EVEN(14), FACTORS(11), CUBIC(12), EVEN(12), FACTORS(9), PRINTER(2).

DOUBLE(3), FACTORS(2), CUBIC(3), EVEN(1), PRINTER(3).

EVEN(4), FACTORS(1), REPDIGIT(1), DOUBLE(4), FACTORS(3), CUBIC(4), EVEN(4).

RESIDUE(5), 3MULTIPLE(15), RESIDUE(5).

PRONIC(6), 3MULTIPLE(24), RESIDUE(8), 3MULTIPLE(18), RESIDUE(6), PRINTER(6).

CUBIC(7), EVEN(5), RPINTER(7).

ELECTRON(8), DOUBLE(8), FACTORS(7), CUBIC(8), DOUBLE(16), FACTORS(15), PRINTER(8).

SQUARE(9), TRIANGULAR(3), ELECTRON(11), PRINTER(9).

TRIANGULAR(10), ELECTRON(18), DOUBLE(7), FACTORS(6), PRINTER(10).

REPDIGIT(11), PRINTER(11).

3MULTIPLE(12), RESIDUE(4), HAPPY(24), PRINTER(12).

HAPPY(13), SQUARE(16), TRIANGULAR(4), PRINTER(13).

CATALAN(14), ABUNDANT(18), PRONIC(72), 3MULTIPLE(90), RESIDUE(30), PRINTER(14).

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

Если графически изобразить ход выполнения каждого задания печати, а затем повернуть и/или отразить диаграмму так, чтобы название его стартового терминала приобрело привычный для чтения вид, то можно разглядеть одну из букв английского алфавита. Вместе эти буквы, расположенные в соответствии с номерами их заданий печати, образуют понятие из области математики - LAMBDA CALCULUS (лямбда-исчисление). Оно и является ответом на задание.