Сложность_3

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

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

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

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

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

При проведении пяти отрезков из конца отрезка появляются 5 новых свободных концов и пропадает один старый. В результате число свободных концов увеличивается на 4. Поэтому если пятёрки отрезков проведены k раз, то число свободных концов равно  4k + 1.  При  k = 250  получаем нужное число свободных концов.