Question

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

Answer 1

Ответ:

нет не может

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

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

Answer 2

Чтобы понять, может ли каждый из семи друзей получить открытки именно от тех троих друзей, которым он сам напишет, давайте рассмотрим эту ситуацию более подробно.

Допустим, у нас есть семь друзей: A, B, C, D, E, F и G. Пусть каждый из них отправит открытки троим другим друзьям. Например, A отправляет открытки B, C и D, и так далее. Это можно представить как ориентированный граф, где каждый друг соединен стрелкой с тремя другими друзьями.

Суть вашего вопроса заключается в том, может ли каждый друг получить открытки от тех троих друзей, которым он сам напишет. В таком случае, это означает, что в графе не должно быть циклов длиной 3. Поскольку семь друзей и каждый из них соединен с тремя другими друзьями, у нас есть 3 * 7 = 21 стрелка в графе.

Теперь, если бы граф не содержал циклов длиной 3, это означало бы, что каждый друг мог бы получить открытки именно от тех троих друзей, которым он сам напишет. Однако, чтобы убедиться, что это возможно, давайте проверим, может ли граф с 7 узлами и 21 стрелкой быть без циклов длиной 3.

Такой граф, в котором каждый узел соединен с тремя другими узлами, не может быть без циклов длиной 3. Это следует из леммы о рукопожатиях в графе. В этом случае, сумма степеней всех узлов (количество исходящих стрелок) равна удвоенному числу стрелок, то есть 42. Это означает, что сумма степеней всех узлов должна быть четным числом. Но в графе, в котором каждый узел связан с тремя другими, сумма степеней узлов будет 21 * 3 = 63, что является нечетным числом.

Таким образом, невозможно создать граф без циклов длиной 3 в данной ситуации, и, следовательно, невозможно, чтобы каждый из семи друзей получил открытки именно от тех троих друзей, которым он сам напишет.