Задача 498 В турнире участвовали 55 теннисистов....

slava191

17.01.2014

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

f(k) - максимальное количество игр, которые сыграл победитель турнира с k участниками.
Тогда f(2)=1,f(3)=2,f(4)=2 - победитель не может выиграть последовательно у остальных троих, т.к. нарушается условие задачи (количество предыдущих побед отличалось не более чем на одну).
f(5)=3. Аналогично f(5)<4, а f(5)=3, когда теннисисты разбиваются на две группы по 2 и 3 человека.

Пусть k=6,7?f(k)=3, т.к. Победитель и Финалист выиграли в своих группах, поэтому если f(k)=4, значит Финалист провел минимум 2 игры ? в его группе минимум 3 человека, значит в группе Победителя максимум 4 человека, но тогда до Финала тот провел 2 игры, противоречие.
f(8)=4, т.к. тогда можно разбить на две группы по 5 и 3 человека, при этом f(5)=3,f(3)=2,|3?2|?1.

Аналогично, если k=9,10,11,12, то f(k)=4. Если f(k)=5, то Финалист провел в своей группе минимум 3 игры ? в этой группе минимум 5 человек ? в группе Победителя максимум 7 человек, что противоречит тому, что он провел 4 игры в своей группе.
f(13)=5, разбиваем на две группы по 8 и 5 человек.
Аналогичными рассуждениями получаем, что f(k)=5 при k=13,...,20.
f(21)=6,f(k)=6 при k=22,...,33
f(34)=7,f(k)=7 при k=35,...,54
f(55)=8,f(k)=8 при k=56,...,88

Ответ: 8