|
|
 |
Условие
В шахматном турнире каждый участник сыграл с каждым из остальных одну партию.
Доказать, что участников можно так занумеровать, что окажется, что ни один
участник не проиграл непосредственно за ним следующему.
Подсказка
Примените индукцию по числу участников турнира.
Решение
Применим индукцию по числу n участников турнира. База (два участника) очевидна.
Шаг индукции. Рассмотрим некоторый турнир с n + 1 участником. Выделим одного из участников – C, все встречи между остальными участниками образуют турнир для n участников. Согласно предположению индукции, этих n участников можно обозначить A1, A2, ..., An так, что участник Ai не проиграл Ai+1 (для всех i = 1, 2, ..., n – 1). Пусть m – наибольший номер, для которого участник С проиграл участникам A1, A2, ..., Am (если C выиграл у участника A1, то полагаем m = 0). Тогда C не проиграл участнику Am+1 (кроме случая m = n). Поэтому ряд A1, A2, ..., Am, C, Am+1, Am+2, ..., An удовлетворяет условию (если m = 0, то ряд начинается с С, если m = n, то ряд заканчивается на C).
