Есть идея!

Обобщение на случай n множеств шариков (каждое множество составляют шарики одного цвета) очевидно: если имеется n множеств шариков, то следует быть готовым к тому, что придется купить n + 1 шариков (чтобы 2 шарика заведомо были одного и того же цвета).

Третья задача потруднее двух предыдущих. У миссис Смит не близнецы, а тройня. В автомате находятся б красных, 4 белых шарика и 1 синий шарик. Сколько монет достоинством в 1 цент должна приготовить миссис Смит, чтобы среди шариков, выданных автоматом, заведомо были 3 шарика одного цвета?

Как и прежде, начнем с рассмотрения наименее благоприятного случая. Миссис Смит может получить из автомата 2 красных, 2 белых шарика и 1 синий шарик, то есть всего 5 шариков. Шестой шарик должен быть либо красным, либо белым и, следовательно, подходить по цвету к ранее выпавшим из автомата либо 2 красным, либо 2 белым шарикам. Значит, миссис Смит должна приготовить 6 центов. Если бы синих шариков в автомате было не меньше двух, то в наименее благоприятном случае миссис Смит могла бы сначала извлечь из автомата по 2 шарика каждого цвета, и, чтобы получить 3 шарика одного и того же цвета, ей непременно понадобился бы седьмой шарик.

«Неожиданное» решение — это своего рода «прозрение», позволяющее оценить длину серии испытаний в наименее благоприятном случае. Ту же задачу можно было бы решить и более сложным способом: обозначить каждый из 11 шариков «своей» буквой, выписать все возможные варианты выдачи шариков из автомата и установить, в каком случае длина цепочки испытаний до появления трех шаров одного цвета имеет наибольшую длину. Но при таком решении потребовалось бы перебрать 11! = 39 916 800 последовательностей всех возможных исходов испытаний. Если мы условимся не различать шары одного цвета, то и тогда при таком подходе пришлось бы перебрать 2310 последовательностей возможных исходов.

Обобщение задачи на случай, когда требуется определить наименьшее число монет, при котором из выданных автоматом шаров заведомо можно выбрать k шариков одного цвета, приводит к следующему решению. Если имеются шары n цветов (шаров каждого цвета не меньше k), то для получения k шаров одного цвета необходимо выбрать не более n(k ? 1) + 1 шаров. Читателю доставит удовольствие самостоятельно исследовать, что произойдет в том случае, если шаров одного или нескольких цветов будет меньше k.

Задачи этого типа можно промоделировать не только на автоматах для продажи жевательной резинки, но и многими другими способами. Например, сколько карт необходимо вытащить из колоды в 52 листа, чтобы 7 карт заведомо были одной масти? Здесь n = 4, k = 7, и наша формула дает ответ? 4(7–1)+1=25.

Мы рассмотрели лишь очень простые комбинаторные задачи, но и они приводят к интересным и трудным вопросам теории вероятностей. Например, какова вероятность извлечь 7 карт одной масти, если вы вытаскиваете из колоды, не возвращая, n карт, где n — любое число от 7 до 24? (Вероятность извлечь 7 карт одной масти, очевидно, равна 0, если из колоды вытащить менее 7 карт, и равна 1, если вытащить более 24 карт). Как изменятся вероятности, если мы условимся возвращать каждую извлеченную карту и тщательно тасовать колоду перед тем, как вытягивать из нее очередную карту? Более трудный вопрос: каково математическое ожидание (среднее по длинной серии испытаний) числа карт, которые необходимо извлечь (с возвратом или без возврата) из колоды, чтобы k из них заведомо были одной масти?

Турнир по настольному теннису

Пять членов клуба любителей настольного тенниса средней школы им. Милларда Филмора решили провести между собой турнир по олимпийской системе.

Тренер составил таблицу розыгрыша турнира, снабдив ее следующими пояснениями.

Тренер. Пять — число нечетное, поэтому в первой круге один участник турнира свободен от игры. Еще один участник свободен от игры во втором круге. Таким образом, всего за турнир будет сыграно 4 партии.

На следующий год в спортивный клуб записалось 37 школьников. Тренер снова составил таблицу розыгрыша турнира, постаравшись свести до минимума число участников, которые переходят в следующий круг без игры. Сколько партий было сыграно за весь турнир на этот раз?

Как, вы еще не сосчитали? А ведь задача решается просто! В каждой партии проигравший выбывает, а поскольку дли того, чтобы определить победителя, следует исключить всех участников, кроме одного, то за весь турнир должно состояться 36 партий. Не правда ли, все очень просто?

Сколько участников турнира перейдут в следующий круг без игры?

Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа n всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?

При заданном n число участников, остающихся без партнера, можно определить следующим образом. Вычтем из n наименьшую степень числа 2, которая больше или равна n. Полученную разность запишем в двоичной системе. Число единиц в двоичной записи и будет равно числу участников турнира, вынужденных перейти в следующий круг без игры из-за нехватки партнера. В нашей задаче мы вычтем 37 из 64 (то есть из 2⁶) и получим разность, равную 27. Десятичное число 27 в двоичной системе имеет вид 11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.

Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из n элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно n ? 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.

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

Стаканчики профессора Квиббла

Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.