До финала

До финала

МАТЕМАТИЧЕСКИЙ КРУЖОК

А.БЛИНКОВ

На личной олимпиаде XXVI Турнира имени А.П.Савина школьлникам 5–6 классов была предложена следующая задача. Задача 1. Школьный турнир по настольному теннису проходил по такой системе: на каждом этапе игроки разбивались на пары и играли одну партию, на следующем этапе опять разбивались на пары и играли одну партию (пары не повторялись) и так далее. Школьник, дважды проигравший, выбывал из турнира. Если на каком-то этапе количество участников нечетно, то один проходил на следующий этап без игры. Сколько человек участвовало в турнире, если до финала, в котором должны были играть двое, было сыграно 29 партий? Эта же задача, но с добавленным вопросом – «Сколько человек участвовало в турнире, если до финала, в котором должны были играть двое, было сыграно 30 партий?» – вошла под номером 15 в Конкурс имени А.П.Савина (см. «Квант» № 11-12 за 2021 г.). К удивлению жюри, считавшего задачу простой, ее решили немногие. Поэтому, прежде чем привести решение, обратимся к «классической задаче» в слегка измененной формулировке. Задача 2. В турнире по боксу, проходившему по олимпийской системе (проигравший выбывает), было проведено 29 боев, не считая финального. Сколько боксеров участвовало в турнире? Решение. В каждом из боев, прошедших до финала, проигрывал один боксер, который выбывал из турнира. В финале встречались двое не проигрывавших ранее, значит, всего участников было 29 + 2 = 31.

Упражнение 1. В турнире по тем же правилам участвовало 66 боксеров. Сколько боев проведено до финала?

Главный вывод – для решения задачи 2 нет необходимости разбирать, как именно проходили бои. Это касается и задачи 1.

DOI: https://doi.org/10.4213/kvant20220205

Решение задачи 1. Каждый из школьников, дошедших до финала, либо вовсе не проигрывал, либо проиграл одну партию. Поэтому на долю остальных приходится 29, 28 или 27 проигранных партий. Так как школьник выбывал после двух проигранных партий, то 29 или 27 партий быть не могло, а количество выбывших составляет 28: 2 14. Значит, в турнире могло участвовать только 16 школьников. Задача решена. Отметим, что и в данном случае не надо приводить пример, описывающий как именно проходил турнир, и показывать, что полученный ответ достигается, так как в условии сказано, что турнир состоялся, а полученный ответ – единственный. Но ситуация изменится, если в таком турнире до финала было сыграно 30 партий. Действительно, рассуждая аналогично, получим, что на долю выбывших приходится 30, 29 или 28 партий. Тогда в турнире могло участвовать $30^{:} 2 2 17$ или $28^{:} 2 2 16$ школьников. В этом случае требуется показать, что оба полученных ответа возможны. Сделаем это для 17 участников. Один из школьников без игры прошел на второй этап, на котором «отдыхал» один из школьников, выигравший на первом этапе, а Таблица 1 остальные, выигравшие на первом и не игравший ранее участники, встречались с проигравшими, сменив соперников, и вновь выиграли. Тогда после второго этапа 8 участников выбыли, а осталось 9 участников, не имеющих поражений. Следующие два этапа проходили по аналогичной схеме, после чего осталось 5 школьников, не имеющих поражений. Результаты пятого, шестого, седьмого и восьмого этапов приведены в таблице 1 (индекс соответствует номеру этапа). Таким образом, до финала дошли участники 1 и 2, а сыграно было $8 + 8 +^{4} +^{4} + 2 + 2 + 1 + 1 = 30$ партий.

Упражнение 2. Приведите аналогичный пример для 16 участников такого турнира, в котором сыграно 30 партий.

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

47

МАТЕМАТИЧЕСКИЙ

порядок разбиения на пары. Приведем первую часть правил турнира, система проведения которого носит название Double Elimination. Турнир разделен на две сетки – верхнюю и нижнюю (сетку победителей и сетку проигравших). Все участники начинают турнир в верхней сетке. Участники разбиваются на пары, которые проводят в первом туре игры между собой. Победители первого тура выходят во второй тур верхней сетки. Проигравшие переходят в нижнюю сетку. В нижней сетке турнир начинается со второго тура. Начиная с этого тура, игры проводятся одновременно в обеих сетках, но никто не должен играть с одним и тем же соперником дважды. Выигравший в верхней сетке переходит в следующий тур в ней же. Проигравший в верхней сетке переходит в следующий тур в нижней сетке. Выигравший в нижней сетке переходит в следующий тур в ней же. Проигравший в нижней сетке выбывает из турнира. При таком подходе приведенный пример не работает, так как уже во втором туре между собой встречаются участники из разных сеток. Более того, если на каждом этапе игроки разбивались на пары, то такой турнир вообще провести невозможно! Действительно, уже после второго этапа количество участников в нижней сетке существенно превысит количество в верхней, поэтому в какой-то момент в верхней сетке останется один участник, у которого не будет пары, а в нижней сетке – не менее двух. Это удобно показать на примере 16 участников (см. таблицу 2, пары чисел – количество

Таблица 2 участников в верхней и нижней сетках соответственно). На помощь приходит вторая часть правил, которая имеет несколько разновидностей. Наиболее простая из них такова. На некоторых этапах игры проводятся только в нижней сетке до тех пор, пока количество участников в обеих сетках не станет одинаковым. После того, как в обеих сетках останется по два участника, на следующем этапе образуются две пары, в каждой из которых участник из верхней сетки встречается с участни-

