Задача 00012

а) В группе из четырёх человек, говорящих на разных языках, любые трое могут общаться (возможно, один переводит двум другим).
Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.
б) То же для группы из 100 человек.
в) То же для группы из 102 человек.

Решение

  а) Рассмотрим граф с четырьмя вершинами A, B, C, D, соответствующими людям, и соединим ребрами людей, знающих общий язык. Условие означает, что каждая тройка вершин соединена хотя бы двумя рёбрами. А доказать нужно, что есть два ребра без общих вершин. Пусть это неверно.
  Первый способ. Если в тройке  (A, B, C)  проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке  (B, C, D)  не больше одного ребра. Противоречие.
  Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее  4·2 : 2 = 4.  С другой стороны, каждому ребру соответствует отсутствующее «противоположное» ребро. Следовательно, рёбер не более трёх. Противоречие.

  в) Отделим двух человек, говорящих на одном языке, а остальных разобьём на четвёрки. Согласно а) каждую четвёрку можно разбить на две пары с общим языком.

Задача 00011

Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы – квадраты со стороной b, всего 9 кварталов). Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата – тоже улицы).

Решение

Всего есть 24 отрезка (улицы) длины b, по которым должен проехать асфальтоукладчик. К восьми перекрёсткам подходит нечётное число таких отрезков. По одному из отрезков, подходящему к такому перекрёстку, асфальтоукладчику придётся проехать дважды. Поскольку отрезок соединяет два перекрёстка, лишних проездов не меньше  8 : 2 = 4.  Итого весь путь составит не меньше  24b + 4b = 28b.
  Пример на рисунке показывает, что путь такой длины возможен.

Задача 00010

В одной из вершин  а) октаэдра;  б) куба сидит муха. Может ли она проползти по всем его рёбрам ровно по одному разу и возвратиться в исходную вершину?

Решение

а) Пусть, A, B, C, A1B1C1 – вершины октаэдра, причём  (A, A1),  (B, B1)  и  (B, B1) – пары противоположных вершин. Тогда любая пара вершин, кроме этих трёх, соединяется ребром. Путь мухи может быть следующим:  ABA1C1BCAC1B1CA1B1A  (см. рис.)

б) В каждой из восьми вершин куба сходится по три ребра. Это означает, что степень каждой вершины полученного графа нечётна, значит, путешествие совершить невозможно.

Задача 00009

Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?

Решение

Пусть разрезано k клеток. Рассмотрим граф, рёбрами которого являются половинки проведённых диагоналей, а вершинами – вершины и центры разрезанных клеток.
Поскольку граничные клетки доски, очевидно, разрезать нельзя, то в полученном графе не более 64 + k вершин и 4k рёбер. Согласно формуле Эйлера (64 + k) – 4k + 1 ≥ 2, то есть k ≤ 21.
Пример с 21 разрезанной клеткой см. на рисунке.

Задача 00006

Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток.
Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?

Решение

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а рёбрами – верёвочки. В этом графе нужно удалить как можно больше рёбер так, чтобы он остался связным. Будем убирать рёбра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число рёбер в нашем графе в этот момент. Количество вершин осталось тем же –  51·601 = 30651.  Число рёбер в дереве на единицу меньше (см. задачу 31098 б), то есть их 30650. Сначала же их было  601·50 + 600·51 = 60650.  Таким образом, можно удалить 30000 рёбер (но не более!).

Задача 00003

Дано 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 выходят не менее чем две стрелки (второй случай аналогичен) – в вершины A2A3. Остальные вершины разобьем на пары. Теперь соединим стрелками новую вершину с тройкой A1A2A3 – как показано на рис. справа, а со всеми парами – как показано на рис. в центре. Как и в случае а), легко доказать, что полученный граф удовлетворяет условию задачи.

Задача 00002

В стране Ориентация на всех дорогах введено одностороннее движение, причём из каждого города в любой другой можно добраться, проехав не более чем по двум дорогам. Одну дорогу закрыли на ремонт так, что из каждого города по-прежнему можно добраться до любого другого. Докажите, что для каждых двух городов это можно сделать, проехав не более чем по трём дорогам.

Решение

Пусть удалена дорога, ведущая из А в В. Рассмотрим произвольные два города C и D, отличные от А и В.
1) До удаления дороги АВ из C в D можно было проехать по одной или двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому удаление дороги АВ не повлияет на проезд из C в D.
2) После удаления дороги АВ по условию остался путь из A в B. Пусть E – последний город на этом пути перед B. Как показано выше, из C в E можно проехать не более чем по двум дорогам. Значит, из C в B можно проехать не более чем по трём дорогам.
Аналогично доказывается, что из А можно проехать в D не более чем по трём дорогам.
3) До удаления дороги АВ из A в E можно было не более чем по двум дорогам. Очевидно, ни одна из них не совпадает с АВ. Поэтому после удаления дороги АВ из А в В можно проехать не более чем по трём дорогам (по маршруту АEВ).

Задача 00001

На сторонах некоторого многоугольника расставлены стрелки.
Докажите, что число вершин, в которые входят две стрелки, равно числу вершин, из которых выходят две стрелки.

Решение

Пусть n – число сторон данного многоугольника, а k – число вершин, в которые входит по две стрелки. Всего стрелок – n, из них 2k стрелок входят в данные k вершин, остальные n – 2k стрелок входят еще в n – 2k вершин (в каждую – по одной). Остаётся n – k – (n – 2k) = k вершин, в которые не входит ни одной стрелки, то есть из которых выходит по две стрелки.