1. Игрок 11 проиграл игроку 05, поэтому известно, что игрок 13 слабее, чем игроки 05, 11 и 12.

2. Пусть X есть t-Vi в порядке убывания элемент и пусть 5 есть множество всех элементов у, таких, что выполненных сравнений недостаточно для доказательства того, что х < у и у < X. Существуют перестановки, удовлетворяющие всем выполненным сравнениям, но в них все элементы 5 меньше, чем х; действительно, мы можем потребовать, чтобы все элементы S были меньше, чем х, и вложить полученное частичное упорядочение в линейное упорядочение. Аналогично существуют допустимые перестановки, в которых все элементы S больше, чем х. Следовательно, мы не можем знать положение х, если 5 не пусто.

3. Соперник может считать проигравшего в первом сравнении слабейшим среди всех игроков.

4. Предположим, что наибольшие {t - 1) элементов - это {а\,... ,at-\}. Любой путь определения наибольших t-элементов на дереве сравнений, совместимый с этим предположением, должен включать, по меньшей мере, n - t сравнений для определения наибольшего из оставшихся п - t + 1 элементов. Каждый из таких путей должен иметь не менее n - t точек выбора альтернатив, т. е. их в сумме существует не менее 2"~. Таким образом, каждый из п- выборов наибольших {t - 1) элементов должен появиться не менее чем в 2"" листьях дерева.

5. Действительно, Wt{n) < Vt{n) + S{t - 1), как следует из упр. 2.

