Скрыть решение
Решение
Решим более общую задачу: пусть
l учеников занимаются в
n кружках,
l <
n. В доказательстве используем полную математическую индукцию. Пусть для любых
n" <
n, l" <
l, l" <
n" доказано, что найдутся два кружка, пересекающихся ровно по одному ученику.
Предположим, любые два из
n кружков либо не пересекаются, либо пересекаются ровно по двум ученикам. Так как учеников меньше, чем кружков, найдётся ученик, состоящий не менее чем в четырёх кружках. Обозначим его
A. Пусть в первом кружке с ним занимаются ученики
B и
C. Без ограничения общности предполагаем, что во втором кружке состоит также
B. Докажем, что в таком случае
B состоит и в третьем, и в четвёртом, и вообще в любом кружке, в котором занимается
A. Действительно, если бы
B не состоял в третьем кружке, то в нём состояли бы
C и
D — третий участник второго кружка, а четвёртый кружок должен был бы совпадать по составу с одним из первых трёх, что запрещено по условию. В силу симметрии, в любом кружке, в котором занимается
B, также занимается и
A. Пусть они вдвоём участвуют в
k кружках. Тогда ни
A, ни
B, ни остальные
k участников этих
k кружков не могут состоять в остальных
n –
k кружках. Но, по предположению индукции, среди этих
n –
k кружков, в которых состоят
l –
k – 2 учеников, найдутся два кружка, пересекающихся ровно по одному ученику. Противоречие.