математика - Задача про "манчестер юнайтед"

Задачи такого типа (преобразование слов) рассматриваются в ряде разделах математики -- например, в теории формальных языков. Но здесь задание дано как тренировочное, то есть имеется в виду, что решается оно "с нуля", и никакую теорию применять не нужно. К слову сказать, в этой области возникают иной раз такие задачи, у которых постановка очень проста и может быть осознана любым школьником, в то время как решение может быть очень сложным. Но к данной задаче это не относится.

Прежде всего, можно заметить, что буква M здесь везде стоит в начале, и её можно для простоты игнорировать. Тогда окажется, что имеется строка из букв I, U, с которой проделываются определённые преобразования. А именно: 1) I в конце строки разрешено заменять на IU; 2) строку можно удваивать, что есть X заменять на XX; 3) III можно заменять на U; 4) можно удалять UU.

Все эти преобразования по отношению к начальному слову отслеживаются. Проще всего поступить так. Рисуется картинка (граф), где строки изображаются в виде "узлов", а преобразования -- в виде "стрелок", идущих от одних узлов к другим. Рассмотрим для примера слово IU, а также то, что из него можно получить. Легко понять, что к этому слову применимо только удвоение, и ничего больше. Рисуем кружочек, вписываем в него строку IU, а затем рисуем другой кружочек, вписываем в него удвоенную строку, то есть IUIU, и от первого кружочка ко второму проводим стрелочку.

Далее ясно, что и строка IUIU не может быть преобразована никаким способом кроме удвоения. Отсюда следует, что из строки IU мы не можем получить ничего кроме $%(IU)^2$%, $%(IU)^4$%, $%(IU)^8$% и так далее. Здесь я использую стандартное для подобных случаев обозначение в виде степени, где $%X^n$% означает строку $%XX\ldots X$%, где $%X$% повторено $%n$% раз.

Из этих соображений можно увидеть, что из строки IU невозможно получить строку I, в то время как из I получается IU при помощи первого преобразования. Поэтому то отношение, которое здесь называется "равенством", не симметрично.

Указанный способ можно применить и к решению остальных пунктов, но это всё требует конкретного исследования. То есть надо представлять себе, как устроен описанный выше граф преобразований. Обычно бывает так: если что-то можно получить, то приводится конкретный пример. Если получить нельзя, то аргументация бывает несколько сложнее. Надо найти некоторый признак ("инвариант"), который не меняется при преобразованиях. И тогда, если я хочу доказать, что строку Y нельзя получить из строки X, то я вычисляю значения этого инварианта для X и для Y и убеждаюсь в том, что они разные.