6. Пусть g{li,l2, ...,1т) = 7n-2-l-rig(24-22 + - • +2")], и допустим, что / = 9 для/1-1-/2 +

----\-1т+2т < N. Докажем, что f = д, если +lm+2ni = N. Мы можем считать, что

h > h > > 1т. Существует лишь несколько способов выполнения первого сравнения. Стратегия A(j, к) при j < к. Сравнить наибольший элемент группы j с наибольшим элементом группы к. Это дает соотношение

f(h,..,lm) < 1 + g(h,. . . ,lj-l,lj+l,lj + l, . . . ,lk-ulk + l, . . ,1т)

= g(h, ...,ik-i,ij,ik+i,-• • ,/m) >g(h,. ,lm).

Стратегия B(j, k) при h > 0. Сравнить наибольший элемент группы j с одним из меньших элементов группы к. Это дает соотношение f{h,... ,1т) < 1 + П1ах(а,/3) = 1 +/3, где а = g{h,...,lj-i,lj+\,-..,lm) < g(li,...,lm) - 1, /3 = g{h,... ,lk-i,lk-l,lk+i, ,lm) > g{h,... ,lm) - 1. Стратегия C(j, k) при j < k, lj > 0, lk > 0. Сравнить один из меньших элементов группы j с одним из меньших элементов группы к. Соответствующим соотношением будет fill,. . . ,/m) < l+g(ll,. . .,lk-l,lk - l,/* + l, • ..,lm) > g{ll, .,lm).

Значение f(li,lm) найдем, взяв минимум правой части среди всех этих стратегий; следовательно, f(li,. . ,1т) > g(li,... ,1т)- Если m > 1, то стратегия A(m-1, т) показывает, что /(/l, . . .,1т) < g(h,. .. ,1т), поскольку g(li, . . . ,lm-l,lm) = 9(h, ,lm-l,lm-l), еСЛИ

i > >lm. {Доказательство. \\g{M + 2°)] = \lg{M + 2*")] при 0 < a < 6, если M есть положительное кратное 2*".) Если m = 1, используйте стратегию С(1,1).

[В статье С. С. Кислицына определена оптимальная стратегия A(m-1, т) и вычислено /(/, /,...,/) в замкнутом виде; общая формула для / и это упрощенное доказательство были получены Флойдом в 1970 году.]

7. При j > 1, если j + l находится в а, Cj равно 1 плюс число сравнений, необходимых для выбора следующего в порядке убывания элемента а. Аналогично в случае, если j + l находится в а", Ci всегда равно О, так как деревья в конце всегда выглядят одинаково.

8. Другими словами, существует ли расширенное бинарное дерево с п внешними узлами, такое, что сумма ргюстояний от корня до t - 1 наиболее удаленных внутренних узлов меньше, чем соответствующая сумма для полного бинарного дерева? Ответ на этот вопрос

отрицательный, поскольку (как нетрудно показать) к-й в порядке убывания элемент ц{а) больше или равен [lg(n - fc)J при всех а.

9. (Для всех путей используются шесть сравнений, однако эта процедура не оптимальна для Vs{b).)

(3:4) Симметрично (2:4) Симметрично (3:5) Симметрично (2:5) [2

10. (Медиана найдена вручную путем проб и ошибок; использовано упр. 6, чтобы упростить нахождение полезных линий.)

(3:4). Симметрично

(2:4). Симметрично

(5:6) Симметрично

i2:6i Симметрично

13:5[

11. См. Information Processing Letters 3 (1974), 8-12.

12. После удаления наименьшего из {Xi, Хг, Хз, Х4} получаем конфигурацию - плюс п - 3 изолированных элементов; третий из них может быть найден еще за Рз(п - 1) - 1 шагов.

13. Найдя медиану первых /(п) элементов, скажем Xj, сравним ее с каждым из остальных; это даст разбиение всех элементов на приблизительно п/2 - к меньших, чем Xj, и п/2 + к больших, чем Xj, при некотором к. Остается найти \к\-й в порядке убывания или возрастания элемент большего множества, что требует еще п/2 + O(ifelogn) сравнений. Среднее значение равно 0{1/у/п) + 0{п fjn)) (рассмотрите точки, равномерно распределенные на интервале [0..1]). Обозначим через Т{п) среднее число сравнений для /(п) = п/; имеем Г(п) - п = Т{п) - п + п/2 + 0{п); отсюда следует искомый результат.

Интересно, что при п = 5 этот метод требует только 5у сравнений в среднем, что несколько лучше, чем дерево из упр. 9.

14. В общем случае t наибольших элементов можно найти за Ut(n) < V((n - 1) -Ь 1 сравнений, если определить t-й в порядке убывания элемент из {Xi,... ,Xn-i} и сравнить его с Х„ (имея в виду упр. 2). (Киркпатрик доказал, что (12) является нижней оценкой для Ut{n -Ь 1) - 1. При больших t найдена более точная оценка Ut{n) [см. J. W. John, SICOMP 17 (1988), 640-647].)

15. Требуется min(t,n+l-t) слов памяти. Предположим, что t < п + 1 - t. Если мы не сохраним все первые t слов, когда они читались в первый раз, то можем потерять t-я в порядке убывания элемент, зависящий от последующих значений, все еще не известных нам. Обратно, t ячеек достаточно, так как мы можем сравнивать вновь введенный элемент с предыдущим t-м, запоминая значение в регистре тогда и только тогда, когда он больше.

16. Перед началом выполнения алгоритмы (a,b,c,d) = (п,0,0,0), а после завершения получается четверка (0,1,1, п-2). Если соперник, избегает непредвиденных исходов, то после каждого сравнения (а, Ь, с, d) может перейти либо в себя, либо в

(а-2, 6-1-1, c-hl, d), если а > 2;

(а-1, 6, с-Ы, d) или (а-1, 6-1-1, с, d), если а > 1;

(о, 6-1, с, d-1-l), если 6 > 2;

(а, 6, с-1, d-1-l), если с > 2.

Отсюда следует, что требуется [а] -Ь 6 -Ь с - 2 сравнений, чтобы из (а,6,с, d) получить (0,1,\,a+b+c+d-2). [См. САСМ 15 (1972), 462-464. В работе FOCS 16 (1975), 71-74, Пол доказал, что этот алгоритм также минимизирует среднее число сравнений.]

17. Используйте (6) сначала для наибольшего элемента, затем - для наименьшего. Обратите внимание на то, что [n/2j сравнений общие для обоих случаев.

18. Vt(n) < 18п - 151 при всех достаточно больших п.

21. Шаг 0. Постройте два дерева турниров с выбыванием размерами 2* и 2*""".

Шаг j для 1 < j < t. (К этому моменту уже выведено j ~ 1 наибольших элементов. Оставшиеся элементы вместе с набором фиктивных, каждый из которых равен -оо, появятся теперь в двух деревьях, А и В, где А имеет 2* листьев, а. В - 2*~""-.) Пусть о - победитель в А, и предположим, что о выиграл у оо, oi, а-!, где О/ - победитель среди 2 элементов. Аналогично пусть 6 и 6о, 61, bk-t+j-i -

победитель и обладатель второго места в В. Если j = t, вывести max(a, 6) и прекратить выполнение. В противном случае "нарастить" другой уровень в нижней части В, вставив 2*-+J фиктивных элементов, каждый из которых считается проигравшим в первой встрече с участником В. (Наша стратегия - влить В в А, если возможно, заменив им поддерево