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

123456789 раз по X

Иногда самые простые идеи приводят к загадочным результатам. Попробуйте умножить 123456789 на 1, 2, 3, 4, 5, 6, 7, 8 и 9. Что вы заметили? Когда закономерность перестает работать?

Ответы см. в главе «Загадки разгаданные». Расширение темы в главе «123456789 раз по X. Продолжение».

Знак одного. Часть третья

Из мемуаров доктора Ватсапа

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

– Я могу получить 8 из двух единиц, не прибегая к помощи гипотетического выражения для 7, – объявил я. – Вот так:

Но даже под угрозой смерти я не в состоянии получить 7.

– Действительно, это число, судя по всему, является камнем преткновения, – согласился со мной Сомс. – Но ваш результат позволяет нам продвинуться и другими способами:

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

– Нет-нет, Сомс, вы меня убедили!

– Но теперь у нас образовалось еще две лакуны на 12 и 13. Однако, Ватсап, я подозреваю, что эти проблемы взаимосвязаны. Так, посмотрим… Ну да,

а 15 на основе двух единиц у нас уже есть. Тогда

и далее

и, наконец,

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

– Мне невыносимо стыдно, что я не увидел этого сразу.

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

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

– Во всяком случае, – сказал я, – если нам удастся выразить какое-то целое число при помощи двух единиц, то теперь мы сможем выразить при помощи четырех единиц все числа в диапазоне от n – 17 до n + 17.

– Вот именно, Ватсап. Наша задача упрощается с каждой минутой. Все, что нам нужно, – это последовательность чисел, каждое из которых превосходит предыдущее не более чем на 35, так, чтобы эти интервалы с двух сторон перекрывали пробел. Это позволит нам добраться до наибольшего из таких чисел плюс 17.

– Что означает… – начал я…

– Что мы должны действовать систематически!

– Именно.

– Мы уже добрались… напомните мне, Ватсап. Загляните в свои обширные записи.

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

– Мы дошли до 32, Сомс, если учесть замечание, которое вы мимоходом сделали во время поиска выражения для 7.

– И разумеется,

– сказал он. – Очень хорошо. Таким образом, в идеале нам нужно выразить числа 68, 103, 138 и т. д. через две единицы. Но мы можем пользоваться при этом готовыми выражениями для маленьких чисел, если так будет удобнее. Лишь бы разница между двумя соседними числами не была больше 35.

Несколько часов усиленных расчетов – и новые кипы бумаги – дали нам короткий, но важный список:

Но на этом все и застопорилось.

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

– Очень может быть, Сомс.

Сомс кивнул и записал:

105 = 7!!

Затем, в порыве внезапного озарения, добавил:

И воскликнул:

– Если нам удастся найти способ записать 18 при помощи двух единиц, то доступный нам диапазон вокруг целого числа, выражаемого через две единицы, увеличится: мы тогда сможем гарантировать число от n – 20 до n + 20, – он прервался, чтобы перевести дух, и добавил: – Если же нет, то пропущенными в этом диапазоне окажутся только числа n – 18 и n + 18, которые нам, может быть, удастся выразить как-то иначе.

– Мне кажется, пора подвести промежуточный итог, – сказал я и еще раз внимательно просмотрел наши накопившиеся каракули. – По-моему, мы уже выразили через четыре единицы все числа от 1 до 33. Далее

требуют только двух единиц, так что мы немедленно заполняем все пропуски между 26 и 61. Возникает пробел на 62 (потому что это 44 + 18, а на выражении 18 через две единицы мы застряли), но 63 и 64 у нас есть. Далее, опираясь на 80, мы можем добраться до 97. На 98 опять возникает пробел, но 99 и 100 можно получить.

– И намного проще, кстати говоря, – заметил Сомс:

99 = 11/0,1 0,1;

100 = 1/(0,1 0,1);

101 = 1/(0,1 0,1) + 1.

– Таким образом, у нас есть все вплоть до 100, – сказал я, – за исключением 62 и 98.

