Кто поедет в Рио?

2

Кто поegем в Рюо

Г. М. Адельсон-Вельский,
И. Н. Берштейн,
М. Л. Гервер

Задача, о которой идет речь в этой статье, вовсе не носит специфический шахматного — да и вообще спортивного — характер. Ее можно было бы, например, сформировать так: из $n$ попарно не равных по весу камней отображать в порядке убывания $k$ самых тяжелых, ползуясь лишь двухчащными весами без гирь, с помощью минимального числа взвешивания. А вот формулировка, имеющая совершенное реализий математической смысл: составить программу для вычислительной машины, которая за минимальное число сравнений отбирала бы из $n$ попарно неравных чисел $k$ самых больших и располагала бы их в порядке убывания *).

Оговорка о попарном неравенстве чисел (или камней) автоматически обеспечивает выполнение условия: если $a > b$ и $b > c$, то $a > c$. Не нужно быть опытным большиском, чтобы понять, что в спорте на самом деле ничего подобного нет и что, скажем, проигрыв Фишера Петросяну на турине претензентов в Кюрасао и выигры Спасского в решающей партии матча на первенство мира с Петросяном отнюдь не предрешают исхода матча Спасский — Фишер.

Отметим, впрочем, что олимпиская система (проигравший выбывает) основана именно на допущениях, сформированных в начале статьи. Кстати, «обычная» олимпиская схема, по которой проигравший в финале сразу обьявляется вторым призером (а победитель встречи проигравших получиналистов — третьим), есть лишь ухудшенный вариант «Правил ВОМИ»!

Задача, о которой рассказывать авторы, как уже говорилось, носит полне серbezный характер. (Между прочитам, ее решение, при всей его видимой «элементарности», удалось получить лишь совсем недавно, что, безусловно, представляется особый интерес для нашего журнала). Излагать же ее показалось автором приятнее и веселее на «шахматном» языке…

Глава 1. Правила ВОМИ

Свершилось! Шахматные города Васюки, наконец, допущены на Всемирную Олимпiadу в Рю-де-Жаней-

*) В статье разбирается лишь случай $k=3$ (об общем случае говорится в задаче № 3).

ро. Вьяснилось это, как обычно, в последний момент, и теперь нужно в считанные дни проводится отборочный турир и выбрать из 128 шахматистов-любительей трех сильнейших. Двое из них (чемпion и второй призер) будут играть за команду Васю-

4

третього призеров, достаточно провести
$$127 + 6 + 6 = 139$$
партий.

Глава II. Нельзя ли короче?

Хорош ли правила ВОМИ? Нельзя ли определять 1-го, 2-го и 3-го призеров за меньшее число партий?

§ 1. Мнение руководства, случай и рок

Пусть еще до совершенной у руководства Клуба Четырех Коней сложилось мнение, что сильнейший шахматист — А, второй по слиле — В и третий — С. И пусть цель совершенной — проверить, что это действительное так.

Меньше, чем за 127 партий, такую проверку осуществить нельзя, так как все шахматисты, кроме чемпиона, должны проиграть хотя бы по одному партии. А за 127 партий — можно: 125 «аутсайдеров» (все, кроме А, В и С) играют 124 партии «на вылет» (после каждой партии проиграший выбывает), затем победитель играет с C и проиграает *), C проигравает *) В и В проиграает *) А. Собственно говоря, не обязательно даже знать призеров зааннее: их можно угадать случайно, так что иногда («если повезет») три призера определяются за 127 партий.

Мы будем, однako, считать, что про силу шахматистов ничего зааннее не известно и что нам «не веет». Более того, представим себе, что Злой Рок (или агент соперников — как хотите) влаяет на исход каждой партии так, чтобы совершенная тянулись как можно долше. Мы покажем, что в этом случае выбрать 1-го, 2-го и 3-го призеров среды 128 шахматистов меньше, чем за 139 партий, нельзя, как бы **) ни проводились оборочные севернония.

*) Если он выиграет, то, значит, руководство ошибалось, и что делать дальше — неясно.
**) Разумеется, в соответствии с предложениями 1—5 главы I.

§ 2. Формулировка теоремы

