Наибольшее число боёв победителя: олимпиадная задача по математике для 9–11 классов

  Докажем по индукции, что

    а) если победитель провёл не меньше 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 боёв.