Таблицы Брадиса

База индукции п 1 очевидна.

База индукции п 1 очевидна.

Элементы математики в задачах - Г. А. Мерзон

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

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

 

 

Задача 18*. В турнире без ничьих участвовало п команд. Каждая ко­манда сыграла с каждой ровно по одному разу. Докажите, что можно так занумеровать команды числами 1,. . . , п, что (і + 1)-я команда выиграла у і-й (для произвольного і = 1,..., п — 1).

Решение. Докажем утверждение задачи индукцией по п. База индук­ции п = 1 очевидна. Докажем шаг индукции. Пусть для п команд утверждение задачи выполнено. Рассмотрим произвольный турнир без ничьих между п + 1 командой. Заметим, что между первыми п командами произошел турнир без ничьих. Следовательно, их можно так занумеровать, что (і + 1)-я команда выиграла у і-й для каждого