Иэн Стюарт - Математические головоломки профессора Стюарта

Однако я человек упрямый.

– В этом деле нет ни одной зацепки, Сомс.

– Оно такое не одно, – мрачно пробормотал он.

– Нет, я имею в виду… вообще никаких указаний, ни одной улики.

Вот теперь мои слова его наконец заинтересовали, я ясно это видел. Он взял газету из моей протянутой руки и взглянул на диаграмму.

– В данном случае правила очевидны, Ватсап, хотя их здесь и нет.

– Почему?

– Они должны быть достаточно простыми, чтобы мотивировать читателя к разгадыванию загадки, но создавать при этом достаточно сложную задачу, способную удержать интерес.

– Несомненно. Так какие же здесь правила, Сомс?

– Ясно, что в каждой строке и в каждом столбце должны содержаться числа 1, 2, 3 и 4 ровно по одному разу каждое.

– Ах! Так это комбинаторная задачка, разновидность латинского квадрата.

– Да, но этого мало. Очевидно, что важны также две области, разграниченные жирной черной линией. Я предполагаю, что числа в той и другой области при сложении должны давать одинаковую сумму… Да, тогда решение будет единственным.

– Ага! Интересно, какое это решение.

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

Ответ см. в главе «Загадки разгаданные». Если вас заинтересовали задачи без указаний, то их дополнительные примеры вы найдете в главе «Дверца страха».

Современные читатели узнают в головоломке Ватсапа один из вариантов судоку. (На случай, если вы только что вернулись из сорокалетней экспедиции на Проксиму Центавра, поясню: это квадрат 9 × 9, разделенный на 9 блоков 3 × 3, причем в некоторых клетках заранее проставлены цифры. Нужно заполнить остальные клетки таким образом, чтобы в каждой строке, каждом столбце и каждом блоке содержались все цифры от 1 до 9.)

Похожие, но существенно различающиеся головоломки известны давно и имеют долгую историю, восходящую к китайцу Ло Шу и его магическому квадрату, который он будто бы увидел на спине черепахи примерно в 2100 г. до н. э. Книга «Математические и физические развлечения» Жака Озанама, написанная в 1725 г., включала в себя головоломку на тему карточной игры, чуть более близкую к судоку. Возьмите 16 фигурных карт (это туз, король, дама и валет) и выложите их квадратом так, чтобы в каждом ряду и каждом столбце содержались карты всех мастей и достоинств. Кэтлин Оллереншоу показала, что существует 1152 решения этой задачи, которые сводятся всего лишь к двум принципиально разным вариантам, если считать, что два решения совпадают, если одно может быть получено из другого перестановкой мастей или достоинств. Существует 24 × 24 = 576 способов сделать это с любым заданным решением, а 1152/576 = 2.

Сможете ли вы найти эти два принципиально разных решения? Ответ см. «Загадки разгаданные».

В 1782 г. Эйлер опубликовал задачу о 36 офицерах: можно ли построить офицеров шести полков, в каждом из которых по шесть офицеров разных рангов, в каре (то есть квадратом) 6 × 6 таким образом, чтобы в каждой шеренге и в каждой колонне присутствовали офицеры всех рангов из всех полков? Подобные расстановки получили название греко-латинских квадратов, потому что латинские (A, B, C, …) и греческие (α, β, γ, …) буквы можно использовать для обозначения рангов и полковой принадлежности. Эйлер нашел методы построения греко-латинских квадратов, порядок которых (то есть размер квадрата) является нечетным числом или имеет двойную четность, то есть кратен четырем.

Эйлер предположил, что для порядка, выражаемого удвоенным нечетным числом, таких квадратов не существует. Для порядка 2 это очевидно, а в 1901 г. Гастон Тарри доказал это для порядка 6. Однако в 1959 г. Радж Чандра Бозе и Шарадчандра Шанкар Шриханде сумели при помощи компьютера отыскать греко-латинский квадрат порядка 22, а Эрнест Паркер нашел такой квадрат порядка 10. После этого все трое доказали, что гипотеза Эйлера неверна для всех удвоенных нечетных чисел, больших или равных 10.

Квадратные таблицы размером n × n, такие, что каждая строка и каждый столбец содержит все числа от 1 до n (каждое, понятно, по одному разу), получили известность как латинские квадраты, а греко-латинские квадраты были переименованы в ортогональные латинские квадраты. Эти темы входят в область математики, которую называют комбинаторикой, и применяются в области коммуникаций, в экспериментальном дизайне и при составлении расписаний всевозможных соревнований.