Есть идея! (Гарднер) - страница 15

Разрезав шахматную доску по диагонали и повернув половину, мы получим треугольник, изображенный на рис. 3. Числа, стоящие в клетках любого ряда, указывают число кратчайших путей, ведущих в них из самой верхней клетки. Расставленные в клетках числа образуют знаменитый арифметический треугольник Паскаля, и это не удивительно: алгоритм для подсчета числа кратчайших путей, ведущих от вершины, в точности совпадает с процедурой построения треугольника Паскаля. Этот изоморфизм позволяет считать исходную головоломку прологом к изучению необычайно разнообразных и красивых свойств треугольника Паскаля.

Треугольник Паскаля позволяет находить биномиальные коэффициенты (то есть коэффициенты при любом члене разложения (a + b)^>n, где n — любое целое число) и решения многих задач элементарной теории вероятностей. Заметим, что на рис. 3 число кратчайших путей, ведущих из вершины треугольника в самую левую или самую правую клетку нижнего ряда, равно 1 и что по мере приближения к середине ряда число кратчайших путей возрастает. Возможно, вам случалось видеть одно из устройств, действие которых основано на свойствах треугольника Паскаля: по наклонной доске, в которую в шахматном порядке вбиты колышки, скатываются шарики и скапливаются в отсеках под колышками нижнего ряда. Распределение шариков имеет форму колоколообразной кривой, а число шариков в каждом отсеке пропорционально соответствующему биномиальному коэффициенту, потому что число кратчайших путей, ведущих в каждый отсек, в точности совпадает с определенным биномиальным коэффициентом.

Алгоритм, предложенный Сьюзен, как нетрудно понять, остается в силе и для трехмерных сетей, в которых ячейки («кварталы») имеют форму прямоугольных параллелепипедов. Представьте себе куб с длиной ребра 3 единицы, разделенный на 27 единичных кубов. Будем считать его пространственной шахматной доской и в угловую «клетку» поместим ладью, которая может двигаться параллельно любому из ребер куба. Сколькими способами ладью можно перевести кратчайшим путем в клетку, расположенную на другом конце диагонали куба?

В одном родильном доме по чьему-то недосмотру перепутали карточки с именами 4 младенцев. У двух детей оказались их карточки, а карточки остальных двух малюток были разложены неправильно.