– Но о 98 позаботится 105, вместе со всеми остальными числами вплоть до 122, – сказал Сомс.

– О, я и забыл, что у нас есть 105 из двух единиц.

– А поскольку 120 = 5! то есть тоже выражается через две единицы, мы можем добраться до 137. Более того, у нас есть еще 139 и 140.

– Так что единственные пробелы до 140 – это 62 и 138, – сказал я.

– Похоже на то, – сказал Сомс. – Интересно, можно ли заполнить эти пробелы каким-то другим способом?

Сможете ли вы найти способ записать 62 и 138 при помощи четырех единиц, не используя ничего более эзотерического, чем те функции, которые Сомс и Ватсап уже использовали? Ответ см. в главе «Загадки разгаданные».

Сомс и Ватсап все еще не закончили. Но финал уже близок: «Знак одного» завершается в главе «Знак одного. Часть четвертая – завершение».

Номера такси

Сриниваса Рамануджан – индийский математик-самоучка с поразительным талантом к формулам, как правило очень странным формулам, обладавшим, однако, своеобразной необычной красотой. В 1914 г. математики Годфри Харолд Харди и Джон Эденсор Литтлвуд из Кембриджа привезли его в Англию. К 1919 г. у него уже были неизлечимо больные легкие, и в 1920 г. он умер в Индии. Харди писал:

«Помню, как я однажды поехал навестить его, когда он лежал больной в Путни. Я приехал в такси номер 1729 и заметил вскользь, что номер этот показался мне довольно скучным и что я надеюсь, что это не дурное предзнаменование. „Нет, – ответил он, – это очень интересный номер; это наименьшее число, которое можно выразить в виде суммы двух [положительных] кубов двумя разными способами“».

Наблюдение о том, что

1729 = 1 + 12 = 9 + 10,

впервые опубликовал Бернар Френикль де Бесси в 1657 г. Если разрешить отрицательные кубы, то наименьшим таким числом будет

91 = 6 + (–5) = 4 + 3.

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

В 1979 г. Харди и Э. М. Райт доказали, что некоторые числа могут быть выражены в виде суммы произвольно большого числа положительных кубов, так что Ta (n) существует для любых n. Однако вплоть до настоящего времени известны лишь первые шесть таких чисел:

Ta (1) = 2 = 1 + 13;

Ta (2) = 1729 = 1 + 12 = 9 + 10;

Ta (3) = 87539319 = 167 + 436 = 228 + 423 = 255 + 414;

Ta (4) = 6963472309248 = 2421 + 19083 = 54363 + 18948 = 10200 + 18072 = 13322 + 166308;

Ta (5) = 48988659276962496 = 3887 + 3657573 = 107839 + 362753 = 205292 + 342952 = 221424 + 336588 = 231518 + 331954;

Ta (6) = 24153319581254312065344 = 582162 + 28906206 = 3064173 + 28894803 = 8519281 + 28657487 = 16218068 + 27093208 = 17492496 + 26590452 = 18289922 + 26224366.

Ta (3) открыл Джон Лич в 1957 г. Ta (4) нашли Э. Розенстил, Дж. А. Дардис и К. Р. Розенстил в 1991 г. Ta (5) обнаружил Дж. А. Дардис в 1994 г. и подтвердил Дэвид Уилсон в 1999 г. В 2003 г. К. С. Калуд, Э. Калуд и М. Дж. Диннин установили, что приведенное выше число, вероятно, является Ta (6), а в 2008 г. Уве Холлербах опубликовал доказательство.

Волна перемещения

Математические исследования верхом?

Почему бы нет? Вдохновение может осенить где угодно. Выбирать не приходится.

В 1834 г. шотландский инженер-кораблестроитель Джон Скотт Рассел, ехавший на лошади вдоль канала, обратил внимание на поразительное явление:

