Олимпиадная задача по теории множеств и комбинаторике для 8-10 классов: состав партячейки
Задача
В кооперативе из 11 человек имеется партячейка. На каждом собрании ячейки происходит либо приём одного члена в партию, либо исключение из партии одного человека. В партячейке не может быть меньше трёх человек. Возвращаться к какому-либо из прежних составов партячейки запрещено уставом. Может ли к какому-то моменту оказаться, что все варианты состава ячейки реализованы?
Решение
Количество членов ячейки после каждого собрания меняет чётность. Если бы удалось реализовать все возможные составы ячейки, то разность количеств возможных "чётных" и "нечётных" составов была бы равна ±1 или 0.
Количество всех нечётных подмножеств множества из 11 элементов равно количеству всех его чётных подмножеств (см. решение задачи 130711). Но из первого количества мы должны отбросить 11 одноэлементных подмножеств, а из второго – пустое множество и 55 пар. Таким образом, количество нечётных ячеек на 45 больше количества чётных, и реализовать все возможные составы ячейки не удастся.
Ответ
Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь