Всем доброго времени суток! Сын (6 класс) готовится к олимпиаде. Задали задачку:

«Манчестер Юнайтед» («MU»)
Болельщики футбольного клуба «Манчестер Юнайтед» (МU) придумали такую игру. Рассмотрим строки состоящие из трех символов: M, I, и U, которые могут быть получены из строки MI, используя конечное число раз следующие правила преобразования: Правило 1. Добавить U в конец строки, если она заканчивается символом I. Например, можно изменить MI на MIU. Правило 2. Продублировать строку после M (т.е., изменить Mx на Mxx). Например, можно изменить MIU на MIUIU. Правило 3. Заменить III на U. Например, можно изменить MUIIIU на MUUU. Правило 4. Удалить UU. Например, можно изменить MUUU на MU. 1. Возможно ли, получить строку MU из MI, используя эти правила? 2. Опишите все трехсимвольные строки, которые можно получить из строки MI, используя правила 1¬–4. 3. Назовем две строки равными, если используя правила 1–4 из первой строки можно получить вторую строку. Верно ли, что если строка 1 равна строке 2, то строка 2 равна строке 1? Ответ обоснуйте. 4. Пусть в роли исходных строк могут выступать любая из строк MIU, MUI, MII, MUU. Есть ли среди указанных выше строк равные? Если есть, то их больше рассматривать не будем, а оставшиеся строки назовем прародителями. Как определить для строки, какая из исходных строк для нее послужила прародителем? 5. Предложите свои обобщения и направления исследования задачи.

Помогите, пожалуйста. Или хотя бы подскажите, из какого раздела математики это задание.

задан 26 Сен '13 21:19

10|600 символов нужно символов осталось
1

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

Прежде всего, можно заметить, что буква 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 и убеждаюсь в том, что они разные.

ссылка

отвечен 27 Сен '13 19:51

10|600 символов нужно символов осталось
0

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

ссылка

отвечен 26 Сен '13 23:40

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,997

задан
26 Сен '13 21:19

показан
630 раз

обновлен
27 Сен '13 19:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru