Треугольник Паскаля позволяет находить биномиальные коэффициенты (то есть коэффициенты при любом члене разложения (a + b)n, где n — любое целое число) и решения многих задач элементарной теории вероятностей. Заметим, что на рис. 3 число кратчайших путей, ведущих из вершины треугольника в самую левую или самую правую клетку нижнего ряда, равно 1 и что по мере приближения к середине ряда число кратчайших путей возрастает. Возможно, вам случалось видеть одно из устройств, действие которых основано на свойствах треугольника Паскаля: по наклонной доске, в которую в шахматном порядке вбиты колышки, скатываются шарики и скапливаются в отсеках под колышками нижнего ряда. Распределение шариков имеет форму колоколообразной кривой, а число шариков в каждом отсеке пропорционально соответствующему биномиальному коэффициенту, потому что число кратчайших путей, ведущих в каждый отсек, в точности совпадает с определенным биномиальным коэффициентом.
Алгоритм, предложенный Сьюзен, как нетрудно понять, остается в силе и для трехмерных сетей, в которых ячейки («кварталы») имеют форму прямоугольных параллелепипедов. Представьте себе куб с длиной ребра 3 единицы, разделенный на 27 единичных кубов. Будем считать его пространственной шахматной доской и в угловую «клетку» поместим ладью, которая может двигаться параллельно любому из ребер куба. Сколькими способами ладью можно перевести кратчайшим путем в клетку, расположенную на другом конце диагонали куба?
Перепутали
В одном родильном доме по чьему-то недосмотру перепутали карточки с именами 4 младенцев. У двух детей оказались их карточки, а карточки остальных двух малюток были разложены неправильно.
Сколько существует различных вариантов путаницы?
Подсчитать число вариантов совсем нетрудно, если составить таблицу. Оказывается, что карточки с именами 2 детей из 4 можно перепутать лишь 6 различными способами.
Предположим теперь, что после того, как карточки перепутали, у трех детей оказались карточки с их именами, а одному младенцу досталась карточка с чужим именем. Сколько вариантов путаницы существует в этом случае?
Как бы вы стали решать эту задачу? Составили бы таблицу? А может быть, у вас есть идея, как решить эту задачу проще?
Многим кажется, что ответить на вопрос задачи довольно трудно. Те, кто так думает, ошибочно полагают, будто перепутать карточки так, чтобы 3 младенцам из 4 достались карточки с их именами, можно многими способами. Но стоит лишь обратиться к принципу «птичка в клетке» и сформулировать задачу несколько иначе, как ответ сразу становится очевидным. Предположим, что перед нами 4 клетки и на каждой из них укреплена карточка с названием одного из 4 предметов. Если 3 предмета попали в клетки со своими названиями, то четвертому предмету не остается ничего другого, как попасть в клетку, к которой прикреплена карточка с его названием. Таким образом, мы имеем дело лишь с одним вариантом: каждый из 4 предметов оказывается в своей клетке.
Во многих книгах по занимательной математике встречается следующая задача, в которой речь идет лишь о 3 предметах. На столе расставлены 3 закрытые коробки. В одной из них находятся 2 монеты по 5 центов, в другой — 2 монеты по 10 центов и в третьей — 1 пятицентовая и 1 десятицентовая монета. На крышках коробок написано: 10 центов; 15 центов и 20 центов, но ни одна из надписей не соответствует содержимому коробки. Предположим, что из коробки с надписью «15 центов» (напомним, что надпись не соответствует содержимому коробки) извлекли 1 монету и положили на стол перед коробкой. Можно ли, взглянув на эту монету, сказать, какие монеты находятся в каждой из 3 коробок?
Как и в предыдущей задаче, многих вводит в заблуждение кажущаяся неоднозначность выбора: они думают, будто существует довольно много вариантов решения, тогда как на самом деле задача допускает единственное решение. Монета, извлеченная из коробки с надписью «15 центов» (не соответствующей содержимому), может быть монетой достоинством либо в 5 центов, либо в 10 центов. Если извлечена монета достоинством в 5 центов, то в коробке первоначально находились 2 монеты по 5 центов. Если извлечена монета достоинством в 10 центов, то в коробке первоначально находились 2 монеты по 10 центов. И в том и в другом случае содержимое остальных двух коробок восстанавливается однозначно. Нетрудно видеть, что не соответствующие содержимому каждой коробки надписи оставляют лишь 2 варианта распределения монет по: коробкам. После того как из коробки с ложной надписью «15 центов» извлечена 1 монета, один вариант исключается, и остается единственный допустимый вариант, соответствующий правильному решению.
Иногда встречается несколько более сложная разновидность той же задачи. Содержимое всех трех коробок требуется определить, извлекая наименьшее число монет (из любой коробки). Единственное решение задачи состоит в том, чтобы из коробки с надписью «15 центов» извлечь 1 монету. Может быть, вам удастся придумать более сложные варианты задачи: в одной коробке могут находиться более 2 монет, да и самих коробок может быть более 3.
С задачей о младенцах тесно связано немало других задач на сообразительность, так же, как и исходная задача, приводящих к элементарной теории вероятностей. Например, если карточки с именами младенцев перемешаны наугад, то какова вероятность, что у всех 4 младенцев окажутся карточки с их именами? С какой вероятностью у всех 4 младенцев карточки не будут соответствовать их именам? Какова вероятность, что по крайней мере у 1 младенца окажется карточка с его именем? Какова вероятность, что ровно у 1 младенца окажется карточка с его именем? Какова вероятность, что. по крайней мере у 2 младенцев окажутся карточки с их именами? Какова вероятность, что ровно у 2 младенцев окажутся карточки с их именами? Какова вероятность, что не более чем у 2 младенцев окажутся карточки с их именами? И так далее.
Вопрос о «по крайней мере одном» — независимо от того, о чем идет речь, — один из классических вопросов занимательной математики. Довольно часто его облекают в форму задачи об n посетителях ресторана, сдавших шляпы в гардероб. Рассеянный гардеробщик выдал посетителям номера наугад, нимало не заботясь о том, кому достанется номерок от шляпы — ее владельцу или кому-нибудь другому. Какова вероятность, что по крайней мере один посетитель получит свою шляпу? Оказывается, что при возрастании n эта вероятность быстро стремится к 1 — (1/e), то есть немногим больше ½. Здесь e — знаменитая иррациональная константа (число Эйлера), равная 2,71828… В задачах теории вероятностей она встречается так же часто, как число π в геометрических задачах.
Стаканы профессора Квиббла
У профессора Квиббла имеется для вас задача-головоломка.
Проф. Квиббл. Возьмите 3 стакана для сбивания молочного коктейля и попробуйте разложить по ним 11 монет так, чтобы в каждом стакане число монет было нечетным.
Проф. Квиббл. Задачка не из трудных, не так ли? И решений она допускает много. Например, в один стакан можно положить 3 монеты, в другой — 7 монет, а в третий — 1 монету.
Проф. Квиббл. А сумеете ли вы разложить по тем же 3 стаканам 10 монет так, чтобы число монет в каждом стакане было нечетным? Сделать это можно, хотя и не просто!
Проф. Квиббл. Надеюсь, вы не отступили перед трудностями? Вам нужно было лишь догадаться вставить один стакан в другой. После этого уже совсем нетрудно разложить монеты так, чтобы в каждом стакане оказалось нечетное число монет.
Счастливая идея, позволяющая сразу же решить головоломку проф. Квиббла, сводится к тому, что одни и те же монеты могут одновременно находиться более чем в одном стакане. На языке теории множеств решение задачи допускает следующее описание: имеется два множества монет, одно из которых содержит 7 элементов, а другое — 3 элемента, причем в последнем множестве выделено подмножество, содержащее 1 элемент. Наглядно полученное решение можно изобразить в виде следующей диаграммы:
Найти все остальные решения мы предоставляем читателю. Додуматься до 10 решений, одно из которых предложил проф. Квиббл, не составит особого труда, но найти еще 5 решений (всего существует 15 решений задачи) не так-то просто: необходимо «озарение».
После того как вам удастся найти все 15 решений, попробуйте обобщить задачу, варьируя число монет, стаканов и отличительные особенности числа монет, разложенных по стаканам.
Основная идея «счастливой находки», позволившей решить задачу проф. Квиббла (элементы какого-то множества принадлежат другому множеству и при подсчете учитываются дважды), встречается во многих известных головоломках и парадоксах. Приведем лишь одну из таких задач, носящую шуточный характер.
После того как один школьник пропустил целую неделю занятий, его навестил учитель. Школьник принялся объяснять, почему ему некогда ходить в школу.
— Я сплю 8 часов в сутки. Это составляет 8 × 365 = 2920 часов в году, или, так как в сутках 24 часа, 2920: 24 (около 122) суток.
По субботам и воскресеньям школа не работает, что составляет за год 104 дня.
60 дней в году приходятся на летние каникулы.
На завтрак, обед и ужин у меня уходит 3 часа в день, то есть 3 × 365 = 1095 часов, или 1095: 24 (около 45 суток) в год.
По крайней мере 2 часа в день мне необходимы для отдыха, что составляет 2 × 365 = 730 часов, или 730: 24 (около 30 суток) в год.
Школьник выписал названные им числа в столбец и просуммировал:
На сон — 122
Субботы и воскресенья — 104
Летние каникулы — 60
Завтраки, обеды и ужины — 45
Отдых — 30
Итого — 361 день
— Видите, — продолжал школьник, — у меня остается всего-навсего 4 дня в год на болезни, а о праздниках я и не говорю!
Учитель внимательно проверил все выкладки, но не смог обнаружить в них ошибки. Проверьте этот парадокс на своих приятелях. Многие из них сумеют найти ошибку? А ошибка кроется в том, что некоторые подмножества дней года сосчитаны более одного раза: множества, на которые школьник разбил 365 дней в году, перекрываются (пересекаются) так же, как множества монет в стаканах проф. Квиббла.