Доброго времени суток, господа, столкнулся со следующей задачей:
"В Нечётнограде ровно
жителей. Их главное занятие — создавать различные клубы, и в некоторый момент это стало угрожать самому существованию города. Чтобы ограничить количество клубов, городской совет принял следующие правила, с виду безобидные.
1) Каждый клуб должен иметь нечётное количество членов.
2) Каждые два клуба должны иметь чётное количество общих членов.
Докажите следующую теорему. При соблюдении указанных правил невозможно создать больше чем
клубов, где
— количество жителей в городе."
Эта задачка из книжки Иржи Матоушека "33 миниатюры". Там приводится красивое решение этой задачи, используя линейную алгебру(вот те на). Однако, я бы очень сильно хотел решить эту задачу, используя исключительно теорию графов, но у меня это сделать не выходит. Самому пока получилось провести следующие рассуждения: Представим каждый клуб в виде кружка, а в этом кружке будут содержаться точки. Каждая точка есть не что иное как член, входящий в этот конкретный клуб. Коль скоро человек, входящий в один клуб, может входить и в другой, то будем соединять точки из кружков соответствующие одному и тому же человеку. Таким образом, между 2-мя точками есть ребро, если каждая из этих точек представляет одного и того же человека. Пользуясь такой конструкцией, можно сделать 2 вывода. Первый: Любая пара кружков может быть соединена только четным числом ребер. Второй: для любой пары кружков (для удобства обозначим их кружок 1 и кружок 2), коль скоро у них есть какое-то пересечение, есть человек, входящий в кружок 1, но не входящий в кружок 2, и наоборот. Дальше я не понимаю, что делать. Прошу помощи
