Логические и комбинаторные рассуждения на Курчатове

Для каждой карточки рассмотрим другую, дополняющую её до полного набора(например, для карточки такой карточкой будет ). Ясно, что все карточки разбиваются на непересекающихся пар карточек, дополняющих друг друга до полного набора. Далее мы докажем, что в любом искомом наборе обязательно есть ровно по одной карточке из каждой такой пары, т. е.

Из условия следует, что максимум одна карточка из пары может быть среди выбранных, иначе уже есть полный набор. Теперь покажем, что из каждой пары должна быть хотя бы одна карточка. Рассмотрим пару дополняющих друг друга карточек, обозначим их и Предположим, что они обе не входят в выбранный набор. По условию при добавлении любой карточки из колоды найдётся полный набор. Добавив в набор мы найдём несколько карточек, дополняющих до полного набора, т. е. все цифры на этих карточках просто совпадают с множеством цифр на карточке . Аналогично, добавив карточку , мы найдём несколько карточек из набора, цифры на которых совпадают с множеством цифр на карточке Тогда объединим все эти карточки (которые совпадают с наборами на карточках и ) и получим полный набор, противоречие.

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