Турнир по настольному теннису
Пять членов клуба любителей настольного тенниса средней школы им. Милларда Филмора решили провести между собой турнир по олимпийской системе.
Тренер составил таблицу розыгрыша турнира, снабдив ее следующими пояснениями.
Тренер. Пять — число нечетное, поэтому в первой круге один участник турнира свободен от игры. Еще один участник свободен от игры во втором круге. Таким образом, всего за турнир будет сыграно 4 партии.
На следующий год в спортивный клуб записалось 37 школьников. Тренер снова составил таблицу розыгрыша турнира, постаравшись свести до минимума число участников, которые переходят в следующий круг без игры. Сколько партий было сыграно за весь турнир на этот раз?
Как, вы еще не сосчитали? А ведь задача решается просто! В каждой партии проигравший выбывает, а поскольку дли того, чтобы определить победителя, следует исключить всех участников, кроме одного, то за весь турнир должно состояться 36 партий. Не правда ли, все очень просто?
Сколько участников турнира перейдут в следующий круг без игры?
Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа n всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?
При заданном n число участников, остающихся без партнера, можно определить следующим образом. Вычтем из n наименьшую степень числа 2, которая больше или равна n. Полученную разность запишем в двоичной системе. Число единиц в двоичной записи и будет равно числу участников турнира, вынужденных перейти в следующий круг без игры из-за нехватки партнера. В нашей задаче мы вычтем 37 из 64 (то есть из 26) и получим разность, равную 27. Десятичное число 27 в двоичной системе имеет вид 11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.
Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из n элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно n − 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.
Автоматическая сортировка играет важную роль в вычислительной математике и в информатике. Ей посвящено немало книг. Каждый из нас без труда назовет длинный перечень примеров применения автоматической сортировки. Подсчитано, что примерно четверть машинного времени в научных и в технических расчетах затрачивается на решение задач, связанных с сортировкой данных.
Стаканчики профессора Квиббла
Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.
Барни. Перед вами 10 бумажных стаканчиков, расставленных в ряд. В первые 5 стаканчиков я наливаю кинки-колу, остальные 5 стаканчиков остаются пустыми. Можно ли переставить 4 стаканчика так, чтобы пустые и полные стаканчики чередовались?
Барни. Правильно! Стоит лишь переставить второй стаканчик с седьмым, а четвертый с девятым, как задача будет решена.
Разговор Барни с покупателями услышал проходивший мимо профессор Квиббл, большой любитель неожиданных решений, который счел необходимым вмешаться.
Проф. Квиббл. Переставлять 4 стаканчика совсем не обязательно. Я берусь решить задачу, переставив лишь 2 стаканчика. Как, по-вашему, это возможно?
Проф. Квиббл. Мое решение проще простого. Я беру второй стаканчик и переливаю его содержимое в седьмой, а содержимое четвертого стаканчика — в девятый.
Глубокая мысль
Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местами», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как может показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?
Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях n, где n — число полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При n = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При n = 2 решение очевидно и сводится к перестановке одной пары стаканчиков. Возможно, вы удивитесь, когда узнаете, что при n = 3 чередование пустых и полных стаканчиков достигается перестановкой одной пары стаканчиков. Еще немного усилий, и вам откроется довольно простая общая закономерность. При четном n для решения задачи требуется поменять местами n/2 пар, а при нечетном n соответственно (n − 1)/2 пар стаканчиков. Следовательно, если имеется 100 пустых и 100 полных стаканчиков, то задачу можно решить, переставив 50 пар стаканчиков.
При этом вы сдвинете с места 100 стаканчиков. Предложенное профессором Квибблом шуточное решение позволяет вдвое уменьшить число стаканчиков, сдвигаемых с места.
Существует одна классическая головоломка, очень похожая на только что рассмотренную нами задачу, но несколько более трудную. Начнем с 2n предметов, выстроенных в ряд. Пусть по-прежнему n предметов, составляющих первую половину ряда, будут одного типа, а n предметов, составляющих вторую половину ряда, будут другого типа. (Как и прежде, их можно «моделировать» стаканчиками, фишками, игральными картами и т. п.) Требуется переместить предметы так, чтобы предметы одного типа чередовались с предметами другого типа, но в отличие от предыдущей задачи слову «переместить» придается строго определенное значение. На этот раз слово «переместить» означает, что любые два соседних предмета разрешается, не изменяя их последовательности, изъять из ряда и пристроить к любому свободному концу (после одного или нескольких ходов ряд может распасться на несколько звеньев).
Вот как это делается, например, при n = 3:
Как выглядит общее решение? При n = 1 решение тривиально. При n = 2 задача, как нетрудно выяснить, неразрешима. При всех n > 2 головоломка допускает решение не менее чем за n ходов.
Найти решение при n = 4 не так-то просто, и поиск его, несомненно, доставит вам немало удовольствия. Может быть, вам удастся сформулировать алгоритм решения головоломки за n ходов при любом n > 3.
Не меньший вызов любознательному читателю таят в себе многие необычные варианты той же головоломки. Приведем лишь некоторые из них.
1. Правила перемещения пар остаются теми же за одним исключением: если пара образована предметами различных типов, то перед тем, как пристроить ее к свободному концу, последовательность предметов в паре следует изменить. Например, перемещая две фишки, первая из которых (левая) красная, а вторая (правая) черная, их необходимо поменять местами, после чего первой станет черная, а второй красная фишка, и лишь после этого пристраивать к свободному концу. При 8 фишках существует решение в 5 ходов. При 10 фишках 5 ходов также оказывается достаточно. Общее решение неизвестно. Может быть, вам удастся найти его.
2. Правила такие же, как в исходной задаче, но фишек одного цвета на 1 меньше, чем другого, то есть фишек одного цвета n, а фишек другого n + 1. Доказано, что при любом n задачу можно решить за n² ходов, причем это число минимально.
