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

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

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

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

 Можно добавить U в конец строки, если она заканчивается на I. Например, MI превращается в MIU.
 Можно удвоить строку после M. Например, MIU превратится в MIUIU
 Можно заменить три буквы I, идущие подряд, на букву U. Так, MUIIIU можно превратить в MUUU.
 Можно убрать две буквы 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).

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

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

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

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

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

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

См. также 

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

Ссылки 

  Веб-интерфейс для игры в головоломку MU.
  Реализация MU Puzzle онлайн на JavaScript.

Примечания 

Логические игры
Страницы с непроверенными переводами