«Я наблюдал за движением лодки, которую стремительно тянула по узкому каналу пара лошадей, как вдруг лодка остановилась – лодка, но не та масса воды в канале, которую она увлекла и приводила в движение; эта вода собралась вокруг носа судна в состоянии неистового возбуждения, затем внезапно оторвалась от него и покатилась вперед с огромной скоростью, принимая форму большого одиночного возвышения, округлой, гладкой и четко очерченной водяной массы, которая продолжила движение вдоль канала без всякого видимого изменения формы или снижения скорости. Я последовал за ней верхом и догнал; она катилась дальше со скоростью примерно 13 или 15 км/ч, сохраняя первоначальную форму, размером около 9 м в длину и 30–45 см в высоту. Ее высота постепенно снижалась, и после преследования на протяжении 1,5–3 км я потерял ее среди извивов канала. Вот такой в августе 1834 г. была моя первая случайная встреча с этим исключительным и красивым явлением, которое я назвал волной перемещения».

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

Эти открытия поставили физиков того времени в тупик, потому что совершенно не поддавались объяснению с позиции тогдашних взглядов на поведение жидкостей. Более того, видный астроном Джордж Эйри и ведущий специалист по динамике жидкостей Джордж Стокс долго не верили, что такая волна существует. Сегодня мы знаем, что Рассел был прав. В некоторых обстоятельствах нелинейные эффекты, неизвестные математикам того времени, компенсируют тенденцию всякой волны к расхождению, потому что скорость движения волны зависит от частоты колебаний. В этих эффектах первыми разобрались лорд Рэлей и Жозеф Буссинеск примерно в 1870 г.

В 1895 г. Дидерик Кортевег и Густав де Врис предложили уравнение Кортевега – де Вриса, в которое вошли подобные эффекты, и показали, что у него есть обособленные (солитарные) волновые решения. Аналогичные результаты были получены для других уравнений математической физики, и феномен получил новое название: солитон. Серия крупных открытий позволила Питеру Лаксу сформулировать очень общие условия, при которых уравнения имеют обособленные решения, и объяснить эффект туннелирования. Математически этот процесс сильно отличается от того, как взаимодействуют мелководные волны, к примеру, на пруду, когда их формы складываются; все это – прямое следствие математической формы волнового уравнения. Солитоноподобные явления наблюдают во многих областях науки – от ДНК до волоконной оптики. Именно этим объясняется существование широкого спектра явлений со странными названиями вроде «бризер», «кинк» и «осциллон».

Есть также весьма соблазнительная идея, которую пока никому не удалось заставить работать. Элементарные частицы в квантовой механике соединяют в себе каким-то образом две разные несовместимые на первый взгляд характеристики. Как и большинство объектов квантового уровня, они представляют собой волны, но при этом умеют соединяться в частицеподобные блоки. Физики давно пытаются отыскать уравнения, которые согласовывались бы со структурой квантовой механики, но допускали существование солитонов. Лучшее, чего им на сегодняшний день удалось достичь, – это уравнение, описывающее инстантон, который можно интерпретировать как частицу с очень коротким временем жизни, которая возникает из ниоткуда и немедленно после этого исчезает.

Загадка песков

Песчаные дюны образуют самые разные узоры: линейные, поперечные, параболические и т. п. Одна из наиболее интересных их разновидностей – бархан, или серповидная дюна. Название происходит из Туркестана; говорят, что в геологию его ввел русский натуралист Александр фон Миддендорф. Барханы можно найти в Египте, Намибии, Перу… и даже на Марсе. Они имеют серповидную форму, бывают разных размеров и, самое главное, движутся. Они собираются группами, взаимодействуют друг с другом, делятся и соединяются. В последние годы математическое моделирование помогло многое понять в их форме и поведении, но многие стороны их жизни до сих пор остаются загадкой.

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

Барханы ведут себя как солитоны (см. предыдущую тему), хотя технически отличаются в некоторых деталях. Ветер, перенося песок, постепенно сдвигает дюны, причем маленькие дюны перемещаются быстрее больших. Если маленькая дюна догоняет большую, то сначала она как будто поглощается ею, но через некоторое время большой бархан «выплевывает» из себя другой, маленький, как будто первый маленький бархан проделал в большом туннель и прошел его насквозь. После этого маленький бархан продолжает свой бег, оставляя ковыляющего монстра позади.

