Задача 116037

Темы:    [ Турниры и турнирные таблицы ] [ Индукция (прочее) ] [ Числа Фибоначчи ]

Сложность: 4 Классы: 9,10,11

Условие

Автор: Шаповалов А.В.

55 боксёров участвовали в турнире по системе "проигравший выбывает". Бои шли последовательно. Известно, что у участников каждого боя число предыдущих побед отличалось не более чем на 1. Какое наибольшее число боёв мог провести победитель турнира?

Решение

  Докажем по индукции, что
    а) если победитель провёл не меньше n боёв, то число участников не меньше u_n+2;
    б) существует турнир с u_n+2 участниками, победитель которого провёл n боёв (u_k – числа Фибоначчи).

  База (n = 1,  u₃ = 2)  очевидна.
  Шаг индукции. а) Пусть победитель A выиграл последний бой у боксёра B. Оставшиеся поединки фактически распадаются на два турнира: один из них выиграл A, а второй – B. В первом турнире победитель A провёл не меньше  n – 1  боя, значит, число участников не меньше u_n+1. Во втором турнире победитель B провёл не меньше  n – 2  боёв, значит, число участников не меньше u_n. А в исходном турнире число участников не меньше  u_n+1 + u_n = u_n+2.

  б) Достаточно свести в заключительном поединке победителя турнира с u_n+1 участниками, выигравшего  n – 1  бой, и победителя турнира с u_n участниками, выигравшего  n – 2  боя.

  Поскольку  55 = u₁₀,  отсюда следует ответ.

Ответ

8 боёв.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	2010/2011
Номер	32
вариант
Вариант	осенний тур, базовый вариант, 10-11 кл.
Задача
Номер	5