В алфавите языка племени УЫУ две буквы В алфавите языка племени УЫУ две буквы: У и Ы,...

Question

В алфавите языка племени УЫУ две буквы
В алфавите языка племени УЫУ две буквы: У и Ы, причём этот язык обладает интересным свойством: если из слова выкинуть стоящие рядом буквы УЫ и УЫУУ, то смысл слова не изменится. Точно так же смысл слова не изменится при добавлении в любое место слова буквосочетаний УУ, ЫЫУУЫЫ и УЫЫУ. Можно ли утверждать, что слова УЫЫ и УЫУЫ имеют одинаковый смысл?

Answer 1

Забавная задачка.
Понятно, что если мы укажем последовательность применения указанных в условии свойств языка, такую, что из УЫЫ получим УЫУЫ, то задача будет решена.
Однако есть неприятный момент - генерируя всевозможные последовательности мы не имеем критерия конечности. Т. е. мы можем до бесконечности генерировать новые слова но так и не найдем ответ.
Попробуем с другого конца.

Теперь обращаем вниание на то, что все преобразования сохраняют четность количества букв. Мы можем всегда убрать или добавить только четное количество букв.
Это значит, что мы не можем из УЫЫ с 3 буквами получить УЫУЫ с четным числом букв.

Любопытно, что в этом языке Ы можно всегда заменить в любом месте на У с помощью преобразования:

Ы (добавляем слева и справа по УУ) УУЫУУ (выкидываем по первому правилу УЫУУ) У.

Используя правило удаления УЫ и доказанную эквивалентность букв, приходим к выводу, что все четные слова можно сократить до двухбуквенного (или пустого слова, если оно допустимо) . А все нечетные слова - до однобуквенного. Т. е. по сути язык может выразить всего два понятия. Поскольку все слова с четным количеством букв эквивалентны слову ЫЫ, а с нечетным - слову У. :)