Тайны чисел: Математическая одиссея Сотой Маркус
На каждом кубике может с равной вероятностью выпасть любая из шести граней. Когда у нас имеется две игральных кости, то получается 6 6 различных возможных бросков, у каждого из которых будет одинаковая вероятность. Но когда вы проанализируете различные варианты получения заданного общего счета, то поймете, что счет 2 или 12 маловероятен, потому что любая из этих комбинаций получается лишь одним способом. В то же время счет 7 можно получить шестью способами (рис. 3.08).
Рис. 3.08
Итак, получается шанс 6 из 36, или 1 из 6, выбросить 7, а счет 6 или 8 будет следующим по вероятности. Выброшенный счет 7 приведет вас из тюрьмы на поле благотворительного фонда города, который вы не можете купить. Но соседствующие с ним оранжевые поля собственности (Боу-стрит и Мальборо-стрит в лондонской версии игры) являются следующими по вероятности остановками.
Если вам повезет, и вы окажетесь в этой оранжевой области собственности, то нужно будет купить ее и застроить отелями. Тогда вы сможете спокойно собирать плату за проживание с ваших соперников, когда бросок игральных костей выведет их из тюрьмы прямиком в ваше логово.
Телевикторина «Тайн 4исел»
Это игра для двух участников. Возьмите 20 конвертов и пронумеруйте их от 1 до 20. Игрок 1 записывает 20 различных сумм денег на листках бумаги и кладет их по одному в каждый конверт. Затем игрок 2 открывает какой-либо конверт и видит внутри денежную сумму. Он может либо принять эту сумму, либо выбрать другой конверт. Если он выбирает другой конверт, то не может возвращаться и претендовать на предыдущий приз.
Игрок 2 продолжает открывать конверты, пока не удовольствуется призом. Затем игрок 1 оглашает все призы. Игрок 2 получает 20 очков, если он набрал максимальную денежную сумму из имеющихся. Его результат равен 19 очкам, если он выбрал вторую по величине сумму, и т. д.
Теперь все конверты опустошаются, и игрок 2 записывает 20 различных денежных сумм на листках бумаги и кладет их по одному в каждый конверт. Теперь настала очередь игрока 1 попытаться получить наибольший денежный приз. Когда он останавливается на каком-либо из конвертов, то получает очки таким же образом, как и игрок 2. Победителем будет тот, у кого больше очков. Разумеется, это вовсе не означает большее количество денег. Счет идет именно по очкам.
Интригующий аспект этой игры состоит в том, что вы не знаете, каков диапазон призов: максимальный приз может быть и 1, и 1 000 000. Вопрос состоит в том, существует ли математическая стратегия, позволяющая повысить ваши шансы выигрыша. Да, такая стратегия существует. Она состоит в секретной формуле, зависящей от е, только не психоделического, а математического толка. Число e = 2,71828…, наверное, одно из самых знаменитых чисел во всей математике, уступающее лавры первенства только энигматичному . Это число возникает всякий раз, когда оказывается важной концепция роста. Например, оно тесно связано с тем, как на вашем банковском счете накапливаются проценты.
Представьте, что вы хотите инвестировать 1 и изучаете процентные ставки, предлагаемые различными банками, и их условия. Один из банков предлагает 100 % годовых, выплачиваемых по истечении года. В результате ваша инвестиция возрастет до 2. Неплохо, но другой банк предлагает ставку 50 % за полгода, выплачиваемую два раза в год. Тогда через полгода у вас будет 1,50, а через год 1,50 + 0,75 = 2,25. Таким образом, условия второго банка лучше, чем первого. А третий банк предлагает 33,3 % за четыре месяца, выплачиваемые три раза в год. Это приведет к (1,333) = 2,37 через двенадцать месяцев. Если вы разбиваете год на все меньшие и меньшие интервалы, эта капитализация процентов становится все более выгодной вам.
К настоящему времени, как я надеюсь, математик внутри вас понял, что вам выгоднее всего было бы обратиться в «Банк бесконечности», который разделяет год на бесконечно малые промежутки времени. В этом банке у вас будет максимально достижимый баланс. Хотя баланс и увеличивается при все большем разделении года, он не будет бесконечным, а будет стремиться к этому волшебному числу e = 2,71828… Как и у , у е имеется бесконечное десятичное разложение (обозначаемое «…»), которое никогда не повторяется. Оказывается, что е играет ключевую роль в том, чтобы помочь вам победить в викторине «Тайн 4исел».
Математический анализ этой игры предлагает вам сначала вычислить 1/е, что приблизительно составляет 0,37. Теперь вам нужно открыть 37 % конвертов, или около семи из них. Продолжайте открывать конверты, но остановитесь, как только дойдете до денежной суммы, превосходящей все, открытые до нее. Математика оценивает, что в одном случае из трех вы получите максимальный денежный приз. Данная стратегия полезна не только при участии в телевикторине «Тайн 4исел». Для принятия многих решений в нашей жизни можно также руководствоваться ею.
Вы помните вашего первого бойфренда или подругу? Наверное, вы считали их замечательными. Вероятно, у вас были романтические мечты провести всю жизнь вместе. Но потом возникло мучительное чувство, что вы заслуживаете большего. Беда в том, что если вы разорвете отношения с партнером, то пути назад уже не будет. Так в какой момент имеет смысл прекратить дальнейшие поиски и принять то, что у вас имеется? Поиск квартиры является другим классическим примером. Сколько раз получается так, что уже первая просмотренная квартира кажется вам замечательной, но потом представляется необходимым увидеть больше вариантов до заключения договора, хотя при этом вы рискуете упустить первую замечательную квартиру?
Поразительно, но та же математика, которая помогает победить в телевикторине «Тайн 4исел», может дать вам наилучшие шансы при поиске партнера или квартиры. Предположим, что вы начинаете ходить на свидания в возрасте 16 лет и при этом поставили перед собой цель найти любовь своей жизни до пятидесятилетнего возраста. Также предположим, что вы меняете партнеров с постоянной частотой. Математика говорит, что вам стоит сначала изучить окружение в течение 37 % времени, которые вы отвели себе, то есть приблизительно до 28 лет. Затем вы должны остановиться на партнере, который лучше всех, с кем вы встречались до него или нее. Для одного из трех человек это гарантирует, что он найдет наилучшего возможного партнера. Но ни в коем случае не проговоритесь любви вашей жизни о принятой стратегии!
Как выиграть в шоколадно-перечную рулетку?
Даже если вы знаете математику, игры вроде «Монополии» или телевикторины «Тайн 4исел» все же опираются на случай. Но теперь я предложу вам простую игру для двух участников, которая иллюстрирует то, как математика может гарантировать вам победу. Возьмите 13 шоколадных батончиков и стручок жгучего перца и сложите их в кучку на столе. Каждый игрок по очереди берет один, два или три предмета из кучки. Цель игры состоит в том, чтобы заставить вашего соперника взять стручок перца.
Рис. 3.09. Шоколадно-перечная рулетка
Существует стратегия, приводящая к победе, если вы ходите первым. Она состоит в ом, что, сколько бы батончиков ни взял соперник, вы берете из горки столько батончиков, чтобы в данном раунде вы вместе взяли четыре штуки. Например, если ваш оппонент берет три батончика, вы берете один. Если же он берет два, вы также берете два.
Прием состоит в том, что можно расположить батончики шоколада в ряды по четыре штуки (делайте это в голове, иначе вы раскроете свои карты). Вначале имеется 13 батончиков, то есть получается три ряда по четыре плюс один батончик (а также, разумеется, перец). Так что ваш первый ход должен состоять в том, чтобы взять этот одиночный батончик. После этого действуйте по рецепту, приведенному выше: в ответ на ход вашего соперника возьмите столько батончиков, чтобы вместе вы брали четыре. После трех раундов на столе останется только стручок перца, и вашему сопернику придется взять его.
Рис. 3.10. Как расположить шоколад, чтобы гарантировать победу
Стратегия опирается на то, что вы ходите первым. Если первым ходит ваш оппонент, то единственной его ошибки будет достаточно, чтобы вы вернули себе выигрышную позицию. Например, если он возьмет больше одного батончика при первом ходе, он станет расходовать батончики из первого ряда из четырех штук. Тогда вы, как и ранее, возьмите остаток этого ряда.
Вы можете модифицировать игру, начав ее с другого количества батончиков или изменив максимальное число батончиков, которое разрешается брать за один ход. Та же математика, состоящая в разделении батончиков на группы, позволит вам придумать выигрышную стратегию.
Существует другой вариант этой игры, называемый «Ним». Для нахождения гарантированной выигрышной стратегии в «Ним» необходим более изощренный математический анализ. На сей раз на столе находятся четыре кучки. В первой кучке – пять шоколадных батончиков, во второй – четыре, в третьей – три, наконец, в четвертой находится только стручок перца. Теперь вам разрешается брать сколько угодно батончиков, но только из одной кучки. Например, вы могли бы взять все пять шоколадных батончиков из первой кучки либо только один из третьей. Вы проиграете, если вашей единственной возможностью будет взять стручок перца.
Таблица 3.02. Запись чисел в двоичной системе
Чтобы выиграть эту игру, нужно уметь переводить числа из десятичной в двоичную систему счисления. Мы считаем десятками, потому что у нас десять пальцев. После того как вы дошли до 9, вы начинаете новый разряд в записи чисел и пишете 10, чтобы указать, что в этом числе один десяток и ноль единиц. Но компьютеры любят считать двойками, что мы называем двоичной, или бинарной, системой. Каждый разряд в записи числа в двоичном виде соответствует степени 2, а не степени 10. Например, двоичное число 101 подразумевает 1 набор 22, 0 наборов 21 и 1 единицу (20). Итак, 101 – это двоичный вид числа 4 + 1 = 5. В таблице приведено несколько первых чисел, записанные в двоичном виде.
Чтобы выиграть в игру «Ним», нужно перевести число батончиков в каждой кучке в двоичный вид. Тогда получится, что в первой кучке 101 батончик, во второй 100, а в третьей 11. Записывая последнее число как 011 и располагая эти числа в трех строках поверх друг друга, мы приходим к
Заметьте, что в первом столбце содержится четное число единиц, во втором нечетное и в третьем четное. Выигрышная стратегия заключается в том, чтобы при каждом ходе убирать столько батончиков из одной из кучек, чтобы в каждом столбце получалось четное число единиц. Итак, в данном случае возьмите два батончика из третьей кучки, чтобы их число уменьшилось до 001.
Почему это поможет вам выиграть? Что же, каждый раз ваш соперник будет вынужден оставлять как минимум один столбец с нечетным числом 1. Вы последующим ходом возьмете столько батончиков, чтобы снова сделать число 1 во всех столбцах четным. Поскольку число батончиков постоянно уменьшается, в какой-то момент их не останется, так что в трех кучках будет 000, 000 и 000 батончиков. Кто сделает приводящий к этому ход? Ваш соперник всегда оставляет нечетное число 1 хотя бы в одной из кучек, поэтому этот ход сделаете вы. И оппоненту не останется ничего иного, как взять стручок перца.
Эта стратегия сработает независимо от числа батончиков в кучках. Вы даже можете увеличить количество кучек.
Почему магические квадраты играют ключевую роль в облегчении деторождения, предотвращении наводнений и победе в играх?
Умение взглянуть на проблему с разных сторон оказывается очень полезным, когда дело доходит до математики. Может оказаться так, что решение тяжелой головоломки неожиданно станет очевидным, если вы посмотрите на нее под другим углом. Искусство состоит в том, чтобы найти, как правильно рассматривать задачу. Иллюстрацией этому служит игра, обсуждаемая ниже. На первый взгляд довольно трудно следить за ее ходом, но если рассмотреть эту игру иначе, все становится довольно просто. Вы можете загрузить файл с веб-сайта «Тайн 4исел» и вырезать реквизит, необходимый для игры.
У каждого из участников есть пустое блюдо для торта, на которое помещается 15 кусков. Цель игры состоит в том, чтобы первым заполнить свое блюдо ровно тремя секторами из имеющихся девяти секторов разных размеров. Наименьший сектор содержит лишь один кусок, а наибольший – девять кусков. Соперники по очереди выбирают один из секторов.
Цель состоит в том, чтобы получить три числа от 1 до 9, которые в сумме дают 15, одновременно с этим нужно следить за тем, что делает ваш соперник, и расстроить его планы. Так, если ваш оппонент взял сектора с 3 и 8 кусками, необходимо не дать ему набрать 15, взяв сектор с 4 кусками. Если сектор, который вы присмотрели, уже был взят, требуется отыскать другой способ прийти к 15, используя взятые куски и остающиеся. Но заполнять блюдо нужно ровно тремя секторами – использование секторов с 9 и 6 кусками не будет считаться победой, как и заполнение блюда четырьмя секторами с 1, 2, 4 и 8 кусками.
Рис. 3.11. Подберите три сектора, чтобы заполнить ваше блюдо для торта, опередив при этом соперника
Вскоре после начала игры становится довольно трудно уследить за различными способами, которыми вы и ваш соперник можете заполнить блюда. Но игра становится значительно проще, когда вы поймете, что, по существу, играете в замаскированную классическую игру крестики-нолики. Вместо обычной сетки 3 3, на которую вы помещаете 0 и Х, стараясь расположить три в линию до вашего соперника, это состязание разыгрывается на магическом квадрате:
Таблица 3.03
Самый простой магический квадрат подразумевает размещение чисел от 1 до 9 на сетке 3 3 таким образом, что сумма чисел во всех столбцах, строках и на диагоналях равна 15. Это расположение представляет все возможные способы получить 15 сложением 3 различных чисел от 1 до 9. Если представить игру с кусками тортов как расстановку крестиков и ноликов на магическом квадрате, становится понятно, что победителем будет тот, кто первым расположит три в линию, ведь у него будут три числа, которые в сумме дают 15.
По легенде, первый магический квадрат появился в 2000 г. до н. э. Он был нанесен на спину черепахи, которая выползла из реки Ло в Китае. Река сильно разлилась, и император Ю повелел совершить несколько жертвоприношений, чтобы умилостивить речного бога. В ответ речной бог послал на сушу черепаху, расположение чисел на панцире которой должно было помочь императору контролировать реку. Когда это расположение было понято, китайские математики начали составлять все большие и большие квадраты с такими же свойствами. Полагалось, что эти квадраты обладают магической силой, и их стали часто использовать для предсказаний. Самым впечатляющим достижением китайских математиков был магический квадрат 9 9.
Имеются свидетельства о том, что эти квадраты были ввезены в Индию китайскими торговцами, которые имели дело не только с пряностями, но и с математическими идеями. То, как числа переставляются в этих квадратах, сильно резонировло с индуистскими верованиями о реинкарнации, и в Индии эти квадраты использовались в самых разнообразных целях: от составления парфюмерных рецептов до помощи при деторождении. Магические квадраты были также популярны в средневековой исламской культуре. Ее значительно более систематический подход к математике привел к нескольким изощренным способам составления магических квадратов, кульминацией чего стало открытие впечатляющего магического квадрата 15 15 в XIII столетии.
Одно из первых появлений магических квадратов в Европе засвидетельствовано на гравюре Альбрехта Дюрера «Меланхолия», где изображен квадрат 4 4.
Рис. 3.12. Магический квадрат Альбрехта Дюрера
Числа от 1 до 16 расположены в нем так, что их сумма по всем столбцам, строкам и диагоналям равна 34. Кроме того, сумма чисел в каждом из четырех квадрантов (квадратов 2 2, на которые может быть разбит больший квадрат) и в центральном квадрате 2 2 также равна 34. Дюрер даже расположил два числа посередине нижнего ряда, указывающих на год создания гравюры: 1514. А два крайних числа в нижнем ряду соответствуют инициалам художника.
Магические квадраты разного размера традиционно сопоставлялись с различными планетами Солнечной системы. Классический квадрат 3 3 соответствовал Сатурну, квадрат 4 4 в «Меланхолии» – Юпитеру, а самый большой квадрат 9 9 приписывался Луне. Было выдвинуто предположение, что использование Дюрером этого квадрата отражало его мистическое убеждение, что жизнерадостность Юпитера может противостоять тому чувству меланхолии, которым наполнена гравюра.
Другой знаменитый магический квадрат можно найти у входа в пышно украшенный храм Святого Семейства (Temple Expiatori de la Sagrada Famlia), до сих пор не достроенную церковь в Барселоне, проект которой был разработан Антонио Гауди. Магическим числом этого квадрата размером 4 4 является 33, столько лет было Христу при его распятии. Этот квадрат не совсем удовлетворителен, в отличие от квадрата Дюрера, потому что числа 14 и 10 встречаются в нем два раза за счет 4 и 16.
Хотя магические квадраты скорее являются математическим курьезом, с ними связана задача, которую математики до сих пор не смогли решить. По существу, имеется один магический квадрат размером 3 3. (Выражение «по существу» означает, что квадрат, полученный в результате вращения первоначального квадрата или операции отражения, примененной к нему, не будет считаться другим.) В 1693 г. француз Бернар Френикль де Бесси перечислил все 880 возможных магических квадратов размером 4 4, а в 1973 г. Рихард Шрёппель использовал компьютерную программу и рассчитал число магических квадратов размером 5 5. Их оказалось 275 305 224. Помимо этого у нас имеются лишь оценки для числа магических квадратов размером 6 6 и более того. Математики все еще находятся в поисках формулы, которая дала бы точные числа.
Кто изобрел судоку?
Дух судоку можно найти в головоломке, выросшей из математического увлечения магическими квадратами. Возьмите фигурные карты (валетов, дам, королей и тузов) из стандартной колоды карт и расположите их на сетке 4 4 так, чтобы ни в одном ряду и ни в одном столбце не было карт одной и той же масти или достоинства. Эту задачу впервые предложил в 1694 г. французский математик Жак Озанам, поэтому его можно было бы считать изобретателем судоку.
Математиком, несомненно заразившимся этой задачей, был Леонард Эйлер. В 1779 г., за несколько лет до смерти, Эйлер предложил другой вариант задачи. Пусть имеется шесть полков, униформа которых разного цвета, например красная, синяя, желтая, зеленая, оранжевая и фиолетовая. В каждом из полков имеется шесть военнослужащих различного звания, скажем полковник, майор, капитан, лейтенант, капрал и рядовой. Задача состоит в расположении военных на сетке 6 6 так, чтобы ни в одной шеренге и ни в одной колонне не было военных одинакового звания или цвета униформы. Эйлер задал этот вопрос для сетки 6 6, поскольку считал, что невозможно удовлетворительно расположить 36 военных. Лишь в 1901 г. французский математик-любитель Гастон Тарри доказал, что Эйлер был прав.
Эйлер также полагал, что эту головоломку невозможно решить для сетки размером 10 10, 14 14, 18 18 и т. д., если каждый раз прибавлять 4. Но это оказалось неверно. В 1960 г. три математика с помощью компьютера показали, что удается разместить военных 10 разных званий из 10 полков на сетке размером 10 10 вопреки убеждению Эйлера. Они не остановились на достигнутом и полностью опровергли гипотезу Эйлера, доказав, что сетка размером 6 6 представляет единственный случай, когда такое расположение невозможно.
Если вы хотите испытать себя в решении головоломки Эйлера на сетке 5 5, то загрузите соответствующий файл с веб-сайта «Тайн 4исел», вырежьте военных пяти званий из пяти полков. Проверьте, сумеете ли вы разместить их на сетке 5 5, чтобы ни в одной шеренге и ни в одной колонне не было военных из одного полка или одного звания. Эти магические квадраты иногда называют греко-латинскими квадратами. Возьмите первые n букв из латинского и греческого алфавитов и составьте все n n возможных пар из латинских и греческих букв. Теперь расположите эти пары на сетке n n, чтобы ни в одной строке и ни в одном столбце не было одинаковых латинских или греческих букв.
Жизнь в квадратеФранцузский писатель Жорж Перек использовал греко-латинский квадрат размером 10 10 для придания структуры своему роману «Жизнь, способ употребления», изданному в 1978 г. В книге 99 глав, каждая из них соответствует комнате в парижском многоквартирном доме в десять этажей, на каждом из которых по десять комнат (комната под номером 66 не посещается). Каждая из комнат соответствует позиции в греко-латинском квадрате 10 10. Но при этом Перек использует не 10 греческих и 10 латинских букв, а, скажем, 20 авторов, разделенных на два списка по 10 человек. Когда он писал главу про какую-то комнату, то следил за тем, какие авторы приписаны ей, чтобы в ходе повествования использовать отрывки из их произведений. Например, в главе 50 греко-латинский квадрат Перека предписывает ему цитировать Гюстава Флобера и Итало Кальвино. Но в схему вовлечены не только писатели. В общей сложности Перек использует 21 различный греко-латинский квадрат, каждый из них наполняется благодаря двум спискам по 10 пунктов. Эти списки варьируются от мебели, художественного стиля и периода в истории до положений тел, принимаемых обитателями комнат.
Судоку несколько отличается от головоломки Эйлера о военных. В его классической форме вам необходимо разместить девять наборов чисел от 1 до 9 на сетке 9 9 так, чтобы ни в одной строке, столбце или квадранте 3 3 никакое число не встречалось два раза. Несколько чисел уже нанесены на сетку, и требуется заполнить пустые места. Не верьте тем, кто заявляет, что для решения этих головоломок не требуется математика. Они имеют в виду, что не требуется совершать арифметических действий – судоку, по существу, является логической задачей. Но тот же вид логического рассуждения, которое приводит вас к заключению, что в нижнем правом углу может быть только 3, встречается повсюду и в математике.
С судоку связаны несколько интересных математических вопросов. Один из них: сколькими различными способами можно расположить числа на сетке 9 9, чтобы удовлетворить правилам судоку? (Опять-таки под различными мы имеем в виду «существенно» различные: мы считаем два расположения одинаковыми, если одно из них переходит в другое вследствие простой симметрии, например перестановки строк.) Ответ был найден в 2006 г. Эдом Расселом и Фрэзером Джарвисом: 5 472 730 538. Этого вполне достаточно, чтобы газеты продолжали выходить еще какое-то время.
Однако другая математическая задача, связанная с этими головоломками, не была решена полностью. Какое минимальное количество чисел должно быть вначале нанесено на сетку, чтобы судоку решалось только одним способом Понятно, что если этих чисел будет мало – скажем, 3, то головоломку можно будет решить многими способами, имеющейся вначале информации будет недостаточно для однозначного решения. Считается, что необходимо по крайней мере 17 чисел, чтобы судоку решалось только одним способом. Этот вопрос выходит за рамки головоломок, решаемых на досуге. У математики, лежащей в основе судоку, имеются важные следствия для кодов с коррекцией ошибок, с которыми мы познакомимся в следующей главе.
Как математика может вам помочь попасть в Книгу рекордов Гиннесса?
Имеется множество безумных способов попасть в Книгу рекордов Гиннесса. Итальянский бухгалтер Микеле Сантелиа оказался там, напечатав 64 книги на языке оригинала в обратном порядке (3 361 851 слово, 19 549 382 символа). Среди них были Одиссея, «Макбет», латинская Библия (Вульгата) и Книга рекордов Гиннесса за 2002 г. Кен Эдвардс из Глоссопа, графство Дербишир, является обладателем мирового рекорда по скорости поедания тараканов – 36 за одну минуту. А американцу Ашрите Фурману понадобилось 12 часов 27 минут, чтобы пропрыгать на пого-стике («кузнечике») рекордное расстояние 37,18 км. У него также рекорд по самому большому количеству рекордов! Но поможет ли математика в ваших попытках оказаться в зале славы Гиннесса?
Одним из соревнований, за которым Книга рекордов следит с 1961 г., является посещение всех станций лондонского метро за самое короткое время. Оно называется «Вызовом подземки» (Tube Challenge), и рекорд на конец 2009 г. составлял 6 часов 44 минуты 16 секунд. Он был установлен Мартином Хэзелом, Стивом Уилсоном и Энди Джеймсом 14 декабря того же года. Кто-то может сказать, что это мучительная гонка, но если вы хотите попытаться побить их рекорд, то математический анализ карты метро может дать вам преимущество в нахождении самого короткого маршрута, гарантированно включающего все станции метро хотя бы один раз.
«Вызов подземки» не является первым в своем роде. Он представляет более сложный вариант игры, популярной в прусском городе Кёнигсберг в XVIII в. В центре города находится остров, омываемый двумя рукавами реки Прегель, далее река течет на запад и впадает в Балтийское море. В XVIII в. через Прегель было перекинуто семь мостов, и горожане заполняли свой воскресный досуг тем, что пытались пройти по всем по ним, побывав на каждом мосту только один раз. В отличие от «Вызова подземки» главное при этом не скорость, а то, возможен ли такой маршрут вообще. Как ни старались жители Кёнигсберга, они не могли решить эту задачу. Была ли эта миссия на самом деле невыполнима, или все же имелся путь, не найденный горожанами, который проходил по семи мостам по одному разу?
Проблема была окончательно решена Леонардом Эйлером, швейцарским математиком, работавшим в Петербургской академии наук в 800 км к северо-востоку от Кёнигсберга (ранее обсуждалась его задача о греко-латинских квадратах). Эйлер совершил важнейший концептуальный скачок. Он понял, что фактические размеры города были совершенно не важны: значимо было то, как мосты соединялись друг с другом (тот же принцип применяется при составлении топологической карты лондонского метро). Каждый из четырех участков земли, соединяемых мостами Кёнигсберга, может быть сжат в точку, называемую вершиной. Мостам при этом соответствуют линии, соединяющие вершины. В результате получается карта мостов Кёнигсберга, несколько напоминающая значительно упрощенную карту лондонского метро (рис. 3.13).
Рис. 3.13
Задача о прохождении мостов сводится к тому, возможно ли начертить эту карту, не отрывая карандаша от бумаги и не проводя по одной и той же линии дважды (одним росчерком). Благодаря новой математической перспективе Эйлер сумел понять, что невозможно пройти по всем семи мостам, побывав на каждом из них только один раз.
Но почему же это невозможно? При рисовании карты каждая вершина, которую вы посетили в середине путешествия, должна иметь одну входящую и одну выходящую линию. Если вы оказываетесь в этой вершине снова, значит, вы пришли в нее по новому «мосту» и так же должны выйти из нее через новый «мост». Значит, в каждой вершине должно сходиться четное число линий, за исключением начала и конца путешествия.
Если мы поглядим на план семи мостов Кёнигсберга, то увидим, что в каждой из его четырех вершин сходится нечетное число линий – и это говорит нам, что не существует маршрута по городу, проходящего по каждому из мостов только один раз. Эйлер пошел в своем анализе дальше. Если на карте имеется ровно две вершины с нечетным числом линий, такую карту можно нарисовать одним росчерком. Чтобы сделать это, нужно начать рисование с одной из точек с нечетным числом линий, а закончить его в другой вершине с нечетным числом линий.
Рис. 3.14. Теорема Эйлера утверждает, что эту карту можно нарисовать одним росчерком
Существует второй вид карт, который можно обойти по пути, называемому математиками наших дней Эйлеровым: такой, в каждой вершине которого сходится четное число линий. На подобной карте можно начать рисование в любой вершине, потому что путь должен начаться и закончиться в одной и той же вершине, чтобы получилась замкнутая петля. Хотя у вас и могут быть сложности с нахождением нужного пути, теорема Эйлера говорит вам, что, если карта принадлежит к одному из двух описанных мной типов, такой путь должен иметься. Такова сила математики: довольно часто она говорит вам о существовании чего-то, не прибегая к фактическому построению.
Чтобы доказать существование пути, воспользуемся классическим оружием из математического арсенала – индукцией. Она чем-то напоминает способ, посредством которого я борюсь со страхом высоты при подъеме на высокие лестницы или спуске по веревке с вершины водопада: делая раз за разом маленький шажок.
Начните с предположения, что вы умеете рисовать все карты с определенным числом ребер одним росчерком. А теперь представьте, что вам дана карта, у которой на одно ребро больше, чем было до того. Как можно понять, что вы по-прежнему сумеете нарисовать эту новую карту?
Давайте предположим, что у этой карты в двух вершинах сходится нечетное число ребер. Назовем эти вершины A и В. Трюк состоит в том, чтобы удалить одно из ребер, исходящих из вершин с нечетным числом ребер. Давайте удалим ребро, соединяющее B с другой вершиной С. На этой новой карте с одним удаленным ребром по-прежнему только две вершины, в которых сходится нечетное количество ребер: A и C. (Вершина B теперь характеризуется четным числом ребер, потому что мы только что удалили одну исходящую из нее линию; у вершины C теперь нечетное число, потому что мы удалили линию, соединяющую ее с В.) У этой новой карты достаточно малое число ребер, и мы можем ее нарисовать одним росчерком, начиная с вершины А и заканчивая в вершине С. Большую карту также нетрудно нарисовать: просто соедините С и В, добавив ребро, которое мы устранили ранее. Бинго!
Для полноты нам необходимо проанализировать еще несколько случаев. Например, что будет, если из B исходит только одна линия, которая соединяет ее с А, так что вершины А и С совпадают? Но мы можем видеть, что в основе доказательства существования Эйлерова пути лежит красивая идея продвижения шаг за шагом. Подобно тому как я методично поднимаюсь вверх по лестнице, я могу воспользоваться данным приемом для сколь угодно большой карты.
Чтобы увидеть мощь теоремы Эйлера, скажите вашему другу нарисовать настолько сложную карту, насколько он пожелает. Затем просто сосчитайте количество точек, где сходится нечетное число линий, и благодаря теореме Эйлера вы можете тут же сказать, удастся ли нарисовать эту карту одним росчерком.
Я недавно совершил паломничество в Кёнигсберг, который был переименован в Калининград после Второй мировой войны. Город неузнаваемо изменился со времен Эйлера – он был разрушен бомбардировками союзников. Однако три довоенных моста по-прежнему на месте: Деревянный мост (Holzbrcke), Медовый мост (Honigbrcke) и Высокий мост (Hohebrcke). Два моста исчезли полностью: Потроховой мост (Kttelbrcke и Кузнечный мост (Schmiedebrcke). Оставшиеся мосты – Зеленый мост (Grnebrcke) и Лавочный мост (Krmerbrcke) – также были разрушены во время войны, но были перестроены и стали частью гигантской автострады с четырьмя полосами движения, проходящей через город.
Новый железнодорожный мост, по которому также могут ходить пешеходы, соединяет два берега Прегеля к западу от города. Также новый пешеходный Юбилейный мост, построенный на опорах разрушенного Императорского моста, позволил мне перейти реку подобно старому Высокому мосту. Я всегда думаю как математик и первым делом задался вопросом, можно ли совершить путешествие по сегодняшним мостам в духе игры XVIII в.
Рис. 3.15. Мосты Кёнигсберга XVIII в.
Рис. 3.16. Мосты Калининграда XXI в.
Математический анализ Эйлера подсказал мне, что если есть ровно два места, от которых отходит нечетное число мостов, то существует Эйлеров путь: вы начинаете движение в одном месте с нечетным числом и заканчиваете движение во втором. Посмотрев на план мостов сегодняшнего Калининграда, я обнаружил, что такой маршрут действительно возможен.
История мостов Кёнигсберга важна потому, что она дала математикам новый взгляд на геометрию и пространство. В этой новой перспективе важны не расстояния и углы, а то, как формы соединены друг с другом. Так зародилась топология, одна из наиболее влиятельных ветвей математики последнего столетия, которая рассматривалась в главе 2. Задача о мостах Кёнигсберга способствовала возникновению математики, лежащей в основе поисковых систем интернета вроде Google. Они стремятся как можно к более эффективной навигации по Сети. Задача о мостах также может быть полезна при планировании посещения станций лондонского метро, если у вас возникло искушение дать свой ответ на «Вызов подземки».
Как премьер-лига может принести вам «математический миллион»?
В середине сезона ваша команда томится в нижней половине турнирной таблицы, и вы хотите понять, остались ли у нее математические шансы стать чемпионом. Интересно, что математика, лежащая в основе попыток ответа на данный вопрос, напрямую связана с задачей на миллион долларов этой главы.
Чтобы разобраться, возможно ли это математически, вы начинаете с предположения, что ваша команда выиграет все оставшиеся матчи. Это даст ей три очка за каждую игру. Проблемы начинаются, когда вы пытаетесь проследить за необходимым распределением всех остальных очков в турнирной таблице. Вы желаете достаточного количества проигрышей командам, находящимся выше, чтобы ваша команда обошла их. Но не получится так, чтобы все проигрывали, ведь другие команды играют и между собой. Значит, вам необходимо найти правильный способ распределения очков в оставшихся матчах и надеяться, что одна из допустимых комбинаций выведет вас наверх таблицы. Наверняка должен быть более элегантный способ определить, существует ли такая выигрышная комбинация.
Вам необходимо найти хитроумный прием наподобие того, который использовал Эйлер для рисования карт, – он означал бы, что вам не требуется разбирать все возможные сценарии результатов предстоящих матчей. К несчастью, в настоящее время мы не знаем, существует ли такой прием. Миллион долларов получит первый человек, который либо найдет этот прием, либо докажет, что у этой задачи есть некоторая неотъемлемая сложность, из-за которой полный перебор является единственной возможностью решить задачу.
Любопытно, что до 1981 г. существовала эффективная программа, которой вы могли воспользоваться в середине сезона для проверки того, остается ли у вашей команды шанс выиграть премьер-лигу. До 1981 г. команде присуждались лишь два очка за победу, и эти же два очка делились между соперниками в случае ничьей. Это очень существенно с математической точки зрения, поскольку означает, что полное число очков, разыгранных в сезоне, фиксированно. Например, в лиге с 20 командами, такой как премьер-лига, каждая команда играет 38 матчей (один матч дома и один матч на выезде против каждой из остальных 19 команд). Итак, получается 20 38 матчей… за исключением того, что я учел каждый матч дважды. Ведь матч «Арсенала» против «Манчестер Юнайтед» – это также матч «Манчестер Юнайтед» против «Арсенала». Итак, в общей сложности получается 10 38 = 380 матчей. Система подсчета очков, применявшаяся до 1981 г., означала, что полное количество очков в конце сезона будет равняться 2 380 = 760, и эти очки будут распределены между 20 командами. Это обстоятельство было ключевым для эффективной программы, которой можно было воспользоваться в середине сезона, чтобы понять, остался ли у вашей команды шанс выиграть титул.
В 1981 г. все изменилось математически. Когда за победу даются три очка и в общей сложности два очка за ничью (по одному каждой из команд), нельзя сказать заранее, каким будет полное количество очков в конце сезона. Если каждый матч завершится вничью, то полное количество очков будет снова 760. Но если в каждом матче будет победитель, то полное количество очков будет 1140. Это изменение сделало задачу о премьер-лиге трудноразрешимой.
Имеется множество иных вариантов задачи о премьер-лиге, за которые можно взяться, если вы не футбольный болельщик. Классический вариант называется задачей коммивояжера. В качестве примера такой задачи разберитесь со следующим: вы коммивояжер, и вам необходимо посетить 10 клиентов, причем все они находятся в разных городах. Эти города соединены дорогами, как показано на приведенной карте, – но топлива у вас хватит лишь на 238 миль.
Рис. 3.17. Пример задачи коммивояжера. Можете ли вы найти маршрут протяженностью 238 миль или менее, который проходит через все точки на карте и возвращается в начальную точку?
Расстояние между городами задается числом на дороге, соединяющей их. Можете ли вы найти маршрут, позволяющий вам посетить всех 10 клиентов и затем вернуться домой на имеющемся топливе? (Решение приведено в конце главы.) В данной версии задачи миллион предлагается тому, кто найдет общий алгоритм или напишет компьютерную программу, которая выдаст кратчайший путь для любой задаваемой карты и будет при этом существенно быстрее перебора всех вариантов. Число возможных маршрутов экспоненциально растет с ростом числа городов, поэтому поиск методом полного перебора вскоре становится практически невозможен. Или же вы сумеете доказать, что такой быстрой программы не может быть?
Среди математиков преобладает мнение, что задачи этого вида имеют встроенную сложность, что означает отсутствие какого-то умного способа для поиска решения. Я обычно называю эти задачи иголкой в стоге сена, потому что, по существу, имеется много возможных решений, и вы стараетесь найти особенное из них. Техническое название для них – NP-полные задачи.
Как только вы нашли иголку, легко проверить, что она является требуемым результатом, – это одна из ключевых характеристик данных головоломок. Например, вы понимаете, что задача решена, как только вы нашли маршрут на карте, не превосходящий 238 миль. Подобным образом, если вы находите нужную комбинацию результатов на остаток футбольного сезона, вы мгновенно видите, что у вашей команды еще остается математическая возможность стать чемпионами. Задачами класса P в математике называют те, для которых существуют эффективные программы по поиску решения. Задача на миллион долларов может быть сформулирована так: являются ли NP-полные задачи в действительности задачами класса P? Математики говорят об этом как о соотношении классов P и NP.
Имеется другое любопытное свойство, связывающее все NP-полные задачи. Если вы найдете эффективную программу для одной из задач, это будет означать существование таких программ для всех остальных задач. Например, если вам удастся написать умную программу, которая будет выдавать коммивояжеру кратчайший путь, ее можно будет переделать в эффективную программу проверки того, может ли еще ваша команда стать чемпионом. Чтобы дать пример того, как это может сработать, рассмотрим две задачи из класса «иголка в стоге сена» или NP-полных задач, которые кажутся совершенно разными.
Задача о дипломатичном званом обеде
Вы хотите пригласить ваших друзей на званый обед, но некоторые из них на дух не переносят друг друга и вы не хотите, чтобы два врага оказались в одной комнате. Тогда вы решили организовать три обеда и пригласить на них разных людей. Сумеете ли вы написать приглашения так, что два врага не окажутся за одним столом?
Задача о раскраске карты тремя цветами
В главе 2 мы узнали, что карту всегда можно раскрасить с помощью четырех цветов. Но существует ли эффективный прием, позволяющий сказать, что для заданной карты можно обойтись тремя красками?
Но как решение задачи о трех красках может помочь вам в задаче о званом обеде? Давайте предположим, что вы записали имена своих друзей и соединили линиями пары людей, которые ненавидят друг друга:
Рис. 3.18. Линией соединены люди, которых нельзя пригласить на один обед
Чтобы решить, на какой из обедов вы должны пригласить того или иного друга, вы могли бы начать раскрашивать овалы вокруг имен разными цветами, причем разные цвета соответствуют разным званым обедам. Следовательно, решение о том, состоится ли обед, определяется тем, удастся ли раскрасить рисунок выше так, что никакие два имени, соединенные линией, не были бы окрашены в один цвет. Но посмотрите, что произойдет, если вы замените имена друзей чем-то другим (рис. 3.19).
Рис. 3.19. Линией соединены страны, имеющие общую границу
Ваши друзья, которые не любят друг друга, стали европейскими странами, и линии, соединяющие их, обозначают наличие общей границы. Задача о том, на какую из трех вечеринок пригласить того или иного друга, стала задачей о выборе одного из трех цветов для раскраски той или иной страны на карте Европы. Вопросы об организации званых обедов и раскраски карты тремя цветами являются различными версиями одного и того же вопроса, так что, если вы найдете эффективный способ решения одной из NP-полных задач, вы придете к решению их всех! Предлагаю вам на выбор несколько разных задач, на которых вы можете попробовать свои силы с целью выигрыша миллиона.
Сапер
Это компьютерная игра для одного участника, которая имеется в каждом установочном комплекте операционной системы Microsoft. Цель игры состоит в том, чтобы очистить сетку от мин. Если вы щелкаете по квадратику на сетке, и там нет мины, то появляется число, показывающее, во скольких квадратиках вокруг данного есть мины. Если же вы щелкаете по мине… то взлетаете на воздух. Но саперный вызов на миллион долларов предлагает вам сделать несколько иное. Следующий рисунок не может появиться в настоящей игре, потому что никакое расположение мин не может дать такие числа (рис. 3.20). Число 1 означает, что лишь в одном из неоткрытых квадратиков есть мина, а число 2 означает, что заминированы оба.
Рис. 3.20
Но что можно сказать о следующем рисунке – можно ли увидеть такой в настоящей игре?
Рис. 3.21
Существует ли возможность разместить мины так, чтобы появились эти числа? Или же данный рисунок никоим образом не может возникнуть в настоящей игре, потому что не существует расположения мин, совместимого с этими числами? Ваша задача состоит в том, чтобы разработать эффективную программу, которая сумеет дать ответ на этот вопрос для какой угодно картинки.
Задача об упаковке
Вы руководите фирмой по переезду. Все ваши упаковочные ящики имеют одинаковую ширину и высоту, совпадающие с внутренними размерами вашего грузовика (ну, или чуть меньше этих размеров, так, чтобы их можно было разместить внутри). Но длина ящиков разная. Длина вашего грузовика 150 футов, а у имеющихся ящиков следующие длины: 16, 27, 37, 42, 52, 59, 65 и 95 футов.
Рис. 3.22. Упаковка коробок является математически сложной задачей
Можете ли вы найти комбинацию ящиков, которая наполнит грузовик самым эффективным способом? Вы должны найти алгоритм, определяющий для любого заданного числа N и набора меньших чисел n(1), n(2), …, n(r), существует ли набор меньших чисел, складывающийся в большее число.
Судоку
Нахождение эффективной программы для решения сколь угодно больших головоломок судоку является NP-полной задачей. Иногда судоку бывают настолько убийственны, что приходится делать некоторые предположения и потом исследовать логические последствия этих предположений. Не представляется возможным существование какого-то эффективного способа делать эти предположения, иначе чем перебирать различные наборы предположений, пока не получится последовательный ответ.
Такого рода задачи не являются просто играми: они возникают в бизнесе и промышленности, когда компаниям необходимо найти самое эффективное решение какой-то практической проблемы. Незанятое пространство или перерасход топлива влекут денежные потери, и менеджерам часто приходится решать одну из этих NP-задач. В телекоммуникационной промышленности даже используются коды, дешифровка которых зависит от того, удается ли найти иголку в стоге сена. Поэтому не только математики или заядлые игроки заинтересованы в решении этой задачи на миллион долларов.
Будь то математический анализ футбольных игр или организация званых приемов, раскрашивание карт или расчистка минных полей – задача на миллион долларов из этой главы появляется в столь разнообразных обличьях, что вы наверняка сумеете найти привлекательный для себя вариант. Но имейте в виду следующее: эта задача может казаться забавной и игровой, тем не менее она – одна из самых трудных задач на миллион долларов. Математики полагают, что во всех этих задачах имеется некая существенная сложность, из-за чего может не найтись эффективной программы для их решения. К сожалению, всегда оказывается труднее показать, почему что-то не существует, чем показать его существование. Но, по крайней мере, для вас может быть забавно попытаться получить миллион этой главы.
Решения
Лотерея «Тайн 4исел»
Выигрышные номера: 2, 3, 5, 7, 17, 42.
Задача коммивояжера
Вот маршрут протяженностью 238 миль:
Рис. 3.23
15 + 55 + 28 + 12 + 24 + 35 + 25 + 17 + 4 + 5 + 18 = 238
Глава 4
Случай кода, не поддающегося взлому
С того самого времени, когда люди научились общаться друг с другом, они находили все более и более инфернальные способы скрывать сообщения от своих врагов. Возможно, вы, подобно да Винчи, использовали собственный код для ведения дневника, чтобы ваши брат или сестра не могли прочесть его. Но коды используются не только для сохранения тайн: они также гарантируют, что информация передается без ошибок. И мы можем использовать математику для создания новых искусных способов, обеспечивающих то, что полученное сообщение совпадает с отправленным. Это жизненно важно в наш век электронного обмена информацией.
Код представляет собой систематический способ расположения набора символов, передающего определенное значение. Как только вы начнете искать коды, вы обнаружите, что они окружают нас повсюду: штрихкоды находятся на всем, что мы покупаем, коды позволяют нам хранить музыку на MP3-плеерах и просматривать информацию в интернете. Даже эта книга написана кодом: английский язык – это попросту код, использующий 26 букв алфавита, а наши «допустимые кодовые слова» собраны в Оксфордском словаре английского языка. Коды содержатся даже в наших телах – ДНК представляет собой код для воспроизведения живых существ. ДНК состоит из четырех органических химических веществ, называемых основаниями: аденина, гуанина, цитозина и тимина, для краткости обозначаемых A, G, C и Т.
В этой главе я покажу вам, как математика использовалась для создания и взлома некоторых из самых хитроумных имеющихся кодов, как она позволяет нам безопасно и эффективно передавать информацию и дает возможность делать все, от фотографирования планет с космических аппаратов до покупок на eBay. И в конце главы я объясню, как прорыв в решении одной из задач на миллион долларов мог бы также помочь вам во взломе кодов.
Как использовать яйцо для отправки секретного сообщения
В XVI в. итальянец Джованни Порта открыл, что вы можете написать скрытое послание на сваренном вкрутую яйце с помощью чернил, которые получаются при растворении унции квасцов в пинте уксуса. Чернила проникают сквозь скорлупу и оставляют след на белке внутри. После написания нужно смыть текст со скорлупы, а на белке он остается. Какой совершенный прием для отправки тайных посланий! Чтобы взломать код, требуется разбить яйцо! И это только один из многих умопомрачительных способов, придуманных людьми, чтобы скрывать секретные сообщения.
В 499 г. до н. э. тиран по имени Гистией захотел послать тайное сообщение своему племяннику Аристагору, чтобы побудить его к восстанию против персидского царя. Гистией находился в Сузах, на территории современного Ирана, а его племянник был дома в Милете, который теперь принадлежит Турции. Но как же передать послание племяннику, чтобы персидские власти не перехватили его? Гистией придумал хитрый план. Он повелел своему верному слуге обрить голову и вытатуировал сообщение на его голой голове. Когда волосы отросли снова, Гистией отправил слугу к племяннику. Как только слуга приехал в Милет, племянник обрил ему голову, прочел послание и начал восстание против правившего персидского царя.
В то время как племяннику требовалось лишь обрить голову гонца, мы можем испытать определенную жалость к получателям сообщений, посланных по древнему китайскому методу. Послание писалось на куске шелка, который потом туго заматывался в шарик и покрывался воском. Гонец глотал этот шарик, и процедура извлечения послания была не особенно приятной.
Более изощренный способ прятать сообщения был развит спартанцами в V в. до н. э. Они использовали специальный деревянный цилиндр, называемый «скитала». Вокруг него по спирали наматывалась узкая полоска пергамента. Затем секретное сообщение писалось на ней вдоль оси цилиндра. После того как полоска разматывалась, послание походило на тарабарщину. Требовалось намотать полоску на скиталу с такими же размерами, чтобы буквы снова правильно выстроились.
Эти методы отправки секретных сообщений являются скорее примерами стеганографии, искусства тайнописи, чем кодирования (криптографии). Но сколь изощренны ни были они, когда послание перехватывалось, секреты всплывали наружу. Поэтому люди начали задумываться о том, как скрыть смысл сообщения, даже если оно было перехвачено.
Как взломать шифр Камасутры подсчетом
B OBDFSOBDLNLBC, ILXS B QBLCDSV MV B QMSD, LE B OBXSV MH QBDDSVCE.
LH FLE QBDDSVCE BVS OMVS QSVOBCSCD DFBC DFSLVE, LD LE ASNBGES DFSJ BVS OBTS ZLDF LTSBE. DFS OBDFSOBDLNLBC’E QBDDSVCE, ILXS DFS QBLCDSV’E MV DFS QMSD’E OGED AS ASBGDLHGI; DFS LTSBE ILXS DFS NMIMGVE MV DFS ZMVTE, OGED HLD DMUSDFSV LC B FBVOMCLMGE ZBJ. ASBGDJ LE DFS HLVED DSED: DFSVS LE CM QSVOBCSCD QIBNS LC DFS ZMVIT HMV GUIJ OBDFSOBDLNE.
Походит на галиматью, но на самом деле это послание, написанное с использованием одного из самых популярных способов кодирования. Он называется шифром подстановки и состоит в замене каждой буквы алфавита какой-либо другой буквой: так, a может стать P, t может стать C и т. д. (Я использовал строчные буквы для незашифрованного сообщения – оно называется в криптографии открытым текстом – и прописные буквы для зашифрованного текста, или шифротекста.) Если отправитель и получатель сообщения заранее договорились об используемом шифре подстановки, то получатель сможет дешифровать послания, но всем остальным они будут казаться бессмысленными строками абракадабры.
Самая простая версия этих шифров называется сдвигом Цезаря – в честь Юлия Цезаря, который пользовался им для связи со своими военачальниками во время Галльских войн. Принцип его действия состоит в сдвиге каждой буквы на одинаковое число позиций в алфавите. Например, при сдвиге на 3 a становится D, b становится E и т. д. Вы можете загрузить с веб-сайта «Тайн 4исел» соответствующий файл и вырезать шифровальное колесо для создания этих простых сдвигов Цезаря.
Сдвижка на постоянное число позиций дает вам лишь 25 возможных шифров, так что, если вы понимаете, что сообщение было закодировано с помощью одного из них, становится совсем просто расшифровать его. Существует и лучший способ закодировать сообщение: вместо простого постоянного сдвига всех букв можно перемешать их и разрешить замену любой буквы произвольной другой буквой. Эта методика шифрования сообщений была предложена за несколько веков до Юлия Цезаря, удивительно, что она изложена не в военном руководстве, а в Камасутре. Хотя этот древний трактат на санскрите обычно ассоциируется с описанием плотских удовольствий, в нем описывается и несколько других искусств, которыми должна овладеть женщина: от заклинаний и игры в шахматы до переплетного дела и плотничества. А 45-я глава посвящена искусству тайных сообщений, и объясняется, насколько совершенен может быть шифр подстановки для сокрытия подробностей любовных связей.
В то время как имеется лишь 25 сдвигов Цезаря, число возможных шифров становится заметно больше, когда мы позволяем заменять любую букву любой другой. У нас есть 26 возможностей для того, что будет использовано вместо a, для каждой из этих возможностей имеется выбор из 25 букв для буквы b (одна буква уже была использована для кодирования a). Итак, имеется 26 25 различных способов зашифровать буквы a и b. Если мы продолжим выбирать другие буквы для оставшегося алфавита, то найдем, что имеется
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
различных шифров Камасутры. Как мы видели на с. 40, это число обозначается 26!. Только нужно не забыть вычесть 1 из этого числа, потому что имеется вариант, когда А соответствует а, B соответствует b и так далее вплоть до Z, соответствующего z, что не является шифром. Когда мы вычислим 26! и вычтем 1, то придем к общему числу
403 291 461 126 605 635 583 999 999
различных шифров – более четырехсот миллионов миллиардов миллиардов возможностей.
Отрывок в начале данного раздела был закодирован с помощью одного из этих шифров. Чтобы дать вам представление о числе возможных перестановок, замечу, что напиши я закодированный отрывок с использованием всех различных шифров, то лист бумаги вышел бы за пределы Млечного Пути, нашей Галактики. Компьютер, проверяющий по одному шифру в секунду с момента Большого взрыва, который произошел 13 миллиардов лет назад, к настоящему времени выполнил бы лишь часть работы по проверке всех шифров – и при этом очень малую часть.
Поэтому кажется, что взломать этот шифр невозможно. Разве удастся выяснить, каким из этого огромного количества возможных шифров воспользовался я, чтобы закодировать мое послание? Как это ни поразительно, существует способ сделать это, причем он применяет очень простой раздел математики – подсчет.
Таблица 4.01. Частота употребления букв в обычном английском языке, округленная к ближайшему целому процентному значению. С помощью этой информации можно приступить к взламыванию сообщений, в которых использовался шифр подстановки
Впервые криптоанализ, как называется наука о взламывании кода, был разработан арабами во время правления династии Аббасидов. Многогранный ученый IX в. Якуб аль-Кинди отметил, что в написанном тексте некоторые букы появляются снова и снова, в то время как другие используются редко, как показано выше. Это то, что хорошо знакомо игрокам в скрэббл[13]: за букву E, как за самую распространенную, дается лишь 1 очко, в то время как Z оценивается в 10 очков. В письменных текстах у каждой буквы есть выраженная «индивидуальность» – то, как часто она появляется и в каких комбинациях с другими буквами. Ключевым в анализе аль-Кинди является понимание того, что индивидуальность буквы сохраняется при ее замене другим символом.
Итак, давайте начнем взламывать шифр, который использовался при кодировании текста в начале данного раздела. В таблице 4.02 приведена частота употребления каждой из букв, использованных в зашифрованном тексте.
Таблица 4.02. Частотное распределение букв в зашифрованном тексте
Из таблицы мы видим, что буква S встречается с частотой 13 %, это превосходит любую другую букву в шифротексте. Поэтому есть немалый шанс, что данная буква использовалась для кодирования e. (Разумеется, вам приходится надеяться, что я не выбрал для кодирования отрывок из романа Жоржа Перека «Исчезание», на всем протяжении которого не встречается буква e.) Следующей по употребительности буквой шифротекста, с частотой 12 %, является D. На втором месте по употребительности в английском языке находится буква t, поэтому она будет хорошим предположением для соответствия D. Третьей по частоте в шифротексте является буква B, которая используется в 10 % случаев, есть немалая вероятность, что она заменяет третью по употребительности букву английского языка а.
Давайте подставим эти буквы в текст и посмотрим, что у нас получилось:
a OatFeOatLNLaC, ILXe a QaLCteV MV a QMet, LE a OaXeV MH QatteVCE.
LH FLE QatteVCE aVe OMVe QeVOaCeCt tFaC tFeLVE, Lt LE AeNaGEe tFeJ aVe OaTe ZLtF LTeaE. tFe OatFeOatLNLaC’E QatteVCE, ILXe tFe QaLCteV’E MV tFe QMet’E OGEt Ae AeaGtLHGI; tFe LTeaE ILXe tFe NMIMGVE MV tFe ZMVTE, OGEt HLt tMUetFeV LC a FaVOMCLMGE ZaJ. AeaGtJ LE tFe HLVEt teEt: tFeVe LE CM QeVOaCeCt QIaNe LC tFe ZMVIT HMV GUIJ OatFeOatLNE.
Вы можете сказать, что текст по-прежнему выглядит как тарабарщина, но то обстоятельство, что буква а встречается сама по себе несколько раз, говорит нам, что, вероятно, мы декодировали ее правильно. (Конечно, могло оказаться так, что B заменяет i, в таком случае нам пришлось бы вернуться назад и попытаться еще раз.) Также мы замечаем, что довольно часто сталкиваемся со словом tFe, и можно быть уверенным, что это слово the. На самом деле буква F занимает 6 % шифротекста, а в английском языке буква h встречается в 6 % случаев.
Также мы видим слово Lt, в котором была декодирована лишь вторая буква. Есть лишь два слова из двух букв, заканчивающиеся на t: at и it. Мы уже декодировали а, значит, наверняка L нужно декодировать как i, и наша таблица частотного распределения подтверждает это. L появляется в шифротексте с частотой 8 %, и i встречается в английском языке с частотой 7 % – довольно близкое совпадение. Подобный анализ не является точной наукой, мы должны проявлять достаточную гибкость при использовании этой техники. Но чем длиннее текст, тем лучше будут подстраиваться частоты.
Давайте подставим две наши новые декодировки:
a OatheOatiNiaC, IiXe a QaiCteV MV a QMet, iE a OaXeV MH QatteVCE.
iH hiE QatteVCE aVe OMVe QeVOaCeCt thaC theiVE, it iE AeNaGEe theJ aVe OaTe Zith iTeaE. the OatheOatiNiaC’E QatteVCE, IiXe the QaiCteV’E MV the QMet’E OGEt Ae AeaGtiHGI; the iTeaE IiXe the NMIMGVE MV the ZMVTE, OGEt Hit tMUetheV iC a haVOMCiMGE ZaJ. AeaGtJ iE the HiVEt teEt: theVe iE CM QeVOaCeCt QIaNe iC the ZMVIT HMV GUIJ OatheOatiNE.
Постепенно начинает вырисовываться сообщение в целом. Я предоставляю вам возможность довести дешифровку до конца, декодированный текст приведен в конце главы на случай, если вам захочется проверить, сделано ли все правильно. Дам лишь следующую подсказку: это пара моих любимых отрывков из «Апологии математика», написанной кембриджским ученым Г. Х. Харди. Я прочитал эту книгу, когда учился в школе, она повлияла, наряду с другими обстоятельствами, на мое решение стать математиком.
Простой арифметический прием подсчета букв означает, что любое сообщение, закодированное с помощью шифра подстановки, нельзя сделать секретным. Мария I, королева Шотландии, узнала это на собственном опыте. Она обменивалась посланиями, содержащими планы по убийству королевы Елизаветы I, с другим заговорщиком, Энтони Бабингтоном, при этом буквы в них заменялись странными символами (рис. 4.01).
Рис. 4.01. Шифр Бабингтона
На первый взгляд сообщения, посланные Марией, казались непроницаемыми, но при дворе Елизаветы был один из главных европейских знатоков по взламыванию шифров – Томас Фелиппес. Он не был привлекательным человеком, что ясно из следующего описания: «Малорослый, во всем худосочный, подслеповатый, с темно-золотистыми волосами на голове и светло-золотистой бородой, с оспинами на лице». Многие люди считали, что Фелиппес наверняка был в сговоре с дьяволом, раз обладал способностью понимать такие иероглифы, но он использовал тот же прием частотного анализа. Он взломал код, Мария была арестована и предана суду. Расшифрованные письма были тем свидетельством, которое в конечном счете привело королеву к смертной казни за участие в заговоре.
Как математики способствовали победе во Второй мировой войне
Когда стало понятно, что шифру подстановки присуща эта уязвимость, криптографы начали придумывать более изощренные способы кодирования, чтобы отразить атаки, использующие подсчет букв. Одна идея состояла в варьировании шифра подстановки. Вместо того чтобы использовать лишь один шифр подстановки для всего текста, вы можете поочередно использовать два различных шифра. Таким образом, если вы, к примеру, кодируете слово beef, то буквы е в нем будут закодированы по-разному, поскольку к первой из них применяется один шифр, а ко второй – другой. Может оказаться, что beef будет закодирована как PORK[14]. Чем более безопасным вы желаете сделать ваше сообщение, тем больше различных шифров нужно использовать в нем.
Если вам необходимо взломать шифр Камасутры, то для анализа частоты употребления различных букв в закодированном тексте может оказаться полезной следующая веб-страница: http://simonsingh.net.
Конечно, в криптографии требуется приходить к компромиссу между надежностью шифра и легкостью его использования. В самом надежном виде шифра, называемом одноразовым блокнотом, используется свой шифр подстановки для каждой из букв сообщения. Его почти невозможно взломать, потому что нет совершенно никакого намека, как браться за шифротекст. Этот вид шифра также неудобен и громоздок, ведь приходится использовать свой шифр подстановки для каждой из букв сообщения.
Французский дипломат XVI в. Блез де Виженер считал, что для воспрепятствования частотному анализу будет достаточно переключаться между несколькими шифрами подстановки. Хотя шифр Виженера, как он стал известен, на самом деле является значительно более надежной формой кодирования, его все же можно взломать. Британский математик Чарльз Бэббидж в конечном счете нашел метод, позволяющий сделать это. Бэббидж по праву считается дедушкой компьютерного века: он был убежден, что машины можно использовать для автоматических вычислений, а в лондонском Музее науки можно увидеть реконструкцию его «Разностной машины» – механического аппарата для проведения вычислений. Именно систематический подход к решению задач способствовал тому, что в 1854 г. у него появилась идея, как взломать шифр Виженера.
Метод Бэббиджа задействует важное математическое умение – распознавание закономерностей. Первое, что вам необходимо выяснить, – между сколькими различными шифрами подстановки происходит переключение. Поскольку слово the, как правило, многократно встречается в любом открытом тексте, нужно попытаться заметить повторы одной и той же трехбуквенной последовательности, это может послужить ключом к определению количества шифров подстановки. Например, вы замечаете частые повторы последовательности AWR, причем количество разделяющих символов между различными употреблениями AWR кратно четырем. Это будет хорошим указанием на то, что используется четыре шифра.
Как только у вас есть эта информация, вы можете разбить шифротекст на четыре группы. В первую группу входит первая буква, пятая буква, девятая буква и т. д. Во вторую группу включены вторая буква, шестая буква, десятая буква и т. д. Для каждой из этих четырех групп использовался один шифр подстановки. Так что вы можете применить частотный анализ поочередно к четырем группам и взломать шифр.
После взлома шифра Виженера начался поиск нового способа надежно кодировать сообщения. Когда в 1920-х гг. в Германии была разработана шифровальная машина «Энигма», многие сочли, что было создано совершенное кодирование, которое невозможно взломать.
Принцип работы машины «Энигма» основан на переключении на другой шифр замены всякий раз после кодирования буквы. Так, если бы я захотел зашифровать последовательность аааааа (вероятно, она могла бы означать, что у меня приступ боли), то каждая буква а была бы закодирована по-своему. Элегантность машины «Энигма» заключалась в том, что смена одного шифра другим происходила автоматически и крайне эффективно. Сообщение печаталось на клавиатуре. Над ней находился другой набор букв, называемый «ламповой панелью», загоравшаяся буква отображала то, как кодировалась вводимая буква. Электрическое соединение клавиатуры с ламповой панелью происходило не напрямую, а через три вращающихся диска (ротора), в каждом из которых содержался клубок проводов.
Можно понять принцип работы машины «Энигма», если представить большой цилиндр, составленный из трех вращающихся барабанов. На верхнем основании цилиндра вблизи края расположены 26 отверстий, помеченных буквами алфавита. Чтобы закодировать букву, вы роняете шар в отверстие, соответствующее данной букве. Шар падает в первый барабан, у которого 26 отверстий вдоль обода наверху и 26 отверстий вдоль обода внизу. Верхние и нижние отверстия соединены трубками, которые не ведут напрямую от верхних отверстий к нижним, а извиваются сложным образом. В результате шар, попадающий наверху в барабан, выйдет внизу совершенно в другом положении. Средний и нижний барабан устроены схожим образом, но трубки, соединяющие их верхние и нижние отверстия, проложены по-своему. Когда шар падает из отверстия на дне третьего барабана, он попадает в конечную часть устройства, где 26 отверстий опять-таки помечены буквами алфавита.
Рис. 4.02. Принцип работы шифровальной машины «Энигма»: опустите шар в отверстие наверху, соответствующее кодируемой букве. Барабаны вращаются после каждого кодирования, поэтому буквы всякий раз шифруются по-разному
Если бы устройство оставалось в таком же положении, то его действие сводилось бы к усложненному воспроизведению шифра подстановки. Но гениальность конструкции «Энигмы» состоит в том, что всякий раз, когда шар проходит через цилиндр, первый барабан поворачивается на 1/26 оборота. Поэтому, когда опускается следующий шар, первый барабан пошлет его совершенно по другому пути. Например, в первый раз буква а могла быть закодирована как С, но после того, как первый барабан повернулся на одну позицию, шар, брошенный в отверстие а, выйдет внизу в другом месте. Вот так и действовала машина «Энигма»: после кодирования первой буквы первый вращающийся диск поворачивался на одну позицию.
Вращение дисков в каком-то смысле соответствует одометру: после того как первый диск поворачивается на все 26 позиций и возвращается в начальное положение, он поворачивает второй диск на 1/26 оборота. Итак, имеется 26 26 26 различных способов шифровать буквы. Кроме того, оператор «Энигмы» мог менять порядок расположения дисков, что сводится к умножению количества возможных шифров подстановки на 6 (или 3! различных способов расположения трех дисков).
У каждого оператора была шифровальная книга, которая предписывала ему, в какое положение в начале того или иного дня нужно приводить три диска для кодирования сообщений. Получатель сообщения декодировал его, используя те же настройки из шифровальной книги. По мере усовершенствования «Энигмы» были введены дополнительные усложнения, что в конечном счете привело более чем к 158 миллионам миллионов миллионов различных способов установки машины.
В 1931 г. специалисты французской разведки сумели получить инструкцию по использованию шифровальной машины и пришли в ужас. Казалось, не существует никакой возможности понять из перехватываемого сообщения, в какое положение устанавливались диски для кодирования в тот день. А это было совершенно необходимо для дешифровки сообщения. Но у Франции было соглашение с Польшей по обмену разведывательной информацией, и угроза немецкого вторжения оказала стимулирующее воздействие на умственную деятельность поляков.
Польские математики поняли, что каждая из установок дисков характеризовалась своими особенностями в закодированных сообщениях, и этими закономерностями можно было воспользоваться для декодирования сообщений. Если, к примеру, оператор печатал а, то в зависимости от установки дисков эта буква кодировалась, скажем, как D. Затем первый диск поворачивался на одну позицию. Если оператор еще раз нажимал а и она кодировалась как Z, то в каком-то смысле связь D с Z определяется установкой дисков.
Мы могли бы исследовать это с помощью нашего приспособления. Устанавливая барабаны в требуемое положение и опуская по очереди в каждое из отверстий два шара, мы могли бы составить полный набор взаимосвязей, который мог бы выглядеть следующим образом (см. таблицу 4.03).
Таблица 4.03
Каждая буква появляется в каждой строке один, и только один, раз, потому что каждая строка соответствует одному шифру подстановки.
Как поляки использовали эти взаимосвязи? В любой день все немецкие операторы «Энигмы» должны были использовать одну и ту же установку дисков, которая была записана в их шифровальной книге. Затем они выбирали свое собственное расположение дисков и посылали данные о нем, используя исходную установку дисков из шифровальной книги. Для надежности им было рекомендовано передавать сведения о выбранной установке дважды, что было, в противоположность надежности, фатальной ошибкой. Это давало полякам ключ к тому, какая установка дисков использовалась в машине «Энигма» в тот день.
Группа математиков, находившаяся в особняке Блетчли-парк, который расположен на полпути между Оксфордом и Кембриджем, изучала закономерности, подмеченные математиками в Польше, и нашла способ автоматизировать поиск настроек. При этом использовалась электронно-механическая машина под названием «Бомба». Говорят, что эти математики сократили Вторую мировую войну на два года и спасли бессчетное количество жизней. А построенные ими машины положили начало компьютерам, на которые мы полагаемся в наши дни.
Для онлайн-моделирования работы машины «Энигма» воспользуйтесь ссылкой http://bit.ly/BletchleyPark. С веб-сайта «Тайн 4исел» вы можете загрузить PDF-файл с инструкциями, как сделать собственную машину «Энигма».
Передача сообщения на расстояние
Независимо от того, закодировано ваше послание или нет, вам необходимо найти способ передать его из одного места в другое. Во многих культурах, от китайцев до американских индейцев, использовались дымовые сигналы как средство сообщения на большие расстояния. Говорят, что с помощью костров, разводившихся в башнях Великой Китайской стены, можно было передать послание на 500 км за несколько часов.
Визуальные коды, основанные на флагах, восходят к 1684 г., когда Роберт Гук, один из самых знаменитых ученых ХVIIв., представил эту идею Лондонскому Королевскому обществу. Изобретение телескопа сделало возможным передавать оптические сигналы на большие расстояния, но Гука подстегнуло то, что привело к многим техническим достижениям, – война. В предшествовавшем году Вена чуть не была захвачена турецкой армией, в то время как вся Европа не знала об этой опасности. Внезапно стало крайне необходимым придумать способ быстрой передачи сообщений на большие расстояния.
Гук предложил возвести в Европе сеть башен. Если какая-то из них передавала сообщение, то все башни, находившиеся в поле видимости, повторяли его – это было двумерной версией того, как послания отправлялись вдоль Великой Китайской стены. Метод передачи сообщений не был особенно изощренным – большие специальные знаки поднимались наверх посредством веревок. Данное предложение Гука не было осуществлено, и до практического воплощения схожей идеи прошло сто лет.
В 1791 г. братья Клод и Игнас Шаппы построили систему башен, чтобы предоставить французскому революционному правительству быструю связь (хотя одна из башен была атакована толпой, решившей, что ею пользовались роялисты для заговора). Идея была основана на системе знаков, которой пользовались братья в детстве для передачи сообщений между общежитиями в школе со строгими порядками, где они обучались. Клод и Игнас экспериментировали с множеством различных способов визуальной передачи сообщений. В конце они остановились на деревянных планках, фиксировавшихся под разными углами, которые мог легко различить человеческий глаз.
Рис. 4.03. Код братьев Шапп передавался с помощью шарнирно скрепленных деревянных планок
Братья разработали код для подвижной системы шарнирно скрепленных деревянных планок, чтобы обозначать различные буквы или некоторые слова. Основная поперечина могла быть установлена под четырьмя различными углами, в то время как у каждой из двух меньших планок было семь различных положений, что в общей сложности предоставляло возможность передавать 7 7 4 = 196 различных символов. Хотя часть кода использовалась для передачи публичных сообщений, 92 символа, объединенные в пары, представляли секретный код, что давало 92 92 = 8464 различных слова и фразы.
Рис. 4.04. Представление букв и цифр в коммуникационной системе братьев Шапп
Во время первого испытания 2 марта 1791 г. братья Шапп успешно передали сообщение «Если преуспеете, то покроете себя славой» на расстояние в 10 миль (160 км). Правительство было весьма впечатлено предложением братьев, и через четыре года во Франции была воздвигнута система башен и планок, протянувшаяся через всю страну. В 1794 г. одна из линий башен успешно передала менее чем за час на расстояние в 143 мили (230 км) сообщение о том, что французы отвоевали у австрийцев город Конде-сюр-л’Эско. К сожалению, успех не привел к славе вопреки предсказанию первого сообщения. Клод Шапп впал в такую депрессию от слухов, будто он украл многое из существовавшей у военных семафорной системы, что утопился в колодце.
Но вскоре деревянные планки на верхушках башен стали вытесняться флагами, их же стали использовать моряки для обмена сообщениями на море, ведь требовалось только помахать ими, находясь в поле видимости других судов. Наверное, самое знаменитое кодированное сообщение, которое было послано кораблям посредством флагов, изображено на рис. 4.05. Оно было передано 21 октября 1805 г. в 11:45.
Рис. 4.05. Знаменитое послание адмирала Нельсона «Англия ждет, что каждый выполнит свой долг»
Это сообщение Горацио Нельсон поднял на флагмане Королевского флота «Виктория» перед началом решающего Трафальгарского сражения. В британском флоте использовался секретный код, автором которого был другой адмирал, сэр Хоум Попхэм. Кодовые словари имелись на каждом из кораблей Королевского флота, эти книги были начинены свинцом, так что в случае захвата судна кодовый словарь можно было выбросить за борт, чтобы врагу не достался британский секретный шифр.
Код был основан на комбинациях десяти различных флагов, причем каждый из них представлял одну из цифр от 0 до 9. Флаги поднимались на мачты корабля тройками, таким образом обозначая число от 000 до 999. Получатель сообщения глядел в свой кодовый словарь, чтобы понять, какое из слов было зашифровано. England (Англия) кодировалась числом 253, а для слова every (каждый) использовалось число 261. Некоторых слов, к примеру duty (долг), не было в словаре, и их нужно было набрать флагами, зарезервированными для отдельных букв. Первоначально Нельсон хотел послать сообщение «Англия верит, что каждый выполнит свой долг», имея в виду, что Англия была уверена. Но сигнальный офицер, лейтенант Джон Паско, не мог найти слова confides (верит) в кодовом словаре. Вместо того чтобы набирать его по буквам, он вежливо предложил Нельсону употребить имевшееся в словаре слово expects (ждет), как более уместное.
Использование флагов было вытеснено на обочину в связи с развитием телекоммуникаций, но и в нашем современном мире моряки обучаются семафорной азбуке, в которой букве сопоставляется положение рук с флажками. У каждой руки при этом имеется восемь различных положений, что приводит к 8 8 = 64 возможным символам.
Рис. 4.06. Семафорная азбука
Чтобы узнать, как выглядит то или иное сообщение на семафоре, посетите сайт http://bit.ly/Scoutsemaphore или воспользуйтесь смартфоном и сосканируйте QR-код.
NUJV!The Beatles на обложке своего альбома Help!, очевидно, используют семафор, чтобы объявить название. Но, если вы декодируете показываемые ими семафорные знаки, то получится не HELP, a NUJV (рис. 4.07). Роберт Фримен, в голову которому пришла идея о семафоре на обложке, объяснял: «Когда дело дошло до фотографирования, то расположение рук с правильными буквами выглядело не слишком хорошо. Поэтому мы решили импровизировать, и остановились на визуально оптимальном положении рук». На самом деле они должны были показывать так (рис. 4.08):
Рис. 4.07
Рис. 4.08
Как мы увидим, The Beatles – вовсе не единственный ансамбль, неправильно использовавший код на обложке альбома.
Рис. 4.09. Знаете ли вы, что пацифистский символ, использующийся Движением за ядерное разоружение, на самом деле задействует семафорную азбуку? Он представляет буквы N и D (Nuclear Disarmament, ядерное разоружение), объединенные в один символ
Какое сообщение закодировано в Симфонии № 5 Бетховена?
Читать бесплатно другие книги:
