Задача 116233

Тема:    [ Примеры и контрпримеры. Конструкции ]

Сложность: 3 Классы: 11

Условие

Автор: Бородин П.А.

Верно ли, что любые 100 карточек, на которых написано по одной цифре 1, 2 или 3, встречающейся не более чем по 50 раз каждая, можно разложить в один ряд так, чтобы в нём не было фрагментов 11, 22, 33, 123 и 321?

Решение

Пусть имеется x карточек с цифрой 1, y карточек с цифрой 2 и z карточек с цифрой 3. Тогда x + y + z = 100, и так как

то искомый ряд можно сложить из фрагментов 21, затем из фрагментов 32, а затем из фрагментов 31. При этом карточка с цифрой 1 встретится ровно

раз, карточка с цифрой 2 — ровно y раз, а карточка с цифрой 3 — ровно z раз, причём запрещённые фрагменты в предложенном ряде не встретятся, даже если какое-либо из значений x, y или z равно 50.

Ответ

верно.

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

олимпиада
Название	Московская математическая олимпиада
год
Год	2011
Номер	74
класс
Класс	11
задача
Номер	2