Разделы 
Дополнительно
Задача по математике - 3701
2019-06-16 
Теннисная федерация присвоила всем входящим в нее теннисистам квалификационные номера: сильнейшему - первый номер, следующему по силе - второй и т. д. Известно, что во встречах теннисистов, квалификационные номера которых различаются более, чем на 2, всегда побеждает спортсмен с меньшим номером. Турнир, в котором участвуют 1024 сильнейших теннисиста, проводится по олимпийской системе: участники очередного тура разбиваются по жребию на пары и в следующий тур выходит победитель в каждой паре, так что число участников после каждого тура уменьшается вдвое. Таким образом, после десятого тура будет выявлен победитель. Какой наибольший номер может он иметь?
Решение:
Так как теннисист с номером $k$ может проиграть (не считая более сильных) только $(k + 1)$-му и $(k + 2)$-му теннисисту, то после каждого тура номер сильнейшего из победителей не может увеличиться больше чем на 2. Таким образом, номер победителя всего турнира не больше 21. Покажем, однако, что и 21-й теннисист победителем стать не мог. Для этого после первого тура должны были бы выбыть 1-й и 2-й, проиграв 3-ему и 4-му (иначе номер победителя - меньше 21), во втором должны выбыть 3-й и 4-й, а 5-й и 6-й - победить их и т. д. вплоть до 9 тура, в котором 19-й и 20-й должны победить 17-го и 18-го. Таким образом, 21-й теннисист не попадает в финал, где встречаются двое.
Осталось привести пример турнира, в котором побеждает 20-й игрок. Для этого всех теннисистов разобьем на две группы по 512 человек. В первую группу включим 19-го, 20-го и еще 610 более слабых игроков. Турнир в группе организуем так, чтобы выиграл 20-й (это, очевидно, можно сделать). Во вторую группу отнесем 1-го, 2-го, 18-го и оставшихся более слабых игроков и организуем турнир так, чтобы победил 18-й. Это можно сделать, организовав турнир так, как это описано выше: в первом туре 3-й и 4-й выигрывают у 1-го и 2-го, во втором 5-й и 6-й - у 3-го и 4-го и т. д. до восьмого тура, когда 17-й и 18-й выигрывают у 15-го и 16-го, после чего в девятом туре 18-й выигрывает у 17-го. В финале встречаются 20-й и 18-й и, следовательно, 20-й может победить.
Можно доказать по индукции, что в случае $2^n$ игроков наибольший номер победителя - $2n$.
Ответ: наибольший возможный номер победителя - 20.
Теннисная федерация присвоила всем входящим в нее теннисистам квалификационные номера: сильнейшему - первый номер, следующему по силе - второй и т. д. Известно, что во встречах теннисистов, квалификационные номера которых различаются более, чем на 2, всегда побеждает спортсмен с меньшим номером. Турнир, в котором участвуют 1024 сильнейших теннисиста, проводится по олимпийской системе: участники очередного тура разбиваются по жребию на пары и в следующий тур выходит победитель в каждой паре, так что число участников после каждого тура уменьшается вдвое. Таким образом, после десятого тура будет выявлен победитель. Какой наибольший номер может он иметь?
Решение:
Так как теннисист с номером $k$ может проиграть (не считая более сильных) только $(k + 1)$-му и $(k + 2)$-му теннисисту, то после каждого тура номер сильнейшего из победителей не может увеличиться больше чем на 2. Таким образом, номер победителя всего турнира не больше 21. Покажем, однако, что и 21-й теннисист победителем стать не мог. Для этого после первого тура должны были бы выбыть 1-й и 2-й, проиграв 3-ему и 4-му (иначе номер победителя - меньше 21), во втором должны выбыть 3-й и 4-й, а 5-й и 6-й - победить их и т. д. вплоть до 9 тура, в котором 19-й и 20-й должны победить 17-го и 18-го. Таким образом, 21-й теннисист не попадает в финал, где встречаются двое.
Осталось привести пример турнира, в котором побеждает 20-й игрок. Для этого всех теннисистов разобьем на две группы по 512 человек. В первую группу включим 19-го, 20-го и еще 610 более слабых игроков. Турнир в группе организуем так, чтобы выиграл 20-й (это, очевидно, можно сделать). Во вторую группу отнесем 1-го, 2-го, 18-го и оставшихся более слабых игроков и организуем турнир так, чтобы победил 18-й. Это можно сделать, организовав турнир так, как это описано выше: в первом туре 3-й и 4-й выигрывают у 1-го и 2-го, во втором 5-й и 6-й - у 3-го и 4-го и т. д. до восьмого тура, когда 17-й и 18-й выигрывают у 15-го и 16-го, после чего в девятом туре 18-й выигрывает у 17-го. В финале встречаются 20-й и 18-й и, следовательно, 20-й может победить.
Можно доказать по индукции, что в случае $2^n$ игроков наибольший номер победителя - $2n$.
Ответ: наибольший возможный номер победителя - 20.