КРУЖОК

ком из нижней. В случае побед обоих «верхних» участников они разыгрывают финал. В случае поражений обоих на следующем этапе они меняются соперниками и победители этих пар выходят в финал. Если же выигрывает один из них, то образуется пара участников, имеющих по одному поражению, победитель которой выходит в финал и играет с тем, кто поражений не имеет. Отметим, что приведенные правила почти автоматически обеспечивают условие «никто не должен играть с одним и тем же соперником дважды». Тогда турнир, в котором 16 участников сыграли до финала 30 партий, мог быть проведен так, как показано в таблице 3 (в первой строке – количество учас-

Таблица 3 тников в каждой сетке, во второй – количество игр в каждой сетке; на 6 этапе участники из верхней сетки сначала проиграли нижним и поменялись соперниками, после чего победители пар вышли в финал).

Упражнение 3. Приведите пример, показывающий, что в турнире с 17 участниками могло быть сыграно 30 партий до финала, согласно правилам, приведенными выше.

В заключение сравним турниры по олимпийской системе и системе Double Elimination для 16 участников. По олимпийской системе до финала проходит 3 этапа и играется 14 партий, а по системе с выбыванием после двух поражений проходит 6 или 7 этапов, в которых играется 28, 29 или 30 партий, т.е. во втором случае и этапов, и партий как минимум вдвое больше. Желающие могут исследовать, сохранятся ли эти закономерности для турниров с произвольным количеством участников, начав, для простоты, с турнира, в котором $2^{n}$ участников.

51

ОЛИМПИАДЫ

та с воздухом; поток тепла через картонный диск пропорционален разности температур его поверхностей и пропорционален площади диска. А.Аполонский

пуса корабля считайте постоянными (командир может выбирать любое значение расхода). Изменение массы корабля не учитывайте, ускорение свободного падения равно g. А.Заяц

Задача 2. Тяжелый поршень В вертикальном закрытом сосуде переменного сечения имеются два отделения цилиндрической формы: нижнее c площадью сечения $S_{1} S$ и высотой $h_{1} h$, верхнее c площадью сечения $S_{2} 3 S$ и высотой $h_{2} 3 h$ (рис. 10). Нижнее отделение плотно и герметично закрыто подвижным теплопроводящим поршнем (поршень не приклеен, но газ не проникает в пространство между поршнем и опорами), который может с минимальным трением перемещаться внутри верхнего от- Рис. 10 деления. В обоих отделениях находится одно и то же количество Q газа при температуре $T_{0}$. Газ во всем сосуде медленно нагревают. Когда температура газа достигает $величины_{0}^{2T}$, поршень отрывается от опор. 1) Чему равна масса поршня? 2) На какой высоте h c от нижнего основания сосуда окажется поршень в равновесии? Температура всего газа поддерживается $равной_{0}^{2T}.^{3)}$ Газ в сосуде начинают медленно охлаждать. При какой $температуре^{T}$ поршень снова опустится на опоры? Примечание. Температура газа над и под поршнем всегда поддерживается одинаковой. А.Заяц

Задача 4. И снова Снеллиус В архиве Снелла нашли чертеж. От времени чернила частично выцвели и остались видны только 4 точки, две из которых являются точечными действительными источниками $S_{1}$ и $S_{2}$, а оставшиеся две – D и E – их изображениями (рис. 11). Из описания к чертежу следовало, что изображения созданы одной линзой. Найдите построением с помощью циркуля и ли- Рис. 11 нейки (без делений) все возможные положения линзы, ее тип и фокусное расстояние. А.Евсеев, В.Словобянин

Задача 3. Мягкая посадка Космический корабль должен приземлиться на лишенную атмосферы планету и коснуться ее поверхности со скоростью, не превышающей $v_{п}$, которую могут погасить амортизаторы. На $высоте^{h}$ над поверхностью планеты командир корабля включил тормозной реактивный двигатель, создающий силу тяги, направленную вверх. Какой по величине в этот момент была $скорость^{v}$ корабля, направленная вертикально вниз, если оказалось, что в процессе посадки он истратил минимальное количество топлива? (Если таких скоростей несколько, то укажите их все.) Массовый расход P топлива и скорость u истечения газов относительно кор- торах, равна 7 Вт. Определите суммарную мощность, выделяющуюся на резисторах в цепи, изображенной на рисунке 13. Характеристики всех элементов цепей не заданы, но элементы, обозначенные на схемах одинаково, имеют одинаковые характеристики. Источники можно считать идеальными. А.Коновалов

Задача 5. Суммарная мощность В цепи, изображенной на рисунке 12, суммарная мощность, выделяющаяся на резис-

Рис. 12

Рис. 13

11 класс Задача 1. Треугольник и пленка Легкие стержни OA и AB соединены шарнирно между собой (рис. 14). Конец О стержня ОА закреплен шарнирно на гладкой спице, а на конце В стержня АВ прикреплено с помощью шарнира маленькое колечко мас-