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

задан 11 Ноя '13 17:10

не достаточно ли составить сетку турнира по олимпийской системе и оказаться между вариантами 128 и 256 встречами?

(11 Ноя '13 17:25) vinger4
10|600 символов нужно символов осталось
3

Можно сначала решить своего обратную задачу: пусть победитель сыграл (то есть выиграл) $%n$% встреч; какое минимальное число участников могло быть в турнире? Обозначим это число через $%f(n)$%. Понятно, что $%f(1)=2$%: победитель должен был выиграть у кого-то один раз. При этом двух участников достаточно. Можно также для удобства считать, что $%f(0)=1$%: если участник турнира всего один, то он без игры объявляется победителем.

Пусть далее $%n > 1$%. Тогда в финале встречаются $%A$% и $%B$%, где $%A$% побеждает. До этого $%A$% одержал $%n-1$% победу, а $%B$% одержал по меньшей мере $%n-2$% победы. Можно считать, что до финала $%A$% и $%B$% участвовали как бы в двух независимых турнирах (общих участников там быть, очевидно, не могло). Поэтому в турнире с участием $%A$% было не меньше $%f(n-1)$% участника, а в турнире с участием $%B$% -- не меньше $%f(n-2)$% участников (здесь мы неявно ссылаемся на то, что функция $%f$% неубывающая, что очевидно). В итоге получается неравенство $%f(n)\ge f(n-1)+f(n-2)$%. Оно превращается в равенство, если рассуждать по индукции: организуем такие турниры с $%f(n-1)$% участниками и победителем $%A$%, где он выиграл $%n-1$% раз, а также независимо с $%B$%, победившем $%n-2$% раза, и далее пусть $%A$% выиграет у $%B$%. Это даёт пример турнира с $%f(n)$% участниками, то есть соответствующее значение достигается.

Тем самым, мы получаем рекуррентное соотношение для чисел Фибоначчи, и число $%377$% из условия -- как раз одно из них. Прямой подсчёт показывает, что $%f(12)=377$%. Мы уже располагаем примером турнира, где победитель одержал $%12$% побед, а $%13$% он одержать не мог, поскольку число $%f(13)$% заведомо больше $%377$%.

ссылка

отвечен 11 Ноя '13 19:31

А если 144 участника, то 10 ??

(4 Янв '14 19:28) doomsday

@doomsday: я изложил общий алгоритм, и он достаточен для получения ответа в Вашем случае. Если по решению что-то непонятно, я готов ответить на любые вопросы. А подставлять числа в готовые формулы, как я уже сказал, мне неинтересно.

(4 Янв '14 23:57) falcao
10|600 символов нужно символов осталось
0

Как он мог одержать 12 побед, если у участников каждой встречи количество предыдущих побед отличалось не более чем на одну. Получается максимум 1 победа, или нет?

ссылка

отвечен 22 Дек '13 23:44

@Radik: игрок одержал 12-ю победу в тот момент, когда у него было 11 побед в предыдущих играх, и обыграв того, у кого побед к этому моменту было 10. (Здесь сам процесс удобно представлять в виде "дерева", идя от простых схем к более сложным.) К моменту, когда между собой сразились победители, из турнира все остальные участники уже выбыли. Поэтому было много игр до этого момента, и много чьих-то побед -- в том числе тех, кто выбыл на предыдущих этапах.

(23 Дек '13 1:34) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,143

задан
11 Ноя '13 17:10

показан
2164 раза

обновлен
4 Янв '14 23:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru