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

Пронумеруем кружки и сопоставим каждому ученику n - значное двоичное число, где в каждом разряде "0", если ученик не ходит в этот кружок и "1", если ходит. Так как, для любых двух учеников есть кружок, в который ходит ровно один из них, то у разных учеников будут разные коды.

Далее разобьем коды на пары, где коды в каждой из пар не совпадают ни в одном разряде. Так как по условию у любых трех, сопоставленных ученикам кодов, должен быть разряд, в котором все три совпадают, из каждой пары может быть использовано не более одного кода. Поэтому количество школьников не больше половины числа n-значных двоичных кодов, то есть не больше 2^ (n-1);

Докажем, то школьников будет ровно 2^ (n-1). Приведем пример:

Запишем все коды, начинающиеся с "1", тогда все ходят в первый кружок. Таких кодов 2^ (n - 1), поскольку первый член фиксирован, а каждый следующий выражается двумя способами "0" или "1".