Question

Семеро друзей, разъезжаясь в отпуск, условились, что каждый из них пошлет открытки ровно троим из остальных. Может ли случиться, что каждый из них получит открытки именно от тех троих друзей, которым напишет сам?

Answer 1

Ответ:

нет не может

Пошаговое объяснение:

С теорией графов задача решается в одно действие: требуется построить граф с 7 вершинами (люди) , с ребрами, соединяющими те вершины, между которыми была переписка. Тогда степень каждой вершины = 3, сумма степеней вершин = 21, что противоречит лемме о рукопожатиях. Сумма степеней вершин всегда должна быть четна.