Кто назовет 20?

Первый игрок называет одно из двух чисел — 1 или 2. На каждом шаге игроки по очереди прибавляют к результату 1 или 2. Выигрывает тот, кто первым назовет число 20. Существует выигрышная стратегия для этой игры или нет? Что изменится, если вместо 20 для победы нужно будет назвать 83 или 100?

Лабиринт в саду Роуз Болла

Благодаря занимательным задачам У. У. Роуз Болла, популярность получили многие разделы математики. В знаменитом лабиринте Болла стрелками отмечены вход и выход, а точкой — место, где лежат сокровища. Можно ли добраться до них? Попробуйте не подсматривать ответ, а найти решение сами. Получилось? Найденный маршрут будет состоять из линий и точек, обозначающих повороты. Каждое ребро полученного графа нужно пройти дважды (туда и обратно), поэтому все вершины маршрута должны иметь степень 2. Чтобы найти требуемый маршрут, достаточно отмечать коридоры, которые мы уже прошли, чтобы не терять времени понапрасну.

Лабиринт Роуз Болла.

Игра «змейка»

В этой игре, которую придумал Дэвид Сильверман, два игрока по очереди проводят единичные отрезки на сетке размерами 5x5 или 6x6 точек (размер игрового поля может быть произвольным). Отрезки можно добавлять только в начало и конец «змейки». Проигрывает тот, кто вынужден построить цикл. Существует ли выигрышная стратегия для этой игры?

Изящная нумерация графа

В этой игре Соломона Голомба нужно построить граф и подписать его вершины различными целыми положительными числами (или нулем). Вершины нужно пронумеровать так, чтобы разности чисел, присвоенных соседним вершинам, не совпадали, и при этом наибольший номер вершины был как можно меньшим числом.

Ханойские башни

В этой игре, придуманной Эдуардом Люка в 1883 году (и окруженной мнимыми легендами), на три стержня нанизаны п колец разного размера, упорядоченные от меньшего к большему. Большее кольцо не может располагаться поверх меньшего. Нужно переместить кольца так, чтобы восстановить исходную пирамиду на третьем стержне. На каждом ходу можно перемещать только одно кольцо.

Начальное положение колец в игре «Ханойские башни».

Число решений для n колец равно 2ⁿ  — 1. С увеличением n число решений стремительно возрастает. Чтобы определить правильную последовательность ходов, можно использовать графы. Интерактивные версии этой игры есть в интернете.

Игра Ним

Два игрока располагают фишки в несколько групп. Первый игрок может взять любое число фишек из одной группы. Затем второй игрок берет любое число фишек из любой оставшейся группы и так далее. Выигрывает тот, кто забирает последнюю фишку.

Две цепи Мартина Гарднера

Мартин Гарднер, который обожал задачи с плоскими графами, предложил множество подобных задач своим читателям со всего мира. Стремясь показать, как плоские графы используются в электрических цепях, Гарднер придумал задачи, в которых точки (вершины) графа нужно соединить линиями так, чтобы получился плоский граф, то есть избежать пересечений (если две линии пересекаются в точке, которая не является вершиной графа, возникает короткое замыкание). Мы предлагаем читателю решить следующие задачи (ответы приводятся в конце главы на стр. 122).

Цепь в прямоугольнике

В этом прямоугольнике нужно провести пять линий, соединяющих А и A, В и В, С и С, D и D, E и E, не пересекая отрезки AD и ВС, отмеченные на рисунке, и не выходя за границы прямоугольника.

Цепь на квадратной сетке

На этой сетке размерами 7 x 7 клеток нужно провести вдоль линий сетки пять непересекающихся линий так, чтобы соединить точки, обозначенные одинаковыми буквами.

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

* * *

МАРТИН ГАРДНЕР (1914–2010)

Среди звездных авторов научно-популярной литературы особенно ярко блистает звезда Мартина Гарднера. Он родился в городе Талса, штат Оклахома, США, изучал философию, но после окончания университета занялся журналистикой. Много лет, с 1956 по 1986 год, он был автором ежемесячной рубрики «Математические игры» в журнале Scientific American. В этой рубрике и в своих многочисленных книгах он рассказывал о математике, играх, алгоритмах, парадоксах и головоломках.

Кроме этого, он писал о философии, научных исследованиях в различных областях, а также был автором комментариев ко многим книгам. Любопытно, что Гарднер не выступал на конференциях и не преподавал, уделяя все время написанию книг и статей.

Обложка одной из многочисленных книг Мартина Гарднера.

* * *

Маршрут коня на шахматной доске

Шахматная доска используется во множестве математических задач. Классическими являются задачи о перемещении различных фигур (пешки, слона, ладьи, ферзя) по шахматной доске. Особый интерес представляет следующий вопрос: может ли шахматный конь пройти по всем 64 клеткам доски ровно один раз и вернуться в исходную клетку?

Эта задача имеет решение; более того, оно не является единственным. Эту головоломку, как и многие другие шахматные задачи, можно решить с помощью теории графов. Каждая клетка доски соответствует вершине графа, ход коня — ребру, соединяющему две вершины графа. Следовательно, задача сводится к нахождению гамильтонова цикла в этом графе.

Маршрут коня по шахматной доске.