Вейт Шваммле и Ханс Херман опубликовали на эту тему статью, где говорят о сходствах и различиях между столкновениями барханов и солитонами. На рисунке показано, что происходит, когда встречаются две дюны примерно одинаковых размеров. Первоначально (a) меньшая дюна находится позади более крупной, но движется быстрее. Она догоняет большую дюну (b) и взбирается по ее наветренному склону, но застревает на полпути (c). Затем фронтальная часть дюны разделяется, чтобы сформировать другую небольшую дюну (d).

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

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

для эскимосов

Почему в Арктике авно всего лишь 3?

На холоде все съеживается.

Знак одного. Часть четвертая – завершение

Из мемуаров доктора Ватсапа

– Да, это острая штучка, – пробормотал я.

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

Я убрал острое лакомство обратно в буфет вместе с банкой.

– У нас и правда есть возможность, – заметил Сомс, – умножать числа на 3, 9 или 10 с использованием всего одной дополнительной единицы. Для этого достаточно разделить число на (0,(1)), 0, (1) или 0,1.

– Тогда у меня есть вариант! – воскликнул я.

62 = 63 – 1 = 7 9–1 = 7/0,(1) – 1,

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

– И у нас остается одна проблема – 138.

– Так, это 3 46, – размышлял я вслух. – Можем мы получить 46, используя всего три единицы? Тогда мы могли бы разделить его на(0,(1)), как вы предлагали.

Систематическое исследование разных вариантов округления последовательных квадратных корней из факториалов привело нас к неожиданному открытию: 46 можно получить всего из двух единиц. Я покажу здесь только решение: на пути к нему нам пришлось обследовать множество тупиков и потерпеть немало неудач. Начать можно, к примеру, с представления 7 через две единицы:

Затем заметим, что

Двигаясь обратно и подставляя формулы для соответствующих чисел, получим выражение для 138 через три единицы.

– Записать все это явно, Сомс?

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

Вдохновленный неожиданным успехом, я хотел продолжить наш список еще дальше, но Сомс только пожал плечами:

– Может, эта проблема заслуживает дальнейшего рассмотрения. А может, и нет.

Внезапно меня осенило:

– А не можем ли мы доказать, что любое число можно получить из четырех – или меньше – единиц путем подбора полов и потолков повторяющихся квадратных корней из факториалов?

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

Прямо на глазах он вновь начал погружаться в депрессию. В отчаянии я предложил:

– Вы могли бы попробовать логарифмы, Сомс.

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

– Нет-нет, я говорил об использовании логарифмов для облегчения вычислений, а не в формулах… – но Сомс не обратил внимания на мои протесты.

– Вспомните, что представляет собой экспоненциальная функция:

exp (x) = e^x, где e = 2,71828…

– Обратным по отношению к этой функции является натуральный логарифм

ln (x) = значение y, удовлетворяющее exp (y) = x.

– Не правда ли, Ватсап?

Я подтвердил, что, насколько мне известно, дело обстоит именно так.

– Тогда мы просто заметим, что

что несложно доказать.

Я посмотрел на него с открытым ртом, но сумел-таки выдавить из себя полузадушенное:

– Конечно, Сомс.

– В результате мы можем последовательно записать:

и…

Я поспешно схватил его за правую руку.

– Да, Сомс, я понимаю. Это слегка замаскированная версия метода Пеано, который мы ранее отвергли именно из-за его тривиальности.

– Так что, Ватсап, если разрешить экспоненциальные выражения и логарифмы, игра сразу же закончится.

Я согласился – не без грусти, поскольку он сразу же взял свой кларнет и вновь завел бесконечную пьесу какого-то малоизвестного восточноевропейского композитора, в которой не было ни ритма, ни мелодии. Звук походил на вопль кота, попавшего между валками для отжимания белья. Кота, которому медведь наступил на ухо. Притом охрипшего.

