.В группе из 25 человек любые двое имеют общего знакомого. Докажите,

Школьник  А   знаком  с  2-мя  школьниками   Б  и  В.   Б  и  В  должны быть тоже знакомы,  по другому  у  их  не  будет общего знакомого  А.

Поделим  знакомство   Б  и  В  с  остальными  22  школьниками.

Получится,  у  Б  и  В  по  13  знакомств   (2+11).  На двоих  2*13=26 знакомств.

Но,  чтоб  у  22  тоже  было  по  2 знакомства  они  обязаны перезнакомиться,  между собой   11  с  11  иными.

Школьник   А  и  22  школьника  имеют  по  2  знакомства  23*2= 46 знакомств.

Итого:   26 + 46= 72.

Каждое  знакомство  учитывалось  дважды ( А с Б  и  Б с А,  и  так  дальше).

Потому  методов  в  2  раза  меньше  72:2=36.

Представим воспитанников, как вершины графа, а их знакомства, как рёбра. По условию, в данном графе 25 вершин и любые две вершины соединены рёбрами с общей вершиной.

Докажем от неприятного. Пусть в графе не больше 35 рёбер. Допустим, что найдётся верхушка степени 1, тогда осмотрим её и вершину, соединённую с ней ребром. Они не имеют "общей верхушки", так как та, которая имеет ступень 1, не соединена больше ни с одной верхушкой. Если найдётся верхушка степени 0, условие не производится для неё точно. Допустим, что в графе не найдётся верхушки ступени 2, тогда ступень каждой верхушки не меньше 3, а суммарная ступень вершин не меньше 75. Но тогда в графе не меньше 38 рёбер. Значит, найдётся вершина ступени 2. Рассмотрим её. Она соединена с 2-мя верхушками (2 ребра). Любая из остальных 22 вершин должна иметь "общую верхушку" с этой, означает, любая из оставшихся вершин соединена ребром с одной из этих 2-ух (ещё 22 ребра) (это для того, чтоб "верхушка ступени 2" имела "общую вершину" с каждой из других). Осмотрим "эти две вершины", они должны иметь "общую вершину" с каждой из тех, с которыми соединены, означает, обязаны быть соединены и между собой (ещё одно ребро) (чтоб "верхушка ступени 2" и каждая из "этих двух вершин" имела "общую верхушку"). Так как ступень других вершин должна быть не меньше 2, то необходимо ещё не наименее 11 рёбер. Итого в графе не наименее 36 рёбер, что больше 35.

Эти 36 рёбер и есть разыскиваемые 36 методов избрать пару знакомых школьников.