ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 65737
Условиеа) Есть неограниченный набор карточек со словами "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. Точно так же центрально симметричны второй и предпоследний отрезки пути, и т. д. Так и весь путь оказывается центрально симметричным. Подсчитаем ориентированную площадь, охватываемую замкнутой ломаной. Выберем O за начало координат. Тогда если AB и CD – центрально симметричные отрезки, а векторы AB и CD сонаправлены, то сумма ориентированных площадей OAB и OCD равна 0. Значит, и общая ориентированная площадь равна 0.Пусть площадь каждого треугольника решетки равна 1. Тогда треугольники первого типа дают вклад 1, а второго типа – вклад –1. Значит, а) в палиндроме использованы карточки обоих типов, и б) карточек обоих типов поровну. Ответа) Нельзя; б) верно. Замечания1. В решении 1 в п. а) можно рассматривать только пары соседних букв. 2. Баллы – 4 + 6. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|