В кружок ходит 10 человек, некоторые из которых между собой дружат. Может ли так быть, что в этом кружке один участник дружит с 9 другими, один участник — с 7 другими, один участник — с 6 другими, два участника — с 5 другими каждый, два участника — с 3 другими каждый, один участник — с 2 другими, два участника — с 1 другим каждый?
Введём граф, вершинами которого будут чипы, а ребро между вершинами проведём в том и только том случае, если соответствующие чипы соединены проводами.
Будем описывать граф в виде последовательности целых чисел (a1,
Заметим следующие два простых факта.
1. Пусть тогда если реализуема последовательность (a1,
Для реализации достаточно откинуть вершину с номером i.
2. Пусть тогда если реализуема последовательность (a1,
Действительно, если то вершина с номером i должна быть соединена со всеми остальными вершинами, поэтому достаточно откинуть её и все выходящие из неё рёбра.
Предположим противное и пусть последовательность (9, 7, 6, 5, 5, 3, 3, 2, 1, 1) реализуема. Пользуясь фактами 1 и 2 последовательно получаем, что тогда реализуемы и последовательности
но последовательность (2, 2), очевидно, не реализуема. Противоречие; значит, наше предположение неверно и последовательность (9, 8, 7, 5, 5, 3, 3, 3, 2, 1) не реализуема.
Ответ: нет, не может.
Приведем другое решение.
Аналогично первому решению введём граф. Заметим, что если (d1,
Действительно, все рёбра, выходящие из вершин с номерами от 1 до k делятся на два типа:
1) идущие в вершины с номерами от до n — таких не больше
2) идущие в вершины с номерами от 1 до k — таких не больше но каждое мы можем посчитать по два раза.
В задаче нас спрашивают, существует ли граф со степенями вершин (9, 7, 6, 5, 5, 3, 3, 2, 1, 1). Предположим, что он существует, и воспользуемся доказанным утверждением для первых 5 вершин:
противоречие.
Ответ: нет, не может.