Исследуем сразу сущий случай, когда в совершенных участках 128, а любое число шахматистов. Обозначим его через n. Введем также следующое обозначение. Пусть N — произвольное число; для некоторых целых чисел l выполняется неравенство $2^l \geq N$. Обозначим через l [N] наименьшее из этих целых чисел.

Примеры.

1. Так как $2^3 < 10 < 2^4$, то l [10] = 4.
2. Если $2^{k-1} < N \leq 2^k$, то l [N] = k.
3. Вскоре нам понадобится знать, чем равно l [N], если N = 128·127. Так как $128 = 2^7$ и $2^6 < 127 < 2^7$, то $2^{13} < 128·127 < 2^{14}$, откуда l [128·127] = 14.

Теорема. Для определения 1-20, 2-20 и 3-20 призеров среди n шахматистов нужно сырать не менее, чем

$$P(n) = l[n(n-1)] + n-3$$
партий.

По сненее. По-другому эту теорему можно сформулировать так.

Пусть разрешено проверсти максимum R партий, где

$$R < l[n(n-1)] + n-3.$$

Тогда (по каким бы правил ни проводились оборочные севернония) результаты партий могут оказаться такими, что после R партий определить 1-го, 2-го и 3-го призеров еще не удостраняем.

Если n = 128, то l[n(n-1)] = l[128·127] = 14 (см. пример 3). Значит, P(128) = 14 + 128 - 3 = 139. Тем самым из формулированной теоремы следует, что для определения 1-го, 2-го и 3-го призеров среди 128 шахматистов нужно не менее, чем 139 партий. За 139 партий их определить можно по правиле ВОМИ — так что правила ВОМИ хорошо!

§ 3. В бухгалтерии Злого Рока

В § 1 этой главы мы предупредили, что Злой Рок старается затянут отборочные севернония. Сейчас

5

мы указываем стратегию, придерживаясь которой, он добется, чтобы определеня 1-го, 2-го и 3-го призов среди $n$ шахматистов попадобилось как минимум

$$P(n) = l \left[ n(n-1) \right] + n-3$$

партий.

О пределене 1. Будем называть командо любую пару шахматистов $(A, B)^*$. Подчеркием, что команды $(A, B)$ и $(B, A)$ — разные; $A$ играет в команде $(A, B)$ на первой доске, а в команде $(B, A)$ — на второй.

До начала соревнований на участке в Олимпиде претендуют все команды. Сколько их?

Do turнира каждой из $n$ шахматистов имеет шансы играть на первой доске. При этом он может возглавить $n-1$ команду (вторым к нему может попасть любой шахматист, кроме него самого). Таким образом, число всех командаров $n$ ($n-1$).

В ходе соревнований число команд, претендующих на позедку в Рио, постепенно уменьшается (пока не остаетсяровно одна такая команда).

Пусть в турине уже сыгран несколько партий. По их результатам разделим всех участников на 3 группы. К первой отнесем всех, кто не проигral ни одной партии. К второй — тех, кто проигralровно одну партию, причем обязательно шахматисту первой группы. К третьей — всех остальных (тех, кто проигral более одной партии или одну партию — по игроку не из первой группы).

У праванении. Проверьте, что в этой ситуации на позедку в Рио претендуют следующие команды:

1. все команды $(A, B)$, в которых $A$ — из первой группы, а $B$ — из второй, причем единственную партию, которую $B$ проигral, он проигral именно $A$;

2. все команды $(C, D)$, также, что и $C$, и $D$ — из первой группы.

Проверьте, что никакие другие команды на участке в Олимпиде не претендуют.

*) «Команда» состоит именно из двух, а не из трех человек: запасной игрок в состав команде не включается (так удобнее для изложения).

(У казание. Пусть $B$ проигral $A$, тогда $B$ уже заведено не станет чемпоном, а вторым призером сможет стать только при том условии, что чемпоном оказывается $A$. Тем самым $B$ уже не сможет возглавить никакую команду и только в одной команду — в $(A, B)$ — может попасть в качестве второго участника.)

Определение 2. Если к какому-то моменту соревнований шахматист $A$ выигral $a$ партий, а шахматист $B$ — $b$ партий, то мы будем говорить, что в активе команды $(A, B)$ имеется $a+b$ очков. Число $2^{a+b}$ называем характерисмкой команды $(A, B)$.

