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