Задача
В шахматном турнире каждый участник сыграл с каждым из остальных одну партию.
Доказать, что участников можно так занумеровать, что окажется, что ни один участник не проиграл непосредственно за ним следующему.
Решение
Применим индукцию по числу 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).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь