ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98014
Темы:    [ Сочетания и размещения ]
[ Мощность множества. Взаимно-однозначные отображения ]
[ Четность и нечетность ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Фомин С.В.

В кооперативе из 11 человек имеется партячейка. На каждом собрании ячейки происходит либо приём одного члена в партию, либо исключение из партии одного человека. В партячейке не может быть меньше трёх человек. Возвращаться к какому-либо из прежних составов партячейки запрещено уставом. Может ли к какому-то моменту оказаться, что все варианты состава ячейки реализованы?

 

Решение

  Количество членов ячейки после каждого собрания меняет чётность. Если бы удалось реализовать все возможные составы ячейки, то разность количеств возможных "чётных" и "нечётных" составов была бы равна ±1 или 0.
  Количество всех нечётных подмножеств множества из 11 элементов равно количеству всех его чётных подмножеств (см. решение задачи 30711). Но из первого количества мы должны отбросить 11 одноэлементных подмножеств, а из второго – пустое множество и 55 пар. Таким образом, количество нечётных ячеек на 45 больше количества чётных, и реализовать все возможные составы ячейки не удастся.


Ответ

Не может.

Замечания

6 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант весенний тур, основной вариант, 9-10 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .