ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 32101
Темы:    [ Процессы и операции ]
[ Мощность множества. Взаимно-однозначные отображения ]
[ Отношение эквивалентности. Классы эквивалентности ]
Сложность: 4
Классы: 8,9
В корзину
Прислать комментарий

Условие

В алфавите племени Мумбу-Юмбу есть лишь две буквы A и Б. Два разных слова обозначают одно и то же понятие, если одно из них может быть получено из другого с помощью следующих операций:
  1) в любом месте слова комбинацию букв АБА можно заменить на БАБ;
  2) из любого места можно выкидывать две одинаковые буквы, идущие подряд.
  а) Может ли дикарь племени сосчитать все пальцы на своей руке?
  б) А дни недели?


Решение

  б) Пусть мы имеем Мумбу-Юмбовское слово, состоящее не менее чем из четырёх букв. Если в слове есть две одинаковые буквы, идущие подряд, то их можно выкинуть. В противном случае в этом слове буквы чередуются. Значит, начало этого слова имеет вид либо АБАБ, либо БАБА. Начало АБАБ можно заменить на БАББ и далее на более короткое БА. Аналогично, БАБА заменяется на АБ. ,br>   Таким образом, любое слово, состоящее не менее чем из четырех букв можно сократить, то есть любое понятие можно выразить словом, состоящим не более чем из трёх букв.
  Слова АБА и БАБ по условию означают одно и то же, кроме того, слова ББ и АА также означают одно и то же, так оба они могут быть получены вычеркиванием пары одинаковых букв из слова ААББ.
  Поэтому в языке Мумбу-Юмбу может быть выражено не более шести различных понятий: А, Б, АА, АБ, БА и АБА. Поэтому дни недели дикарь племени сосчитать не сможет.

  а) Предположим, что дикарь, произнося любое слово, исполняет параллельно ритуальный танец следующим образом. На земле нарисован круг, разделённый на шесть равных секторов, один из которых отмечен. Обозначим три прямые, делящие круг, через a, b и c так, что выделенный сектор ограничен прямыми a и b. Дикарь становится сначала в отмеченный сектор и, произнося А, прыгает в сектор, симметричный тому, в котором он находится, относительно прямой a, а произнося Б – в сектор, симметричный относительно прямой b. Тогда если два слова означают одно и то же понятие, то в результате их произнесения, дикарь окажется в одном и том же секторе. Действительно, два прыжка через одну прямую оставят дикаря на месте, то есть выкидывание из слова двух одинаковых букв не повлияет на положение дикаря после танца. Комбинация букв АБА соответствует трем последовательным прыжкам через прямые a, b и снова a, что то же самое, что один прыжок через c. Тот же результат будет при последовательности прыжков, соответствующих комбинации БАБ. Поэтому замена АБА на БАБ тоже не влияет на место, в котором окажется дикарь после произнесения слова.

  Нетрудно проверить, что в результате произнесения слов А, Б, АА, АБ, БА и АБА дикарь окажется в различных секторах (см. рис.). Поэтому перечисленные шесть слов обозначают шесть различных понятий. Значит, для обозначения пальцев на руке понятий языка хватит.


Ответ

а) Сможет;  б) не сможет.

Замечания

Источник решения: книга В.О. Бугаенко "Турниры им. Ломоносова. Конкурсы по математике". МЦНМО-ЧеРо. 1998.

Источники и прецеденты использования

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 11
Дата 1988
задача
Номер 10

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .