Сложность_3+

Задача 00013

от

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

Решение

Докажем, что
    а) от каждой зелёной площади можно доехать до синей;
    б) от синей площади можно доехать до любой зелёной.
  Условимся обозначать направление движения на улицах стрелками.

  а) Предположим, что от зелёной площади A1 нельзя доехать до синей площади. Поскольку уехать с площади A1 можно, то от неё, проехав по одной улице, мы доедем до зелёной площади A2. От площади A2 тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади A3, потом до A4 и т.д. Проехав по n улицам, мы вернёмся на площадь A1 и убедимся, что стрелки в городе расставлены так, как на рисунке. Но тогда на синюю площадь нельзя приехать, что противоречит условию.

  б) Изменим направления всех стрелок. Полученная схема движения тоже удовлетворяет условию. Поэтому, как показано в а), при этой расстановке стрелок от каждой зелёной площади можно доехать до синей. Но это означает, что при старой расстановке стрелок от синей площади можно было доехать до любой зелёной.

Задача 00005

от

Имеются две страны: Обычная и Зазеркалье. У каждого города в Обычной стране есть «двойник» в Зазеркалье, и наоборот. Однако если в Обычной стране какие-то два города соединены железной дорогой, то в Зазеркалье эти города не соединены, а каждые два несоединённых в Обычной стране города обязательно соединены железной дорогой в Зазеркалье. В Обычной стране девочка Алиса не может проехать из города A в город B, сделав менее двух пересадок. Доказать, что Алиса в Зазеркалье сможет проехать из любого города в любой другой, сделав не более двух пересадок.

Решение

Из условия следует, что города A и B в Обычной стране не соединены дорогой и что любой другой город в Обычной стране не соединён либо с A, либо с B. Значит, двойники A’ и B’ городов A и B в Зазеркалье соединены дорогой, а каждый другой город Зазеркалья соединён либо с A’, либо с B’. Следовательно, в Зазеркалье из каждого города можно доехать до одного из городов A’ и B’, затем при необходимости доехать до второго из них, а после доехать до любого другого города Зазеркалья. При этом требуется не более двух пересадок.

Задача 00004

от

Какое наименьшее число соединений требуется для организации проводной сети связи из 10 узлов, чтобы при выходе из строя любых двух узлов связи сохранялась возможность передачи информации между любыми двумя оставшимися (хотя бы по цепочке через другие узлы)?

Решение

  Оценка. Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трёх линий связи (если узел А соединён с двумя узлами В и С, то при выходе из строя узлов В и С узел А становится недоступным). Таким образом, всего линий связи должно быть не менее  10·3 : 2 = 15.
  Пример: каркас пятиугольной призмы (10 вершин – узлы, а рёбра – линии связи). Если вышли из строя два узла на одном пятиугольнике – основании призмы, то связь сохранится через другой пятиугольник. Если вышли из строя по одному узлу на разных пятиугольниках, то связь тоже сохранится.

Задача 00002

от

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

Решение

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