Всем доброго времени суток! Сын (6 класс) готовится к олимпиаде. Задали задачку: «Манчестер Юнайтед» («MU») Помогите, пожалуйста. Или хотя бы подскажите, из какого раздела математики это задание. задан 26 Сен '13 21:19 |
Задачи такого типа (преобразование слов) рассматриваются в ряде разделах математики -- например, в теории формальных языков. Но здесь задание дано как тренировочное, то есть имеется в виду, что решается оно "с нуля", и никакую теорию применять не нужно. К слову сказать, в этой области возникают иной раз такие задачи, у которых постановка очень проста и может быть осознана любым школьником, в то время как решение может быть очень сложным. Но к данной задаче это не относится. Прежде всего, можно заметить, что буква 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 falcao |
Сын (6 класс) - возможно я наговариваю на нынешних шестиклассников... но мне кажется, что для них такая задача дана на "тупенький" перебор... Вряд ли им излагали теорию про бинарные отношения толерантности и эквивалентности... Хотя пятый пункт задания - Предложите свои обобщения и направления исследования задачи - вводит в смятение ... отвечен 26 Сен '13 23:40 all_exist |