Обложка статьи «Сможете получить MU из MI, используя 4 правила?»

Сможете получить MU из MI, используя 4 правила?

Перевод задачи из книги «Algorithmic Puzzles», Anany Levitin, Maria Levitin

У вас есть строка MI. Выясните, можно ли получить из неё строку MU, используя только следующие правила:

  1. Если строка заканчивается на I, можно добавить в конец U. Пример: MI -> MIU.
  2. Можно удвоить часть строки после M, то есть изменить Mx на Mxx. Пример: MIU -> MIUIU.
  3. Можно заменить III на U. Пример: MUIIIU -> MUUU.
  4. Можно удалить UU. Пример: MUUU -> MU.

Нельзя.

Почему?

Если проанализировать правила, легко заметить, что у нас может быть всего одна M, которая уже есть в исходной строке. Это важно для понимания второго правила.

Теперь возьмём n — количество повторений I в строке. Для начальной строки MI n = 1, что не делится на 3. Только второе и третье правило могут изменять n, удваивая её или уменьшая на 3. Никакая из этих операций не может дать нам n, которая делится на 3 без остатка, если n не делилась на 3 до преобразований. Нам нужно получить строку MU, где n = 0 и как следствие делится на 3. Эта строка не может быть получена из MI, где n = 1 и не делится на 3.

Не смешно? А здесь смешно: @ithumor