За­ме­тим, что если в клас­се ровно 1 че­ло­век, ко­то­рый по­здо­ро­вал­ся со всеми осталь­ны­ми, двое, тех, кто по­здо­ро­ва­лись со всеми осталь­ны­ми, но не друг с дру­гом, трое тех, кто по­здо­ро­вал­ся со всеми осталь­ны­ми, но не друг с дру­гом, ..., 8 че­ло­век, ко­то­рые по­жа­ли руку всем осталь­ны­ми, кроме как между собой, то будет ровно 556 ру­ко­по­жа­тий. Дей­стви­тель­но, во-пер­вых так что груп­пы та­ко­го раз­ме­ра воз­мож­ны. Bo-вто­рых, в каж­дой груп­пе каж­дый ребёнок сде­лал оди­на­ко­вое число ру­ко­по­жа­тий, а дети из раз­ных групп  — раз­ное. Но дети из одной груп­пы как раз не жали друг другу руки, а зна­чит усло­вие за­да­чи вы­пол­не­но. На­ко­нец, если по­стро­ить граф зна­комств на этих детях, то от пол­но­го графа его будет от­ли­чать от­сут­ствие внут­рен­них ребер в каж­дой груп­пе. То есть всего рёбер будет

До­ка­жем, что не может быть боль­ше k людей, со­вер­шив­ших ровно ру­ко­по­жа­тий. До­пу­стим об­рат­ное, то есть что име­ет­ся хотя бы че­ло­век, сде­лав­ший ровно ру­ко­по­жа­тий. Рас­смот­рим одно из них. Кроме него име­ет­ся всего 35 че­ло­век в клас­се, при этом он со­вер­шил ру­ко­по­жа­тий и есть ещё k че­ло­век, ко­то­рый сде­ла­ли ровно столь­ко же ру­ко­по­жа­тий. Тогда по прин­ци­пу Ди­ри­х­ле, так как найдётся че­ло­век, со­вер­шив­ший столь­ко же ру­ко­по­жа­тий, и ко­то­ро­му он жал руку, что про­ти­во­ре­чит усло­вию за­да­чи.

Из до­ка­зан­но­го утвер­жде­ния легко по­нять, что при­ведённый при­мер яв­ля­ет­ся оп­ти­маль­ным. До­ка­жем стро­го это утвер­жде­ние. Для этого упо­ря­до­чим всех школь­ни­ков по ко­ли­че­ству ру­ко­по­жа­тий, ко­то­рые они со­вер­ши­ли, и обо­зна­чим ко­ли­че­ство ру­ко­по­жа­тий пер­во­го из них (т. е. того, кто со­вер­шил мак­си­маль­ное ко­ли­че­ство ру­ко­по­жа­тий) за a₁, сле­ду­ю­ще­го по ко­ли­че­ству  — за a₂ и т. д. Тогда   — ко­ли­че­ства ру­ко­по­жа­тий, со­вершённые школь­ни­ка­ми на­ше­го клас­са. За­ме­тим, что про­сто по­то­му что боль­ше, чем 35 ру­ко­по­жа­тий со­вер­шить не­воз­мож­но. Причём, если то по утвер­жде­нию, до­ка­зан­но­му ранее. Далее по­лу­ча­ем, что a₂ и a₃ не боль­ше, чем 34, причём так как если бы a₃ было равно хотя бы 34, то и a₂, a₃ тоже были бы равны 34, а таких людей по до­ка­зан­но­му утвер­жде­нию может быть не более, чем 2. Ана­ло­гич­но можно до­ка­зать, что и и т. д. Тогда

Но сумма, сто­я­щая спра­ва, равна сумме сте­пе­ней вер­шин графа из при­ме­ра, при­ведённого выше, а она в два раза боль­ше ко­ли­че­ства рёбер в графе (так как сумма сте­пе­ней вер­шин графа равна удво­ен­но­му ко­ли­че­ству его рёбер).

Ответ: 546.