Всесиб 2024, отборочный этап, 10 класс, задача 5
( баллов) Семь ленивых школьников решили посещать математический кружок в соответствиями с выработанными ими правилами приличия: (а) На каждом занятии должен присутствовать хотя бы один человек. (б) Для любых двух занятий множества присутствовавших на этих занятиях школьников должны различаться. (в) Для каждого и всех среди тех, кто присутствует в день с номером , обязательно должен быть хотя бы один школьник, присутствовавший в день с номером . Какое максимальное число занятий они смогут посетить, не нарушая этих правил?
Ответ
Ответ. .
Решение. Пример того, как можно посетить занятия: первый из них ходит на каждое занятие, а остальные шесть приходят на них всеми возможными множествами. Постоянное присутствие первого школьника при этом обеспечивает выполнение условий (а) и (в), а разные множества остальных в разные дни — выполнение условия (б). Общее число занятий в таком случае равно количеству всевозможных подмножеств во множестве из элементов, то есть .
Докажем, что больше занятий посетить не получится. Рассмотрим все подмножеств множества из семи школьников, разобьём их на пары {подмножество, дополнение к нему в }, которых будет . Если школьниками посещено больше занятий, то для некоторой пары оба её множества, назовём их и , реализовались, как множества посещений в дни с номерами и . Не умаляя общности, можно считать, что меньше . В таком случае, ввиду условия (в), хотя бы один школьник из множества должен был присутствовать и в день , что невозможно, так как множества и не пересекаются.