В 8A классе n учеников (n не меньше 2). Для них организованы кружки, каждый

В 8A классе n учеников (n не меньше 2). Для них организованы кружки, каждый из которых посещают хотя бы двое. Каждые два кружка, у которых есть хотя бы два общих ученика, отличаются по количеству участников. Докажите, что кружков не более n-12.

Обозначим через Nk - максмальное число кружков, в которые ходят ровно k ученика.
Из n учеников можно составить N0=Cn2=nn-12 пар.
1) Количество кружков, в которые ходят ровно два ученика, не должно быть больше N0 (в противном случае среди них будут кружки с одинаковым составом):
N2=N0=nn-12.
2) Максмальное число кружков, в которые ходят ровно три ученика . Из трех учеников каждого кружка можно составить C32=3 пары, поэтому число таких кружков N3 должно быть таким, чтобы число пар в этих кружках не превосходило N0:
C32N3≤N0⇒N3≤N0C32.
И так далее, для Nk получим:
Nk≤N0Ck2.
3) Следовательно, максимальное число кружков, в которые ходят от 2 до n учеников, не больше:
N=N2+N3+…+Nn=k=2nNk≤k=2nN0Ck2=N0k=2n1kk-12=nn-12k=2n2kk-1=
=nn-1k=2n1kk-1=nn-1k=1n-11kk+1=nn-1∙n-1n=n-12.
Таким образом:
N≤n-12.
Что и требовалось доказать.

. Из трех учеников каждого кружка можно составить C32=3 пары, поэтому число таких кружков N3 должно быть таким, чтобы число пар в этих кружках не превосходило N0:
C32N3≤N0⇒N3≤N0C32.
И так далее, для Nk получим:
Nk≤N0Ck2.
3) Следовательно, максимальное число кружков, в которые ходят от 2 до n учеников, не больше:
N=N2+N3+…+Nn=k=2nNk≤k=2nN0Ck2=N0k=2n1kk-12=nn-12k=2n2kk-1=
=nn-1k=2n1kk-1=nn-1k=1n-11kk+1=nn-1∙n-1n=n-12.
Таким образом:
N≤n-12.
Что и требовалось доказать.