Читать «Есть идея!» онлайн - страница 8

По-вашему, ей хватит 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.