Ответ, а также результат гонки Оксфорд – Кембридж 1877 г. см. в главе «Загадки разгаданные».
«Пятнашки»
Эта старая головоломка – моя любимая, она никогда не надоедает. Это увлекательное занятие, где маленькая математическая догадка могла бы избавить нас от невероятного количества напрасных усилий. Плюс к тому она нужна мне в качестве подготовки к следующей теме.
В 1880 г. нью-йоркский почтмейстер по имени Ной Палмер Чепмэн предложил головоломку, которую он назвал «драгоценной», а дантист Чарльз Певи предложил денежный приз за ее решение. Головоломка ненадолго вошла в моду, но никто не сумел выиграть приз, так что ажиотаж быстро спал. Американский составитель головоломок Сэм Лойд[34] утверждал, что именно он ввел моду на эту головоломку в 1870-е гг., но на самом деле все, что он сделал, – это написал о ней в 1896 г. и предложил приз в $1000 за решение, что на время воскресило интерес к полузабытой игре.
Головоломка «пятнашки» (ее также называют игрой в «15» и «загадочным квадратом») начинается с 15 подвижных квадратиков, пронумерованных числами от 1 до 15 и расставленных в форме квадрата с одним пустым квадратиком в правом нижнем углу. Квадратики расставлены в порядке возрастания, за исключением номеров 14 и 15. Задача играющего – поменять местами квадратики 14 и 15, сохранив положение остальных квадратиков неизменным. Делать это нужно сдвиганием любого из соседних квадратиков на пустое место, причем повторять эту операцию можно сколько угодно.
По мере того как вы сдвигаете все больше и больше квадратиков, номера перепутываются. Но если вы будете действовать аккуратно, вы сможете вновь их распутать. Легко предположить, что при достаточной сообразительности можно получить любое, абсолютно произвольное расположение квадратиков.
Лойд с радостью предложил такой щедрый по тем временам приз, поскольку был уверен, что платить не придется. В игре существует 16! потенциально возможных перестановок (15 нумерованных квадратиков плюс один пустой). Вопрос в следующем: какие из этих вариантов можно получить при помощи серии разрешенных ходов? В 1879 г. Уильям Джонсон и Уильям Стори доказали, что ответ состоит в том, что получить можно ровно половину вариантов; причем (так мы и знали, не правда ли?) вариант, который нужен для получения приза, относится к другой половине. «Пятнашка» нерешаема. Но люди в большинстве своем этого не знали.
Для доказательства невозможности решения нужно раскрасить квадратики под шахматную доску, как на правом рисунке. Сдвиг любого квадратика, по существу, меняет его местами с пустым квадратиком, и всякий раз при этом меняется цвет, связанный с пустым квадратиком. Поскольку в результате пустой квадратик должен вернуться на свое первоначальное место, число шагов должно быть четным. Вообще, любая расстановка может быть получена путем серии обменов, но некоторые комбинации требуют четного числа обменов, а некоторые – нечетного.
Существует множество способов получить любую заданную расстановку, но они либо все четные, либо все нечетные. Желаемый результат может быть получен при помощи всего лишь одной замены (нужно поменять местами 14 и 15), но единица – число нечетное, так что получить такую расстановку четным числом замен невозможно.
Это условие оказывается единственным препятствием: разрешенные ходы позволяют получить ровным счетом половину из 16! возможных расстановок. 16!/2 = 10 461 394 944 000; это число настолько велико, что, сколько бы раз вы ни пробовали, бо́льшая часть вариантов останется неисследованной. Это может заронить в ваше сознание мысль, что возможен, безусловно, любой вариант расстановки.
Хитрая шестиугольная головоломка
В 1974 г. Ричард Уилсон обобщил «пятнашки» и доказал замечательную теорему. Он заменил сдвижные квадратики сетью. Квадратики здесь представлены числами, которые могут скользить по ребру, если оно соединено с узлом, на котором в данный момент располагается пустой квадратик. При этом пустой квадратик перемещается на новую позицию. Приведенная на рисунке фигура показывает начальное расположение блоков головоломки. Узлы связаны, если соответствующие им квадратики располагаются по соседству.
Идея Уилсона состоит в том, чтобы заменить эту сеть вообще любой связанной сетью. Предположим, в ней n + 1 узлов. Первоначально один из узлов, отмеченный квадратиком, считается пустым (назовем его узлом 0), а остальные пронумерованы номерами от 1 до n. Смысл головоломки в том, чтобы двигать эти числа (номера) по сети, меняя местами 0 с номером одного из прилегающих узлов. Правилами оговаривается, что в конце концов 0 вновь должен оказаться в начальной точке. Остальные n чисел могут быть расставлены по сети n! способами. Уилсон задал вопрос: какая доля этих способов может быть получена посредством разрешенных ходов? Ответ, очевидно, зависит от сети, но в меньшей степени, чем можно было бы предположить.
Существует один очевидный класс сетей, для которых ответ оказывается необычно маленьким. Если узлы образуют замкнутое кольцо, то единственное положение, которое можно получить разрешенными ходами, – это начальное положение, поскольку 0 по условию должен вернуться в начальную точку. Все остальные числа будут расставлены в прежнем циклическом порядке; не существует способа, посредством которого один номер может обогнуть другой и оказаться с другой его стороны. Теорема Рика Уилсона (названная так, чтобы избежать путаницы с другим математическим Уилсоном) утверждает, что если оставить в стороне кольцевые сети, то в любой другой сети могут быть получены либо все перестановки без исключения, либо ровно половина (только четные).
Ровно за одним замечательным исключением.
В теореме содержится сюрприз. Уникальный сюрприз: сеть с семью узлами. Шесть из них образуют шестиугольник, а один располагается посередине, на одном из диаметров. В этой сети возможно 6! = 720 перестановок; соответственно, половина равна 360. Но в реальности получить можно только 120.
В рассуждениях используется абстрактная алгебра, а именно некоторые элегантные свойства групп перестановок. Подробности см.: Alex Fink and Richard Guy, Rick's tricky six puzzle: S5 sits specially in S6, Mathematics Magazine 82 (2009) 83–102.
Сложно, как азбука
Время от времени математикам на ум приходят безумные, на первый взгляд, идеи, влекущие за собой, как оказывается позже, громадные последствия. ABC-гипотеза – из их числа.
Помните Великую теорему Ферма? В 1637 г. Пьер де Ферма высказал гипотезу о том, что если n³ 3, то уравнение Ферма
an + bn = cn
не имеет ненулевых целых решений. С другой стороны, при n = 2 таких решений бесконечно много, вспомнить хотя бы пифагорову тройку 3² + 4² = 5². Прошло 358 лет, прежде чем правоту Ферма доказали Эндрю Уайлс и Ричард Тейлор (см. «Кабинет…» с. 50).
Дело сделано, можно было бы подумать. Но в 1983 г. Ричард Мейсон вдруг понял, что никто и никогда не рассматривал внимательно Великую теорему Ферма для первых степеней:
a + b = c.
Не нужно быть алгебраическим гением, чтобы найти решения этого уравнения: 1 + 2 = 3, 2 + 2 = 4. Но Мейсон задумался, не станет ли этот вопрос интереснее, если наложить на a, b и c более серьезные ограничения. В результате возникла новая блестящая догадка и родилась новая гипотеза – так называемая гипотеза ABC (или гипотеза Эстерле – Массера), которая произведет настоящую революцию в теории чисел, если кому-нибудь удастся ее доказать. В ее пользу имеется огромное количество численных свидетельств, но доказательство пока, похоже, ускользает, за возможным исключением работы Синити Мотидзуки. Я еще вернусь к ней, когда мы разберемся, о чем, собственно, идет речь.
Более 2000 лет назад Евклид знал, как можно найти все пифагоровы тройки при помощи того, что мы сегодня называем алгебраическими формулами. В 1851 г. Жозеф Лиувилль доказал, что для уравнения Ферма при n ≥ 3 подобной формулы не существует. Мейсон заинтересовался более простым уравнением:
a (x) + b (x) = c (x),
где a (x), b (x) и c (x) – многочлены. Многочлен – это алгебраическая комбинация степеней x, такая, к примеру, как 5x4 – 17x3 + 33x – 4.
Решения, опять же, найти несложно, но они не могут все быть «интересными». Степенью многочлена называется наибольшая степень x, которая в нем присутствует. Мейсон доказал, что если это уравнение верно, то степени a, b и c меньше числа различных комплексных решений x уравнения a (x) b (x) c (x) = 0. Оказалось, что У. Уилсон Стозерс доказал то же самое в 1981 г., но Мейсон развил эту идею дальше.
Специалисты по теории чисел часто ищут аналогии между многочленами и целыми числами. Естественным аналогом теоремы Мейсона – Стозерса могла бы быть такая: пусть a + b = c, где a, b и c – целые числа, не имеющие общих делителей. Тогда число простых делителей у каждого из чисел a, b и c меньше числа различных простых делителей abc.
К несчастью, очевидно, что это утверждение неверно. Так, если взять сумму 9 + 16 = 25, то имеем 9 = 3 × 3 (2 делителя), 16 = 2 × 2 × 2 × 2 (4 делителя) и 25 = 5 × 5 (2 делителя). А их произведение abc = 9 × 16 × 25 имеет лишь три различных простых делителя (2, 3 и 5). Упс. Однако математики не сдаются. В данном случае они попытались модифицировать это утверждение так, чтобы оно выглядело правдоподобным. В 1985 г. Дэвид Массер и Жозеф Эстерле сделали именно это. Их вариант утверждения выглядит так:
«Для любого ε