После каждой новой партии актив любои команды либо увеличивается на 1 (если победитель партии входит в эту команду), либо не меняется. Соответствие характерисмкой любои команды либо удаливается, либо остается неизменной.

Определение 3. Пусть проведено некоторое число партий. Сложившуюся ситуацию удобно характеризовать числом $M$, которое равно сумме характерисмкой всех команда, еще претендующих на участке в Олимпиде.

Чему равно $M$ в начальной ситуации (до проведения соревнований)? Никто не выигral еще ни одной партии, в активе каждой команды 0 очков, характерисмкой любои команды равна $2^0=1$. Таким образом, $M$ начальное — это просто общее число команда, то есть $M_{\text{начальное}}=n$ ($n-1$).

Лемма. Пусть в некоторых ситуациях, характеризуемой числом $M$, проводится партия между шахматами $A$ и $B$. Обозначим через $M_A$ число, характеризущее ситуацию, которая возникнет, если выиграет $A$, а через $M_B$ — характерисму ситуацию в случае выигрыша $B$. Тогда

$$M_A + M_B = 2M,$$

так что хотя одно из чисел $M_A$ и $M_B$ не меньше $M$.

Доказательство. До игры между $A$ и $B$ все команды, претендущие на участке в Олимпиде, естественно разбить на 3 группы.

6

I группа. Команды, в которых $A$ входит, а $B$ либо не входит, либо входит после $A^*$).

II группа. Команды, в которых $B$ входит, а $A$ либо не входит, либо входит после $B$.

III группа. Команды, в которых не входят ни $A$, ни $B$.

Обозначим через $M_I$, $M_{II}$, $M_{III}$ суммы характеристикоманд I, II и III группы (так что $M=M_I+M_{II}+M_{III}$).

Докажем, что $M_A=2M_I+M_{III}$. Действительно, после победы $A$ на победу в Рио претендуют только команды I и III группы; при этом в III группе характеристики команд не меняются, а в I группе удваивается.

Аналогично доказывается, что

$$M_B = 2M_{II} + M_{III}.$$

Итак,

$$M_A + M_B = 2(M_I + M_{II} + M_{III}) = 2M.$$

Стратегия Злого Рока. Как идет отборочный турпир? Как мы знаем, все партии проводятся последовательно (одна за другой). Участники каждой новой партии называются в зависимости от результатов всех предыдуших игра.

Пусть уже проведено неокоторое число партии, и очередная игра называется между шахматами $A$ и $B$. Злой Рок подсчитывает характеристики $M$, $M_A$ и $M_B$ (см. лемму); затем если $M_A>M_B$, он устранает так, чтобы победил $A$, а если $M_B>M_A$ — так, чтобы победил $B$; если же $M_A=M_B$, то он не встрешается. Так как большее из чисел $M_A$ и $M_B$ завершено не меньше $M$ (по лемме), то при такой стратегии характеристика $M$ после каждой партии не уменьшается.

Подчерком, что Рок достаточно быть Всемогущим и не нужно быть

*) В входит после $A$ только в одну команду ($A, B$); эта команда включается в I группу, размещется, только при том условии, что она еще претендует на победу в Рио.

Всеведущим: не вникая в планы устроительной турпира, он применяет одну и ту же стратегию при любом расписании игра.

Далее мы показем, что при этой стратегии определяние 1-го, 2-го и 3-го призеров потребует как минимум

$$P(n) = l[n(n-1)] + n-3$$

партий.

§ 4. Доказательство теоремы

Do corvevohany $M_{начальное} = n(n-1)$. Чему равно $M$, когда corvevohany закончены и определяны 1-й, 2-й и 3-й призеры $X$, $Y$ и $Z$? Для поезда на Олимпiadу отбрана одна команда ($XY$). Обозначим через $v$ число очков в активе этой команды. Тогда $M_{конецное} = 2^v$.

Если Злой Рок придерживался описанной выше стратегии, то после каждой партии характеристика $M$ не уменьшалась, так что $M_{конецное}$ не меньше, чем $M_{начальное}$. Отсюда $2^v \geq n(n-1)$, то есть $v \geq l[n(n-1)]$. Таким образом, первые два призера $X$ и $Y$ участвовали не меньше, чем $l[n(n-1)]$ партий.

