MU (головоломка)

Головоломка MU (англ. Mu Puzzle) — головоломка, которую создал Дуглас Хофштадтер. Упомянута в книге Гедель, Эшер, Бах. Ход головоломки - переписывание одной строки в другую по заданным правилам. Головоломка построена так, что она не имеет решения.

Предположим, что есть символы M, I, и U, которые могут быть объединены, и при объединении из них получаются определенные строки. Головоломка звучит так:

«Пусть в начале есть строка MI. Преобразуйте её в строку MU, каждый выбирая один из возможных вариантов хода:^[1][2]

1. Можно добавить U в конец строки, если она заканчивается на I. Например, MI превращается в MIU.
2. Можно удвоить строку после M. Например, MIU превратится в MIUIU
3. Можно заменить три буквы I, идущие подряд, на букву U. Так, MUIIIU можно превратить в MUUU.
4. Можно убрать две буквы U, идущие подряд. MUUU при этом ходе превращается в MU.»

Головоломка не имеет решения: невозможно изменить строку MI так, чтобы вместо неё появилась строка МU по данным правилам.

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

В этой головоломке можно посмотреть на общее количество букв I в строке.

Первый и четвертый варианты хода не меняют это число.

Второй вариант хода удваивает число букв I, третий способ уменьшает это число на 3. Докажем, что число букв I не делится на 3, если ходы начались со строки MI:

• В начале игры число букв I равно 1, а единица не делится на 3.
• Удваивая число, которое не делится на 3, вы не сможете сделать так, что оно будет делиться на 3.
• Вычитая 3 из числа, которое не делится на 3, вы не сможете сделать так, что число станет делиться на 3.

Таким образом, целевая строка MU не может быть достигнута, потому что в строке MU 0 букв I (т. е. нет ни одной буквы), а 0 - это число, которое делится на 3 (а по доказанному ранее число не должно делиться на 3).

На языке сравнений по модулю, число 2 в степени a не может быть сравнимо с нулём по модулю 3. (здесь число а показывает количество применений второй операции, так как операции 1, 3 и 4 не меняют остаток числа по модулю n).

${\displaystyle n\equiv 2^{a}\not \equiv 0{\pmod {3}}.\,}$

Глава XIX в книге Гедель, Эшер, Бах предлагает заменить буквы M, I и U цифрами. Каждая строка из букв M, I, U заменяется на число. M - это цифра 3, I - это 1 и U - это 0. (Например, строке MIUIU будет соответствовать число 31010.)

Начальная строка в головоломке (MI) сопоставлена числу 31.

Четыре правила преобразований, приведенные выше, можно записать так:

1. Обозначим имеющееся число как 10k + 1. Тогда после преобразования оно станет 10 × (10k + 1). Например, посмотрим на преобразование MI-MIU. При записи цифрами оно будет выглядеть как 31-310.
2. Обозначим имеющееся число как 3 × 10^m + n. Тогда результат преобразования будет равен 10^m × (3 × 10^m + n) + n. Например, число 310 станет выглядеть как 31010. (для букв это записывается как MIU - MIUIU)
3. Обозначим имеющееся число как k × 10^{m + 3} + 111 × 10^m + n. Тогда результат операции будет равен k × 10^{m + 1} + n. Например, 3111011 заменяется на 30011. Если это записать в виде букв, то получится: MIIIUII - MUUII.
4. Обозначим имеющееся число как k × 10^{m + 2} + n. Новое число будет иметь вид k × 10^m + n. Например, 30011 можно заменить на 311. (с точки зрения букв: MUUII - MII)

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

(Примечание: описание первого правила здесь несколько отличается от того, которое применялось в книге. В книге использовалась буква m. Но буква m уже используется в показателях степеней, поэтому здесь она заменена на букву k. Кроме того, здесь запись первого правила была несколько^{[уточнить]} изменена, чтобы она была более схожей с тремя другими правилами).^[3]

• Инвариант (математика)

• Hofstadter's MIU System  (неопр.). Дата обращения: 29 ноября 2016. Архивировано 4 марта 2016 года. Веб-интерфейс для игры в головоломку MU.
• MU Puzzle  (неопр.). Дата обращения: 13 мая 2018. Архивировано из оригинала 14 мая 2018 года. Реализация MU Puzzle онлайн на JavaScript.