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

Проект МЦНМО
при участии
школы 57
Задача 65737
Темы:    [ Процессы и операции ]
[ Инварианты и полуинварианты (прочее) ]
[ Центральная симметрия помогает решить задачу ]
[ Вспомогательная площадь. Площадь помогает решить задачу ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

а) Есть неограниченный набор карточек со словами "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.

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

олимпиада
Название Турнир городов
Турнир
Дата 2015/16
Номер 37
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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