Решение 1. Назовем весом рассадки количество пар знакомых между собой людей во всех аудиториях. Найдем рассадку наименьшего веса. Пусть в ней нашелся человек, у которого в его аудитории хотя бы знакомых, тогда заметим, что по принципу Дирихле хотя бы в одной из аудиторий количество его знакомых не более Пересадим его в эту аудиторию. Заметим, что вес рассадки уменьшился хотя бы на Значит выбранная рассадка была не наименьшего веса. Противоречие с предположением.

Решение 2. Переведем задачу на язык графов: пусть дан граф, в котором степень каждой вершины не превосходит требуется распределить вершины по трем группам так, чтобы степень каждой вершины внутри своей группы не превосходила Распределим вершины по трем группам произвольно. Предположим, что все же существует вершина, степень которой внутри ее группы По принципу Дирихле, в одной из двух оставшихся групп эта вершина имеет степень Переместим ее в эту группу. Ясно, что после этого действия количество ребер, проходящих внутри трех групп, уменьшилось хотя бы на Будем повторять это действие до тех пор, пока степень каждой вершины в своей группе не станет Описанный процесс конечен, так как с каждым его шагом уменьшается количество ребер, проведенных внутри трех групп, при этом изначально в графе было проведено конечное количество ребер.