Черное настроение поглотило Сомса окончательно и бесповоротно.

На этом заканчивается «Знак одного».

Правда, я так и не рассказал вам, что такое субфакториал. Ну, ничего, в следующий раз.

Серьезный беспорядок

Пора объяснить, что такое субфакториалы.

Предположим, что у каждой из n дам имеется шляпка. Все они складывают свои шляпки в одно место, затем каждая из них берет какую-нибудь случайную шляпку и надевает на себя. Сколькими способами можно это сделать, чтобы ни на одной из дам не оказалось ее собственной шляпки? Такое размещение называется беспорядком.

К примеру, если дам три – скажем, Александра, Бетани и Валерия, – то шляпки между ними можно распределить шестью способами:

АБВ АВБ БАВ БВА ВАБ ВБА.

Для АБВ и АВБ Александра получает свою собственную шляпку, так что беспорядка не возникает. Для БАВ собственную шляпку получает Валерия, а для ВБА – Бетани. Это оставляет нам два варианта беспорядка: БАВ и ВАБ.

Если дам четыре – предположим, к группе присоединилась еще Грейс – существует 24 варианта расстановки:

однако в 15 из них (вычеркнутые) кто-нибудь из дам получает свою собственную шляпку. (Убираем все с А в первой позиции, с Б во второй, с В в третьей и с Г в четвертой.) В результате получаем 9 вариантов беспорядка.

Число вариантов беспорядка из n объектов и есть субфакториал (обозначается! n или n ). У этого понятия множество определений. Простейшее из них, вероятно,

Первые значения этой величины

Бросание монетки – несправедливый жребий

Бросание монетки – фундамент теории вероятностей, поскольку орел или решка выпадают на ней с равной вероятностью. Бросание монетки считается живым воплощением случайности. С другой стороны, моделью монетки может служить простая механическая система, и ее поведение полностью определяется начальными условиями броска – в первую очередь вертикальной скоростью, начальной скоростью вращения и ориентацией оси вращения. Это, собственно говоря, делает движение монетки неслучайным. Так откуда же берется случайность в бросание монетки? Я вернусь к этому вопросу после описания открытия, имеющего ко всему этому непосредственное отношение.

Перси Диаконис, Сьюзен Холмс и Ричард Монтгомери показали, что на самом деле бросание монетки – не совсем «честная» жеребьевка. Существует небольшой, но заметный сдвиг вероятности: при бросании монетка с несколько большей вероятностью падает на ту же сторону, на которой она лежала на большом пальце. В реальности вероятность ее падения именно в таком положении составляет приблизительно 51 %. В своем исследовании ученые предполагали, что монетка при падении не подскакивает, что разумно при падении на землю, особенно в траву, или для того случая, когда ее ловят на лету, но не тогда, когда она падает на деревянный стол.

Вероятность 51 % становится статистически значимой только после примерно 250 000 бросков. Возникает этот сдвиг потому, что ось, вокруг которой вращается монетка, может и не быть горизонтальной. В предельном случае представьте, что ось располагается под прямым углом к монетке, так что монетка, вращаясь, всегда остается горизонтальной, как гончарный круг. В таком случае она всегда будет приземляться той же стороной, которой лежала, то есть вероятность ее непереворачивания составит 100 %. Другой предельный случай – ось горизонтальна, и монетка кувыркается в воздухе. Хотя в принципе конечное состояние монетки в этом случае определяется начальной вертикальной скоростью и скоростью вращения в воздухе, даже небольшие ошибки в этих параметрах приводят к тому, что монетка падает той же стороной кверху лишь в 50 % случаев. При таких бросках небоьшие ошибки приводят к случайному взаимодействию механической системы и монетки.

Как правило, ось вращения монетки не находится ни в одном из крайних положений, а расположена в каком-то промежуточном, близком к горизонтали. Поэтому возникает легкий сдвиг вероятности в сторону падения той же стороной вверх. Подробные расчеты дали 51 % вероятности. Эксперименты с монеткобросательным автоматом подтвердили этот результат с разумной достоверностью.

На практике бросание настоящей монетки все-таки дает случайный результат с 50 % вероятностью, причем вовсе не по приведенным причинам. Дело в том, что начальная ориентация монетки на пальце тоже случайна. Если говорить о длинных сериях, то монетка в половине случаев взлетает орлом кверху, а в половине – решкой кверху. Это снимает сдвиг на 1 %, потому что при броске неизвестно, из какого именно положения стартует монетка.

Дополнительную информацию см. в главе «Загадки разгаданные».

Покер по почте

Предположим, что Алиса и Боб – традиционные участники криптографической переписки – хотят сыграть в покер, точнее, в пятикарточный стад. Но Алиса живет в Австралии, в Алис-Спрингс, а Боб – в Англии, в Боббингтоне. Но возможно, они могли бы пересылать друг другу карты по почте? Главная проблема – как раздать карты, то есть дать каждому игроку «в руки» по пять карт. Как могут при этом оба игрока быть уверены, что каждому из них достались карты из одной колоды и что второй игрок их не знает?

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

Как ни удивительно, способ играть в такие карточные игры, как покер, по переписке, по телефону или через Интернет существует, причем без всякой опасности, что кто-то из игроков при этом обманывает. Алиса и Боб могут создать шифр, воспользовавшись теорией чисел, и прибегнуть к сложному обмену посланиями. Такой метод известен как «протокол с нулевым разглашением» – способ убедить собеседника в том, что ты обладаешь каким-то конкретным знанием, не раскрывая, в чем это знание состоит. Так, вы могли бы убедить онлайновую банковскую систему в том, что знаете секретный код, записанный на обороте кредитной карты, не передавая при этом никакой полезной информации о самом коде.

Гостиницы часто хранят ценности гостей в небольших сейфовых ячейках в холле. Для обеспечения безопасности каждая такая ячейка снабжается двумя ключами: один хранится у администратора, другой выдается постояльцу. Чтобы открыть сейф, необходимы оба ключа. Алиса и Боб могут воспользоваться аналогичной схемой:

1. Алиса раскладывает карты по одной в 52 ящичка и запирает их на кодовые замки, ключи к которым известны только ей. Затем она почтой пересылает все ящички Бобу.

2. Боб (который не может отпереть ящички и посмотреть, что за карты в них лежат) выбирает пять ящичков и высылает обратно Алисе. Она отпирает их и получает свои пять карт.

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

4. Алиса отпирает свои замки и возвращает ящички Бобу. Теперь он может отпереть их и получить свои пять карт.

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

Алиса и Боб перевели свою методику игры на язык математики, выделив ее существенные черты. Они представили карточную колоду согласованным набором из 52 чисел. Кодовые замки Алисы обозначаются шифром A, известным только ей. Это функция, математическое правило, превращающее число карты c в другое число Ac. (Я беру на себя вольность не писать всякий раз A (c), чтобы не пришлось говорить о «композиции» функций.) Алисе известен также обратный шифр A^–1, который переводит Ac обратно в c. То есть

A¹Ac = c.

Боб не знает ни A, ни A^–1.

Аналогично замки Боба соответствуют шифрам B и B^–1, известным только ему, таким, что B^–1Bc = c.

С учетом этих предварительных замечаний метод соответствует следующей процедуре:

1. Алиса пересылает все 52 числа Ac₁, …, Ac₅₂ Бобу. Он понятия не имеет, каким картам эти числа соответствуют; по существу, Алиса перетасовала колоду.

2. Боб «сдает» пять карт Алисе и пять самому себе. Он высылает Алисе ее карты. Чтобы упростить запись, рассмотрим лишь одну из этих карт, обозначив ее Ac. Алиса может выяснить значение c, применив к полученному числу A^–1, так что она знает, какие карты ей сданы.

