Мартин Гарднер - Есть идея!

Миссис Джонс не повезло: ее близнецы заметили автомат для продажи разноцветных шариков жевательной резинки прежде, чем миссис Джонс успела миновать его.

Первый близнец. Мама, купи мне жевательную резнику!

Второй близнец. И мне, и мне! Я хочу шарик такого же цвета, как у Билли.

Автомат был почти пуст. Предугадать, какого цвета шарик выпадет, если опустить в щель автомата монету в 1 пенс, невозможно. Сколько однопенсовых монет придется приготовить миссис Джонс, чтобы из купленных шариков заведомо можно было выбрать 2 шарика одного и того же цвета?

Потратив 6 пенсов, миссис Джонс заведомо могла бы извлечь из автомата 2 красных шарика; 4 пенса ушли бы на «добывание» 4 белых шариков, а 2 пенса — на 2 красных шарика. Израсходовав 8 пенсов, миссис Джонс заведомо получила бы 2 белых шарика. Следовательно, миссис Джонс необходимо приготовить 8 центов. Правильно?

Нет, не верно! Если бы первые два шарика, выкатившиеся из автомата, были разного цвета, третий шарик непременно совпал бы по цвету с одним из них. Следовательно, миссис Джонс необходимо приготовить всего лишь 3 пенса.

Предположим теперь, что в автомате осталось 6 красных, 4 белых и 5 синих шариков. Сможете ли вы подсчитать, сколько монет в 1 пенс следует приготовить миссис Джонс, чтобы среди выкатившихся из автомата шариков заведомо нашлось 2 шарика одного и того же цвета?

По-вашему, ей хватит 4 центов? А что вы скажете о бедной миссис Смит, которая безуспешно пыталась отвлечь от автомата для продажи жевательной резинки внимание своей тройни?

На этот раз в автомате находились 6 красных, 4 белых шарика и лишь 1 синий шарик. Сколько монет достоинством в 1 пенс следует приготовить миссис Смит, чтобы среди купленных шариков заведомо были 3 шарика одного цвета?

Вторая задача о шариках жевательной резинки лишь незначительно отличается от первой. Идея решения второй задачи по существу та же: первые три шарика могут быть разного цвета (например, один шарик может быть красным, один синим и один белым). Это наименее благоприятный случай, так как к достижению желаемого результата ведет самая длинная последовательность испытаний. Четвертый шарик заведомо совпадает по цвету с одним, из трех первых шариков. Итак, чтобы 2 шарика оказались одного и того же цвета, необходимо купить 4 шарика. Следовательно, миссис Джонс следует приготовить 4 цента.

Обобщение на случай 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 из них заведомо были одной масти?