Задача

Допустим, вы — репортер из «Алгоритмических спортивных новостей», и к концу сезона возникает следующая ситуация. Четыре бейсбольные команды пытаются занять первое место в Восточной подгруппе Американской лиги; назовем их «Нью- Йорк», «Балтимор», «Торонто» и «Бостон».
На данный момент команды имеют следующее количество побед:

Нью-Йорк: 92, Балтимор: 91, Торонто: 91, Бостон: 90.

В сезоне осталось пять игр: все возможные пары из перечисленных команд, кроме Нью-Йорка и Бостона.

Вопрос заключается в следующем: сможет ли Бостон набрать побед не меньше, чем любая другая команда в подгруппе (то есть закончить на первом месте — воз- можно, разделив его с другой командой?)

Если немного подумать, становится очевидно, что ответ будет отрицательным. Один из аргументов выглядит так: очевидно, Бостон должен выиграть все оставши- еся игры, а Нью-Йорк должен проиграть обе оставшиеся игры. Но это означает, что и Балтимор, и Торонто выиграют у Нью-Йорка; следовательно, победитель игры Балтимор-Торонто будет иметь больше побед.

Следующий аргумент позволяет избежать подобного анализа. Бостон может набрать не более 92 побед. Совместно три другие команды имеют 274 победы, и в трех играх друг с другом будет ровно три победы, так что итоговая сумма со- ставит 277. Но 277 побед для трех команд означают, что одна из них будет иметь более 92 победы.

Естественно задать некоторые вопросы: (i) Существует ли эффективный ал- горитм для определения того, лишилась ли команда шансов на первое место? (ii) Когда команда лишается шансов на первое место, существует ли «усредняю- щий» алгоритм наподобие описанного выше, который доказывает это?

Перейдем к более конкретной формулировке: имеется множество S команд, для каждой команды х S текущее количество побед равно wх. Кроме того, две команды x,y S еще должны сыграть gxy партий друг с другом. Наконец, задана

конкретная команда z.

Мы воспользуемся методами максимального потока для двух целей. Во-первых, будет представлен эффективный алгоритм для принятия решения о том, выбыла ли команда z из соревнования за первое место — другими словами, возможно ли выбрать результаты остальных игр так, чтобы команда z имела побед не меньше, чем любая другая команда в S.

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

(7.59) Допустим, команда z действительно выбыла из борьбы за первое место. Тогда существует «доказательство» этого факта в следующей форме:

♦ z может закончить игры с максимум m победами.

♦ Существует подмножество команд T !Ξ S, для которого

Е⅞+∑⅜>Ч1.

лег т.уеГ

(А следовательно, одна из команд Tнеизбежно получит строго больше m побед.)

Следующий пример дает более сложную иллюстрацию того, как работает «ус- редняющий» аргумент (7.59). Предположим, остались те же четыре команды, но с другими количествами текущих побед:

Нью-Йорк: 90, Балтимор: 88, Торонто: 87, Бостон: 79.

У Бостона еще остаются четыре игры против каждой из трех остальных команд. У Балтимора остается еще по одной игре против Нью-Йорка и Торонто. И наконец, Нью-Йорку и Торонто осталось сыграть еще шесть игр друг с другом. Понятно, что для Бостона ситуация выглядит мрачно, но действительно ли он выбыл из борьбы за первое место?

Да, у Бостона действительно не осталось шансов на первое место. Чтобы убе- диться в этом, заметьте, что у Бостона может быть не более 91 победы; а теперь рассмотрим множество команд T = {Нью-Йорк, Торонто}. Нью-Йорк и Торонто вместе уже имеют 177 побед; в шести оставшихся играх общее количество побед достигнет 183, а 183/2 > 91. Это означает, что у одной команды неизбежно будет более 91 победы, поэтому Бостон не сможет занять первое место. Любопытно, что в данном экземпляре задачи для множества всех трех команд, опережающих Бо- стон, такое доказательство не подходит: все три команды имеют в сумме 265 побед, и между ними осталось еще 8 игр; в сумме получается 273, а 273/3 = 91 — этого недостаточно, чтобы доказать, что Бостон не сможет разделить первое место с другими командами. Следовательно, для усредняющего аргумента должно быть выбрано множество T, которое состоит из Нью-Йорка и Торонто и не включает Балтимор.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача