Турнир имени Ломоносова. Задача про рукопожатия

В классе учится 36 человек. Каждое утро, заходя в класс, некоторые в знак приветствия жмут друг другу руки, причём никто никому не жмёт руку за день более одного раза. В один из дней оказалось, что никакие два ученика, которые сделали одинаковое число рукопожатий, не жали руку друг другу. Какое максимальное число рукопожатий могло быть сделано в этот день?

Задача была предложена 9 марта 2020 года на заключительном туре Турнира имени Ломоносова, который проводится для 11-классников.

Воспользуемся "жадным" алгоритмом.
Пожать руку всем (35 одноклассникам) мог только один, потому что если бы нашёлся ещё один такой школьник, то он не смог бы пожать руку первому и, таким образом, пожал бы руки не все одноклассникам.

Пожать руки 34 одноклассникам могли максимум двое школьников, ведь если бы их было хотя бы трое, то каждый из них не пожал бы руку минимум двоим одноклассникам и, таким образом, сделал бы не более 33 рукопожатий.

Аналогично
33 одноклассникам могли пожать руки не более трёх школьников;
32 одноклассникам могли пожать руки не более четырёх школьников;
31 однокласснику могли пожать руки не более пяти школьников;
30 одноклассникам могли пожать руки не более шести школьников;
29 одноклассникам могли пожать руки не более семи школьников;
28 одноклассникам могли пожать руки не более восьми школьников.

Получается как раз 1+2+3+4+5+6+7+8=36 школьников.

Сколько в таком случае они сделали рукопожатий? Так как каждое пожатие считается два раза, то
(35+2*34+3*33+4*32+5*31+6*30+7*29+8*28)/2=546.

Осталось построить пример, показывающий, что такая ситуация возможна. В общем-то, он строится из оценки.
Разобьём школьников на группы в 1, 2, 3, 4, 5, 6, 7, 8 человек. Пусть школьники пожмут руки всем тем, кто с ними не в одной группе. Получается как раз нужный пример!