В одной из вершин а) октаэдра; б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?
Решение
а) Пусть, A, B, C, A1, B1, C1 – вершины октаэдра, причём (A, A1), (B, B1) и (B, B1) – пары противоположных вершин. Тогда любая пара вершин, кроме этих трёх, соединяется ребром. Путь мухи может быть следующим: ABA1C1BCAC1B1CA1B1A (см. рис.)
б) В каждой из восьми вершин куба сходится по три ребра. Это означает, что степень каждой вершины полученного графа нечётна, значит, путешествие совершить невозможно.
Семиугольник разбит на выпуклые пяти- и шестиугольники, причём так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.
Решение
Рассмотрим полученную картинку как плоский граф. Так как из каждой вершины выходит не менее трёх рёбер, то E ≥ 3V/2. Подставив в формулу Эйлера, получим 2 = V – E + F ≤ 2E/3 – E + F = F – E/3, то есть E ≤ 3F – 6. Обозначим количество пятиугольников через a, количество шестиугольников через b. Заметим, что 5a + 6b + 7 = 2E ≤ 6F – 12 = 6(a + b + 1) – 12. Отсюда a ≥ 13.
Дан отрезок OA. Из конца отрезка A выходит 5 отрезков AB1, AB2, AB3, AB4, AB5. Из каждой точки Bi могут выходить ещё пять новых отрезков или ни одного нового отрезка и т.д. Может ли число свободных концов построенных отрезков равняться 1001? Под свободным концом отрезка понимаем точку, принадлежащую только одному отрезку (кроме точки O).
Решение
При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно 4k + 1. При k = 250 получаем нужное число свободных концов.
Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?
Решение
Оценка. Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трёх линий связи (если узел А соединён с двумя узлами В и С, то при выходе из строя узлов В и С узел А становится недоступным). Таким образом, всего линий связи должно быть не менее 10·3 : 2 = 15. Пример: каркас пятиугольной призмы (10 вершин – узлы, а рёбра – линии связи). Если вышли из строя два узла на одном пятиугольнике – основании призмы, то связь сохранится через другой пятиугольник. Если вышли из строя по одному узлу на разных пятиугольниках, то связь тоже сохранится.
Дано n точек, n > 4. Докажите, что можно соединить их стрелками так, чтобы из каждой точки в любую другую можно было попасть, пройдя либо по одной стрелке, либо по двум (каждые две точки можно соединить стрелкой только в одном направлении; идти по стрелке можно только в указанном на ней направлении).
Решение
Индукция по n. База. При n = 5 требуемый граф представлен на рис. слева. Шаг индукции. Рассмотрим n + 1 точку. Пусть n из них уже соединены – получился граф с n вершинами. Можно считать, что каждые две из этих n точек соединены стрелкой: иначе проведём все недостающие стрелки (направив их в любую сторону), условие тем более будет выполняться. Обозначим (n+1)-ю точку через C и рассмотрим два случая.
1) n чётно. Разобьём n точек на пары. Пусть {Ak, Bk} – одна из пар (1 ≤ k ≤ n/2) и из Ak идёт стрелка в Bk. Тогда проведём из C стрелку в Ak и из Bk проведём стрелку в C (рис. в центре). Так проделаем для каждой пары. Новый граф с n + 1 вершиной построен. Пусть X, Y – две любые различные его вершины. Если и X и Y не совпадают с C, то из X в Y можно пройти (не более чем за два «хода») по индукционному предположению. Пусть X или Y совпадает с C. Тогда другая из этих точек (Y или X) входит в какую-то пару из тех, на которые мы разбили первые n точек. Таким образом, X и Y – это какие-то две из трёх точек, изображенных на центральном рисунке. Глядя на этот рисунок, легко перебрать все возможные варианты и убедиться, что требование выполняется. 2) n нечётно. Выберем любую вершину A1. Она соединена стрелками со всеми остальными вершинами: A2, …, An. Из A1 выходят не менее чем две стрелки или в A1 входят не менее чем две стрелки (так как n > 4). Пусть из A1 выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A2, A3. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A1, A2, A3 – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.