3. Бобу необходимо выяснить, какие карты он выбрал для себя, но только Алиса знает, как извлечь истинные значения из зашифрованных. Но Боб не может послать свои карты Алисе, потому что тогда она будет знать, что у него в руке. Поэтому к каждой своей карте Ad он применяет свое шифровальное правило, чтобы получить BAd, и высылает результат такой обработки Алисе.

4. Алиса может вновь применить свое правило A^–1, чтобы «снять замок», но на этот раз ее ждет засада: результат будет равен A^–1BAd.

В обычной алгебре мы могли бы поменять A^–1 и B местами, чтобы получить

BA^–1Ad,

что равняется Bd.

После этого Алиса могла бы выслать результат обратно Бобу, а тот, в свою очередь, применил бы B^–1, чтобы получить d.

Однако функции нельзя переставлять таким образом. К примеру, если Ac = c + 1 (и, соответственно, A^–1c = c – 1) и Bc = c, то A^–1Bc = Bc – 1 = c^– 1, тогда как

BA^–1c = (A ^–1c) = (c – 1) = c^– 2c + 1,

то есть совсем не то же самое.

Чтобы обойти это препятствие, следует избегать подобных функций и выбирать такие методы шифрования, для которых A^–1B = BA^–1. В этом случае говорят, что для функций A и B действует коммутативный закон, поскольку все это несложно привести к эквивалентному условию AB = BA. Обратите внимание: в описанном нами физическом методе замки Алисы и Боба и правда позволяют перестановку. Их можно навешивать и снимать в любом порядке, результат будет тот же: ящичек с двумя замками.

Таким образом, Алиса и Боб могут играть в покер по переписке, если сумеют придумать два допускающих перестановку шифра A и B, таких, чтобы алгоритм расшифровки A –1 был известен только Алисе, а алгоритм B^–1 – только Бобу.

Боб и Алиса выбирают большое простое число p, которое может быть опубликовано и известно всем. Они согласуют также 52 числа c₁, …, c₅₂ (mod p), которые будут представлять карты.

Алиса выбирает некоторое число a от 1 до p – 2 и определяет свою кодирующую функцию A как Ac = c^a (mod p).

Пользуясь базовой теорией чисел, можно сказать, что обратная (декодирующая) функция имеет вид

A^–1c= c^a' (mod p)

для некоего числа a', которое она может вычислить. Алиса держит и a, и a' в секрете.

Аналогично Боб выбирает себе число b и определяет свою кодирующую функцию B как Bc = c^b (mod p) и обратную к ней

B^–1c = c^b' (mod p)

для числа b', которое он может вычислить. Он держит b и b' в секрете.

Кодирующие функции A и B подчиняются коммуникативному закону, поскольку

ABc = A (c^b) = (c^b)^a = c^ba = c^ab = (c^a)^b = B (c^a) = BAc,

где все равенства выполняются (mod p). Поэтому Алиса и Боб могут использовать A и B описанным образом.

Исключение невозможного

Из мемуаров доктора Ватсапа

– Ватсап!

– А? Что? Вы это мне, Сомс?

– Сколько раз можно повторять, Ватсап, чтобы вы не приносили журнал The Strand в этот дом!

– Но… как…

– Вы знаете мои методы. Вы нетерпеливо постукивали пальцами, как делаете обычно, пока меня дожидаетесь. При этом вы то и дело поглядывали на свернутую газету, которая торчит у вас из кармана пальто. Газета эта слишком толста для Daily Reporter, хотя именно это название красуется у нее на первой полосе, так что в нее, наверное, завернут какой-то журнал. А поскольку вы по привычке прячете от меня лишь один журнал, сомневаться в его природе не приходится.

– Простите, Сомс, я просто надеялся получить кое-какие сравнительные данные о методах исследования из произведений коллеги… э-э… шарлатана из дома напротив.

– Тьфу! Этот человек – мошенник! Жулик, называющий себя детективом!

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