Олимпиадная задача по комбинаторике и теории графов о бусинках для 8-9 классов

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

  В результате останется 2n бусинок, разложенных в n коробок, по две в каждой. Будем выстраивать коробки в "цепочку" так, чтобы соседними были коробки, содержащие бусинки одного цвета (аналогично правилам игры в домино). Это можно делать до тех пор, пока цепочка не "замкнётся", то есть на концах не будут находиться коробки, содержащие бусинки одного цвета.

  Все коробки при этом разобьются на несколько цепочек (в частности, если коробка содержит две бусинки одного цвета, то цепочка состоит из неё одной). Ясно, что, выбрав одну из двух бусинок в любой из коробок, мы однозначно определяем выбор бусинок из других коробок той же цепочки и никак не ограничиваем выбор бусинок из коробок других цепочек. Поэтому общее количество способов требуемого выбора равно 2^k, где k – количество получившихся цепочек. Осталось заметить, что хотя бы одна из цепочек у нас имеется, так как если в процессе отбрасывания одиночных бусинок мы уже отбросили девять цветов, то у нас осталось две бусинки одного цвета, лежащие в одной коробке.

Ответ задачи отсутствует