Кроме того, было проведено как минимум $(n-3)$ партии без их участия. Действительно, каждый из $(n-3)$ шахматных, не вошедших в признаную тройку, должен был проиграть кому-то, кроме $X$ и $Y$, — иначе он претендуал бы на третье место.

Таким образом, всего в турире было сыграно не менее, чем

$$P(n) = l[n(n-1)] + n-3$$

партий. Теорема доказана.

Глава III. Как определить трех призеров среди $n$ шахматов?

В главе I были приведены правила, по которым можно определить трех призеров среди 128 шахматов. Приведем аналогичные правила для случая $n$ шахматов. Пусть $l[n]=k$, то есть

$$2^{k-1} < n \leq 2^k.$$

7

§ 1. Определение чемппона

Игры проводятся по оптимийской системе. На 1-м этапе всех участников разбиают на две группы: в одной $2^k$—пар; в другой паре определяется победитель, которое допускают ко 2-м этапу; члены первой группы начинают борьбу сразу со 2-го этапа. Всего ко 2-м этапу допущено

$$\left(n - 2^{k-1}\right) + \left(2^k - n\right) = 2^{k-1}$$

участников. Все этапы, начиная со 2-го, «стандартины»*): участники этапа разбиаются на пары, в каждой из пар определяется победитель, которое допускают к следующему этапу. Чемппон определяется в финансовой игре на $k$-м этапе. Так как каждый из $n$ участников, кроме чемппона, проигрывает при такой системеровно одну партию, то всего на $k$ этапах будет сыграна $(n-1)$ партия.

§ 2. Определение второго призера

На это место претендуют шахматные, проигрывшие только чемппону. Их не более чем $k$; присвоим им номера 1, …, $k$ ($N_2$ i — это тот, кто проигрывал чемппону на $i$-м этапе**).

Проводим игры так: $N_2$ 1 играет с $N_2$ 2***), затем победитель—с $N_2$ 3, и т. д. (всего не более чем $k-1$ партия). Победитель последней партии — второй призер.

*) 1-й этап в отличие от случая, разобранного в правильах ВОМИ, является «нестандартным» (то есть требует указанного в этом параграфе дополнительного разбиения участников на группы), если $n$ не есть точная степень двойки.

**) Отметим, что $N_2$ 1 может не достигся никакому (если чемппон начал игры со 2-го этапа).

***) Иного этапа не проводится (см. предыдущую способу), и все начинается с партией между $N_2$ 2 и $N_2$ 3.

§ 3. Определение третьero призера

Легко проверить (см. § 3 главы I), что второй призер выиграл не более $k$ партий и поэтому на третье место претендуют не более $k$ человек. Сильнейший из них завершимо определяется за $k-1$ партию. Это и есть третьей призер.

§ 4. Выводы

Что бы найти среди $n$ шахматистов 1-го, 2-го и 3-го призеров, достаточно проверить

$$\left(n-1\right) + \left(k-1\right) + \left(k-1\right) = 2k + n-3 = 2l \left[n\right] + n-3$$

партий. Это число мы обозначим через $Q(n)$.

Глава IV. Обсуждение результатов

Пусть $n$ — целое число, $n \geqslant 3$. Обозначим через $I(n)$ число, удовлетворяющее следующим двум условиям:

1. за $I(n)$ партий наверняка можно определить 1-го, 2-го и 3-го призеров среди $n$ шахматистов.

2. если $R < I(n)$, то результат партий могут оказаться таким, что за $R$ партий определить 1-го, 2-го и 3-го призеров среди $n$ шахматистов не удается.

Тогда результаты, полученные в главах II и III, можно записать в виде формулы

$$P(n) \leqslant I(n) \leqslant Q(n).$$

Напомним, что

$$P(n) = l \left[n(n-1)\right] + n-3,$$

$$Q(n) = 2l \left[n\right] + n-3,$$

где $l \left[n\right] = k$ при $2^k \geqslant n > 2^{k-1}$.

Можно показать, что $Q(n)$ равно либо $P(n)$, либо $P(n)+1$. В первом случае $I(n)=P(n)=Q(n)$. Во втором случае для $I(n)$ имеются две возможность: либо $I(n)=P(n)$, либо $I(n)=Q(n)$. Обе возможности