Задача 005 — Задачи на Графы

В школе организовали $n(n>1)$ кружков. Оказалось, что для любых двух школьников есть кружок, в который ходит ровно один из них, а для любых трёх школьников есть либо кружок, в который ходят все трое, либо кружок, в который не ходит ни один из них. Какое наибольшее количество учеников может быть в этой школе?

Подсказка

Сопоставьте каждому ученику число в двоичной записи.

Решение

Ответ: $2^{n-1}$ .

Решение: Пронумеруем кружки и сопоставим каждому ученику $n$ -значное двоичное число, где в $k$ ом разряде стоит 0 , если ученик не ходит в этот кружок, и 1 , если ходит. Так как для любых двух школьников есть кружок, в который ходит ровно один из них, у разных школьников будут разные коды. Далее, разобьём коды на пары, где коды в каждой из пар не совпадают ни в одном разряде. Так как по условию у любых трёх сопоставленных школьникам кодов должен быть разряд, в котором все три совпадают, из каждой такой пары может быть использовано не больше одного кода. Поэтому школьников не больше, чем половина числа $n$ значных двоичных кодов, то есть не больше $2^{n-1}$ . Пример на $2^{n-1}$ : использованы в точности все коды, начинающиеся с 1 .