Математики не стали ограничиваться стандартной доской размером 8 x 8 клеток и рассмотрели возможность обхода досок размерами 5 x 5, 6 x 6, 3 x 10 клеток и других. Эти задачи представляют собой задачи на поиск гамильтоновых цепей в графах, число вершин которых равняется n x m. Например, для доски 6 x 6 клеток задача имеет решение, для досок 5 x 5 или 2 x 8 — нет.

Интересной читателю будет и задача о поиске маршрута шахматной ладьи из одного угла доски в диагонально противоположный, проходящего через все клетки. Можно рассмотреть доску размерами 7 x 7 клеток или общий случай — n x n клеток.

Простая игра в шахматы может подарить вам огромное множество интересных задач.

Льюис Кэрролл и эйлеровы графы

Чарльз Лютвидж Доджсон (1832–1898), известный под псевдонимом Льюис Кэрролл, был не только автором «Алисы в стране чудес», но и любителем занимательных математических задач. Он любил придумывать остроумные головоломки, которые мог решить даже ребенок. Некоторые из его задач сегодня изучаются в теории графов, хотя в его эпоху к теории графов относили лишь задачи, где нужно было нарисовать заданную фигуру, не отрывая карандаша от бумаги. Самой известной из подобных задач Кэрролла является задача о трех квадратах, показанных на рисунке. Сможете ли вы обойти этот граф, не отрывая карандаша от бумаги и не проводя ни одну линию дважды?

Томас О’Бейрн придумал удивительный метод решения подобных задач, который заключается в том, что нужно раскрасить смежные области чередующимися цветами (см. рисунок) и тем самым «разделить» области, чтобы найти искомый путь. Маршрут обхода становится очевидным, и можно легко провести карандашом нужный путь на исходном графе.

Задача о четырех окружностях

Спустя много лет после Кэрролла О’Бейрн придумал похожую задачу, заменив три квадрата четырьмя пересекающимися окружностями, которые образуют красивую симметричную фигуру.

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

Магические звезды

Магические звезды — удивительная игра из области занимательной комбинаторики, в которой смешались графы и числа.

На рисунке изображена пятиугольная звезда — символ школы пифагорейцев. Десять ее вершин обозначены кругами. Можно ли расположить в вершинах звезды числа от 1 до 10 так, чтобы сумма чисел во всех рядах из четырех вершин была одинаковой? Эта сумма чисел называется магической константой. Попробуйте решить задачу, прежде чем продолжить чтение. Чему равна магическая константа для пятиугольной звезды?

Не получается? Не беспокойтесь. Вам не удается найти решение, потому что его не существует. Обратите внимание, что сумма чисел от 1 до 10 равна 55. Так как каждое число находится в двух линиях звезды, общая сумма чисел на всех линиях будет в два раза больше, чем 55, то есть 110. Следовательно, магическая константа должна равняться 110/5, то есть 22. Остается распределить числа так, чтобы их сумма в каждом ряду равнялась 22.

Иан Ричардс заметил: каждая из линий, в одной из вершин которой находится число 1, должна содержать, помимо единицы, еще три числа, которые в сумме дают 21. Следовательно, сумма чисел на двух этих линиях равна 42, поэтому 10 должно находиться в одном ряду с 1 (шесть чисел, среди которых нет 10, в сумме могут давать максимум 4 + 5 + 6 + 7 + 8 + 9 = 39). Пусть А — линия, на которой находятся 1 и 10, В — другая линия с вершиной 1, С — другая линия с вершиной 10. Тогда числа на линии А можно расположить четырьмя возможными способами. Если на одной из линий будут располагаться 1, 10, 4, 7, то поместить числа на В и С будет невозможно. Следовательно, остаются три случая:

Магическая гексаграмма

Рассмотрим магическую гексаграмму. Гексаграмма — это знаменитая и легендарная Звезда Давида и Печать Соломона, образуемая наложением двух равносторонних треугольников друг на друга.

Как видно на рисунке, эта фигура имеет 12 вершин, расположенных в шесть рядов по четыре вершины, поэтому в этой задаче нужно присвоить вершинам числа от 1 до 12. Так как сумма чисел от 1 до 12 равна 78, магическая константа будет равна 78·2/6, то есть 26. Сосредоточьтесь, приготовьте карандаш и найдите одно из нескольких десятков решений этой задачи. В конце главы (стр. 122) приведено одно из возможных решений.

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

Более простой альтернативой этой задаче, для которой существует строгий алгоритм решения, являются магические окружности — несколько окружностей, в точках пересечения которых нужно расположить числа так, чтобы сумма чисел на каждой окружности была одинаковой, например 20. На следующем рисунке изображены три окружности, точки пересечения которых обозначены буквами а, b, с, d, р, q. Можно записать соотношения, которые должны выполняться для чисел, соответствующих этим вершинам.

Получим систему уравнений:

a + b + c + d = 20,

с + d + р + q = 20,

а + Ь + р + q = 20.

Сложив все три уравнения, получим:

2а + 2Ь + 2с + 2d + 2р + 2q = 60,

или, что аналогично,

a + b + c + d + q = 30.

Вычтем из последнего равенства все три исходных равенства и получим:

a + b = c + d = p + q = 10.

Следовательно, существует множество различных вариантов, например:

а = 1, Ь = 9, с = 2, d = 8, р = 3, q = 7.

* * *