Головоломка MU (англ. Mu Puzzle) — головоломка, которую создал Дуглас Хофштадтер. Упомянута в книге Гедель, Эшер, Бах. Ход головоломки - переписывание одной строки в другую по заданным правилам. Головоломка построена так, что она не имеет решения.
Правила головоломки Предположим, что есть символы M, I, и U, которые могут быть объединены, и при объединении из них получаются определенные строки. Головоломка звучит так:
«Пусть в начале есть строка MI. Преобразуйте её в строку MU, каждый выбирая один из возможных вариантов хода:Here: Chapter I.
Можно добавить 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.
Примечания
Категория:Логические игры Категория:Википедия:Страницы с непроверенными переводами