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

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

Условие

Автор: Гришин А.

Имеется 20 бусинок десяти цветов, по две бусинки каждого цвета. Их как-то разложили в 10 коробок. Известно, что можно выбрать по бусинке из каждой коробки так, что все цвета будут представлены. Докажите, что число способов такого выбора есть ненулевая степень двойки.


Решение

  Ясно, что пустых коробок нет. Если имеется коробка, в которой находится только одна бусинка, то эта бусинка в любом случае должна быть выбрана. Уберём эту коробку с бусинкой, а также вторую бусинку того же цвета (из другой коробки). Останутся 18 бусинок, разложенные в 9 коробок. Количество способов выбрать по бусинке из каждой коробки осталось при этом тем же, что и в исходной задаче. Будем продолжать действовать так до тех пор, пока имеются коробки, содержащие всего одну бусинку. Пустых коробок при этом появиться не может, так как это привело бы к противоречию с условием задачи: в этом случае не существовало бы ни одного способа требуемого выбора.
  В результате останется 2n бусинок, разложенных в n коробок, по две в каждой. Будем выстраивать коробки в "цепочку" так, чтобы соседними были коробки, содержащие бусинки одного цвета (аналогично правилам игры в домино). Это можно делать до тех пор, пока цепочка не "замкнётся", то есть на концах не будут находиться коробки, содержащие бусинки одного цвета.
  Все коробки при этом разобьются на несколько цепочек (в частности, если коробка содержит две бусинки одного цвета, то цепочка состоит из неё одной). Ясно, что, выбрав одну из двух бусинок в любой из коробок, мы однозначно определяем выбор бусинок из других коробок той же цепочки и никак не ограничиваем выбор бусинок из коробок других цепочек. Поэтому общее количество способов требуемого выбора равно 2k, где k – количество получившихся цепочек. Осталось заметить, что хотя бы одна из цепочек у нас имеется, так как если в процессе отбрасывания одиночных бусинок мы уже отбросили девять цветов, то у нас осталось две бусинки одного цвета, лежащие в одной коробке.

Замечания

1. Для знатоков. Рассмотрим граф, вершинами которого являются коробки. Две вершины-коробки соединим ребром, если в них лежат бусинки одного цвета (если коробка содержит две бусинки одного цвета, возникает петля). Первая часть вышеизложенного решения состоит в стирании вершин степени 1 (пока это возможно). Вторую часть можно упростить: в полученном графе все вершины имеют степень 2, следовательно, граф распадается на циклы.

2. 7 баллов.

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

олимпиада
Название Турнир городов
Турнир
Дата 1998/1999
Номер 20
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 5
журнал
Название "Квант"
год
Год 1999
выпуск
Номер 3
Задача
Номер М1683
web-сайт
задача
web-сайт
задача

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

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