Задача 41:

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

Решение:

Указание: Общее количество «втекающих» рек должно быть равно общему количеству «вытекающих» рек.

Задача 42:

В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый такой город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

Решение:

Пусть в столицу входит a дорог. Тогда общее число «входящих дорог равно 21 • 100 + a, а общее количество «выходящих» дорог не больше 20 • 100 + (100 – a). Поэтому 21 • 100 + a ≤ 20 • 100 + (100 – a), то есть 2a ≤ 0. Таким образом, a = 0.

Задача 43:

В некотором государстве каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

Решение:

Занумеруйте города и направьте движение от городов с меньшими номерами к городам с большими номерами.

Задача 44:

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

Решение:

Рассмотрите сначала вершины, соединенные с любой фиксированной вершиной A, затем – новые вершины, соединенные с ними и т.д. При этом ребра, соединяющие добавляемые вершины с уже рассмотренными, ориентируем в направлении к новым вершинам.

Задача 45:

В связном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия:

а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой;

б) для каждой вершины числа входящих и выходящих ребер равны.

Решение:

Рассмотрим эйлеров цикл, проходящий по всем ребрам графа, и ориентируем все ребра в соответствии с порядком прохождения цикла.

Задача 46:

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

Решение:

Докажите, что существует замкнутый путь вдоль стрелок, проходящий по каждому ребру ровно один раз.

Задача 47:

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

Решение:

Индукция по числу городов. База очевидна. Для доказательства индукционного перехода удалим сначала один из городов. В силу индукционного предположения есть город А с требуемым свойством. Вспомним теперь про удаленный город. Если в него ведет хотя бы одна дорога, то город А – искомый. В противном случае сам удаленный город удовлетворяет требуемому свойству.

Задача 48:

Несколько команд сыграли между собой круговой турнир по волейболу. Будем говорить, что команда А сильнее команды В, если либо А выиграла у В, либо существует команда С такая, что А выиграла у С, а С – у В.

а) Докажите, что есть команда, которая сильнее всех.

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

Решение:

Если существует команда, выигравшая и у команды-победительницы, и у всех команд, проигравших победителям, то у такой команды очков больше, чем у победителей турнира, что невозможно.

Задача 49:

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

Решение:

База – для трех городов. Для доказательства индукционного перехода удалите город, имеющий и входящие и выходящие дороги.

Задача 50:

20 команд сыграли круговой турнир по волейболу. Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, …, 19-я у 20-й.

Задача 51:

Какие-то две команды набрали в круговом волейбольном турнире одинаковое число очков. Докажите, что найдутся команды А, В и С такие, что А выиграла у В, В выиграла у С, а С выиграла у А.

Решение:

Пусть А и В набрали одинаковое количество очков, причем В выиграла у А. Тогда если для любой команды С, у которой выиграла А, выиграла и В, то у В должно быть очков больше, чем у А. Следовательно, есть команда С такая, что А выиграла у С, а С выиграла у В.

Задача 52:

В некотором государстве 101 город.

а) Каждый город соединен с каждым дорогой с односторонним движением, причем в каждый город входит 50 дорог и из каждого города выходит 50 дорог. Докажите, что из любого города можно доехать в любой другой, проехав не более, чем по двум дорогам;

б) Некоторые города соединены дорогами с односторонним движением, причем в каждый город входит 40 дорог и из каждого города выходит 40 дорог. Докажите, что из любого города можно добраться до любого другого, проехав не более, чем по трем дорогам.

Решение:

Пусть из города А нельзя доехать до города В. Рассмотрите города, в которые входят дороги из А, и города, из которых выходят дороги в В. б) Вычислите общее количество дорог, выходящих из первой группы городов. Заметьте, что этих дорог достаточно много для того, чтобы хотя бы одна из них кончалась в городе из второй группы.

Задача 53:

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

Решение:

Пусть удалено ребро между вершинами А и В. Выберем две произвольные вершины. Рассмотрите три случая: обе эти вершины не совпадают с А или В, одна из них совпадает с А или с В, эти вершины – А и В.