|
|
 |
Условие
а) Есть неограниченный набор карточек со словами "abc", "bca", "cab". Из них составляют слово по такому правилу. В качестве начального слова выбирается любая карточка, а далее на каждом шаге к имеющемуся слову можно либо приклеить карточку слева или справа, либо разрезать слово в любом месте (между буквами) и вклеить карточку туда. Можно ли так составить палиндром?
б) Есть неограниченный набор красных карточек со словами "abc", "bca", "cab" и синих карточек со словами "cba", "acb", "bac". Из них по тем же правилам составили палиндром. Верно ли, что было использовано одинаковое количество красных и синих карточек?
Решение 1
Будем рассматривать всевозможные пары букв, входящих в слово. Назовём пары a...b, b...c и c...a хорошими, пары a...c, c...b и b...a – плохими.
а) Рассмотрим, как меняется число пар при добавлении одной карточки. Внутри этой карточки есть две хорошие и одна плохая пары. Поскольку вставляются три разных буквы "в одно место", то с каждой из имевшихся уже букв они образуют три новые пары: нейтральную, хорошую и плохую. Отсюда ясно, что число хороших пар всегда больше числа плохих. А в палиндроме их должно быть поровну из-за симметрии слова.
б) Как показано в а), каждая красная карточка увеличивает разность между числом хороших и плохих пар на единицу, а каждая синяя – уменьшает на единицу. Поскольку в палиндроме число хороших пар равно числу плохих, то и число красных карточек равно числу синих.
Решение 2
Рассмотрим на плоскости треугольную решётку из равных треугольников, раскрасим её в шахматном порядке, и выберем на ней стартовый узел O. Сопоставим буквам a, b, c сдвиг на единичные векторы в трёх направлениях (см. рис.) и будем рассматривать слово как описание пути, начинающегося в точке O. При этом любая из троек abc, bca, cab добавляет в путь обход вокруг тёмного треугольника, а из троек acb, cba, bac – вокруг светлого. Путь по-прежнему остаётся замкнутым, хотя некоторые рёбра, возможно, проходятся несколько раз. Если замкнутый путь оказался палиндромом, то первое и последнее ребро совпадают по направлению, но одно начинается в O, а другое в O заканчивается. Значит, соответствующие отрезки центрально симметричны относительно O. Точно так же центрально симметричны второй и предпоследний отрезки пути, и т. д. Так и весь путь оказывается центрально симметричным.
Пусть площадь каждого треугольника решетки равна 1. Тогда треугольники первого типа дают вклад 1, а второго типа – вклад –1. Значит, а) в палиндроме использованы карточки обоих типов, и б) карточек обоих типов поровну.
Ответ
а) Нельзя; б) верно.
Замечания
1. В решении 1 в п. а) можно рассматривать только пары соседних букв.
2. Баллы – 4 + 6.
