Решение задачи 367

Условие:

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

Решение:

Каждому школьника сопоставим двоичный код длины n: на позиции i стоит единица, если школьник ходит на кружок и 0 иначе.

Оценка:

Из первого условия следует, что у каждых двух школьников различаются коды. Значит, школьников не больше 2ⁿ. Разобьем все двоичные коды длины n на пары: в каждой паре находятся противоположные коды, другими если у одного кода на i-ой позиции стоит 0, то у другого на позиции i стоит 1, и наоборот. Таких пар 2ⁿ⁻¹. Второе условие задачи на языке кодов выглядит так: для любых трех кодов найдется хотя бы один разряд, на котором они совпадают. Отсюда следует, что и для любых двух кодов найдется разряд, на котором они совпадают. Если школьников больше чем 2ⁿ⁻¹, то по принципу Дирихле найдутся два школьника с противоположными кодом, а значит, второе условие задачи заведомо не выполнено. Значит школьников не больше чем 2ⁿ⁻¹.

Пример:

Приведем пример на 2ⁿ⁻¹ школьников. Рассмотрим все двоичные коды длины n, начинающиеся на 1. Таких кодов 2ⁿ⁻¹, каждому школьнику присвоим один из этих кодов. Тогда любые три школьника одновременно ходят на первый кружок и для любых двух школьников есть кружок, в который ходит ровно один из них.

Ответ: 2ⁿ⁻¹.