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