Участие в играх является существенной частью человеческого опыта. Игры – это безопасный способ исследования ситуаций, происходящих в реальной жизни. «Монополия» – это микрокосм экономики, шахматы – поле сражения 8 × 8, покер – упражнение в оценке риска. Игры позволяют нам научиться предсказанию того, как при выполнении определенных правил будут развиваться события, и соответственному планированию своих действий. Благодаря им мы знакомимся со случайностями и непредсказуемостью, играющими столь большую роль в игре жизни, организуемой природой. От древних цивилизаций во всем мире нам досталось в наследство захватывающее разнообразие игр. Камешки, бросаемые в песок, палочки, подкидываемые в воздух, жетоны, вставляемые в прорези в деревянных колодках, соревнования с помощью рук и карт с изображениями на них… От древней игры манкала до «Монополии», от японской игры го до покерных столов Лас-Вегаса – в играх неизменно побеждает тот, кто лучше следует математическому, аналитическому подходу. В настоящей главе я покажу вам, как математика может быть секретным оружием к победной серии.

 

Как стать чемпионом мира по игре «Камень, ножницы, бумага»?

«Дзян-кэн-пон» в Японии. «Ро-шам-бо» в Калифорнии. «Кай-бай-бо» в Корее. «Чин-чон-ча» в Южной Африке. В игру «Камень, ножницы, бумага» играют по всему миру.

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

Логическое обоснование первых двух побед достаточно очевидно: камень затупляет ножницы, ножницы режут бумагу. Но почему камень проигрывает бумаге? Лист бумаги – не слишком-то хорошая защита от камня, запущенного в вас. Но возможно, эта условность дошла до нас из Древнего Китая. В те дни прошение, подаваемое императору, символизировалось камнем. Император указывал на то, принял или нет он прошение, посредством листа бумаги, помещаемого под камнем или над ним. Если камень был покрыт листом бумаги, то в прошении отказывалось, а подавший его проигрывал дело.

Происхождение этой игры довольно трудно проследить. Есть свидетельства, что в нее играли на Дальнем Востоке, она была распространена и у кельтских племен и, вероятно, даже у древних египтян, которые любили игры на пальцах. Но все эти цивилизации уступили первенство в изобретении этой игры разновидности ящериц, которая прибегала к ней в борьбе за выживание задолго до того, как Homo sapiens начал делать жесты.

На западном побережье Америки обитает вид ящериц Uta stansburiana, более известный как обыкновенная пятнистая ящерица. У самца этого вида три возможных окраса – оранжевый, синий и желтый, и у каждого из них различная тактика спаривания. Оранжевые ящерицы – самые сильные. Они нападают на синих ящериц и побеждают их. Синие ящерицы больше желтых и охотно вступают с ними в битвы, нанося соперникам поражения. Но, хотя желтые самцы меньше синих и оранжевых, они выглядят как самки, что сбивает с толку оранжевых самцов. Поэтому оранжевые самцы, всегда готовые вступить в бой, не замечают, как желтые ящерицы проскальзывают у них под носом и спариваются с самками. Иногда желтых ящериц называют «пронырами» из-за используемого ими нечестного приема для обмана оранжевых ящериц. Итак, оранжевая побеждает синюю, синяя побеждает желтую, а желтая побеждает оранжевую – мы видим эволюционную версию игры «Камень, ножницы, бумага».

Рис. 3.01

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

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

Игра «Камень, ножницы, бумага» недавно переросла рамки детских площадок и вышла на уровень международных соревнований. Каждый год чемпиона мира по «Камню, ножницам, бумаге» наряду с вожделенным титулом ожидает приз в $ 10 000. В списке славы доминировали участники из США, но в 2006 г. житель Северного Лондона Боб Купер по прозвищу Камень сумел сдержать свои нервы и завоевать звание. Как он готовился к турниру? «Несколько часов тяжелых тренировок перед зеркалом каждый день». Полагаю, что это помогает укрепить психологическую подготовку к противостоянию с оппонентом, намеревающимся читать ваши мысли. А каков секрет его успеха? Его прозвище подталкивает соперников к мысли, что он будет чаще обычного выкидывать «камень». Поэтому у Боба появляется возможность изрезать «ножницами» «бумагу», которую соперники готовят, чтобы обернуть его «камень». Но после того, как оппоненты догадываются о его уловке, Боб Купер использует математический подход.

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

Стратегия, опирающаяся на рандомизацию, дает вам лишь равный шанс выиграть, потому что при этом игра «Камень, ножницы, бумага» ничем не отличается от подбрасывания монеты для определения победителя. Но, если мне приходится соперничать с чемпионом мира, я соглашусь на любую стратегию, дающую мне тот же шанс выиграть. Мне не приходит в голову много видов спорта, где можно придумать стратегию, дающую вам шанс пятьдесят на пятьдесят победить чемпиона мира. Может быть, спринт на 100 м? Я так не думаю.

Но как можно выбрать ряд исходов и быть совершенно уверенным, что он случаен и не характеризуется какой-то скрытой закономерностью? Это серьезная проблема: мы, люди, печально известны своей неспособностью выдать случайную последовательность – мы настолько склонны к закономерностям, что в любую нашу «случайную» последовательность просачивается структура. Вы можете загрузить PDF-файл с веб-сайта «Тайн 4исел», содержащий игральную кость «Камень, ножницы, бумага». Соберите игральную кость, которая поможет вам делать случайный выбор и победить в игре.

Ножницы и Сезанн

Игра «Камень, ножницы, бумага» использовалась для улаживания разногласий как в детских песочницах, так и на заседаниях директоров компаний. Был знаменитый случай, когда аукционные дома Sotheby’s и Christie’s решили выбрать, кому из них продавать коллекцию импрессионистских полотен Ван Гога и Сезанна, посредством единственного раунда «Камня, ножниц, бумаги». Каждый из аукционных домов должен был за выходные определиться со своим выбором. Sotheby’s нанял за немалые деньги команду аналитиков первого ранга, чтобы те предложили выигрышную стратегию. Аналитики пришли к выводу, что это игра случая и один выбор ничем не хуже другого. Поэтому они предложили «бумагу». А в Christie’s просто спросили одиннадцатилетнюю дочь одного из служащих, что бы сделала она. «Все полагают, что вы покажете “камень”, поэтому выбирают “бумагу”. Значит, нужно показать “ножницы”», – сказала она. Christie’s выиграл контракт на продажу. Сказанное лишь должно продемонстрировать вам, что математика не всегда дает преимущество.

 

Насколько вы сильны в случайности?

Интуиция зачастую подводит нас в отношении последствий случайности. Давайте я предложу вам пари. Я подкину монету 10 раз. Вы дадите мне £ 1, если случится так, что выпадут подряд три орла или три решки. Если такого не будет, я дам вам £ 2. Согласны ли вы на такое пари?

А если я повышу свою ставку до £ 4? Мне думается, что даже если вы не были уверены сначала, то примете пари теперь. В конце концов, насколько вероятно, что выпадет подряд три орла или три решки при десяти бросках монеты? Как это ни поразительно, такое происходит более чем в 82 % случаев. Поэтому, даже если я выплачиваю по £ 4 за три идущих подряд одинаковых исхода, я не останусь внакладе при достаточно долгой игре.

Точная вероятность того, что при десяти подбрасываниях монеты выпадет подряд три орла или три решки, равна 846/1024. Вот славные подробности того, как можно получить эту вероятность. Достаточно любопытно, что числа Фибоначчи, с которыми мы познакомились в главе 1, являются ключом к подсчету шансов – это еще одно свидетельство того, что они встречаются повсюду. Если я подброшу монету N раз, то имеется 2N различных исходов. Мы обозначим gN количество комбинаций, когда не встречается трех идущих подряд орлов или решек. С этими комбинациями вы выиграете пари. Мы можем сосчитать gN , воспользовавшись правилом для чисел Фибоначчи:

g N  =   g N – 1  +   g N – 2 .

Для приведения чисел в движение нужно только знать, что g1  = 2 и g2  = 4, потому что при одном или двух бросках монеты не может выпасть последовательность из трех орлов или трех решек, ведь мы еще не подкидывали монету три раза. Итак, gN принимает следующий вид:

2, 4, 6, 10, 16, 26, 42, 68, 110, 178…

Следовательно, имеется 1024 – 178 = 846 различных комбинаций после десяти подбрасываний монеты, в которых содержится последовательность из трех идущих подряд орлов или решек. Итак, вероятность выпадения такой последовательности равна 846/1024, и я выигрываю приблизительно в 82 % случаев.

Почему правило Фибоначчи оказывается ключом к вычислению gN ? Возьмите все возможные комбинации после N –  1 подбрасывания монеты, в которых нет идущих подряд трех орлов или трех решек. Мы обозначили их число gN –  1 . Теперь возьмем такую комбинацию после N бросков, что у броска N был противоположный исход броску N –  1. А сейчас возьмем все комбинации после N –  2 бросков, не содержащие трех идущих подряд орлов или решек. Их число равно gN –  2 . Пусть у бросков N –  1 и N был противоположный исход по сравнению с броском N –  2. Таким образом вы генерируете все возможные комбинации после N бросков, не содержащие трех идущих подряд орлов или решек.

 

Как выиграть в лотерею?

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

Розыгрыши итальянской государственной лотереи проводятся два раза в неделю, они проходят в десяти городах страны. Участники выбирают числа от 1 до 90. В какой-то момент шар с номером 53 отказывался выпадать в Венеции на протяжении почти двух лет розыгрышей. Разумеется, после столь долгого отсутствия он наверняка выпадет на следующей неделе – так думали многие итальянцы. Одна женщина поставила все сбережения своей семьи на то, что выпадет шар с номером 53. Когда он снова не появился, женщина утопилась в море. Были и другие трагические случаи, например когда мужчина застрелил свою семью, а потом убил себя. У него образовался огромный долг после того, как он поставил на шар 53. Как оценивается, итальянцы вложили £ 2,4 миллиарда – в среднем £ 150 на семью – в ставки, что выпадет 53.

Были даже призывы к правительству запретить номер 53 в лотерее, чтобы положить конец общенациональной одержимости этим числом. Когда плотина наконец-то была прорвана, и 9 февраля 2005 г. шар 53 показался в розыгрыше, было выплачено £ 400 миллионов неназванному числу игроков. С неизбежностью нашлись те, кто обвинил правительство в подтасовке лотереи, чтобы не проводить огромные выплаты. Подобный слух циркулировал не впервые. В 1941 г. шар с номером 8 не появился после 201 розыгрыша в Риме. Многие полагали, что Муссолини подтасовал его невыпадение, чтобы направить ставки нации на шар номер 8 на финансирование итальянских военных расходов.

А теперь давайте проверим, насколько вы удачливы, и сыграем в нашу маленькую лотерею. Я не могу обещать вам миллионы фунтов, но зато участие в ней не будет вам стоить ничего. Чтобы сыграть в лотерею, сначала выберите 6 из 49 чисел билета (рис. 3.02).

Рис. 3.02. Лотерея «Тайн 4исел»

Выбрали числа? Чтобы посмотреть, оказались ли они выигрышными, зайдите на веб-сайт http://bit.ly/quickpick .

Чтобы проверить, выиграли ли вы, зайдите на веб-сайт, приведенный выше в тексте в рамке. Выберите 1 ticket, United Kindom and National Lottery (1 билет, Соединенное Королевство и Национальная лотерея), а затем щелкните «Pick Tickets» – «Вытянуть билеты». Если у вас нет доступа к интернету, то посмотрите на заранее выбранные шесть чисел в конце этой главы. Только не надо жульничать. Как и при решении математических головоломок, вы получите значительно большее удовольствие, если получите ответ сами, а не подглядите его.

Каков ваш шанс выбрать правильно все шесть чисел и выиграть в лотерею? Чтобы сосчитать вероятность, нужно найти число всех различных способов выбрать 6 чисел, назовем это число N. Тогда у вас будет 1 шанс из N выиграть в лотерею. Для разогрева давайте найдем число различных способов выбрать 2 числа. У вас есть 49 вариантов для вашего первого числа. Второе число вы можете выбрать 48 способами. Каждый выбор первого числа может сочетаться с одним из 48 оставшихся чисел. Итак, у вас имеется 49 × 48 различных пар чисел. Но постойте, ведь каждый выбор был сосчитан дважды. Например, если вы выбрали 27 в качестве вашего первого числа, а затем 23 в качестве второго, то получится то же самое, если вы выбрали 23 первым, а 27 вторым. Итак, возможных пар в 2 раза меньше, чем вы подумали сначала, что означает, что число пар, которые вы можете выбрать, равно ½ × 49 × 48.

Теперь перейдем к шести числам. Имеется 49 вариантов выбора первого числа, 48 второго, 47 третьего, 46 четвертого, 45 пятого и, наконец, 44 варианта выбора последнего числа. Что дает 49 × 48 × 47 × 46 × 45 × 44 комбинаций шести чисел. Однако мы опять учли каждую комбинацию более одного раза. Например, сколько раз мы сосчитали комбинацию 1, 2, 3, 4, 5, 6? Что же, мы могли выбрать в качестве первого любое из этих шести чисел (и выбрали, скажем, 5). Тогда у нас останется пять возможных способов выбрать второе число (скажем, 1), четыре варианта для следующего числа (скажем, 2), три для последующего (скажем, 6), два для предпоследнего числа (скажем, 4), а последнее число – единственное, которое осталось (в данном случае 3). Итак, имеется 6 × 5 × 4 × 3 × 2 × 1 различных способов выбрать шесть чисел 1, 2, 3, 4, 5, 6. То же самое относится к любой комбинации шести чисел. Значит, нам нужно разделить 49 × 48 × 47 × 46 × 45 × 44 на 6 × 5 × 4 × 3 × 2 × 1, чтобы получить правильное число всех возможных вариантов заполнить наш лотерейный билет. И каков ответ? 13 983 816.

Это число определяет также ваш шанс выиграть, потому что оно дает число всех возможных комбинаций шаров при розыгрыше. Другими словами, ваш шанс выбрать правильную комбинацию среди всех возможных будет 1 из 13 983 816.

А какова вероятность того, что вы не угадали ни одно число? Мы можем найти ее тем же способом, как и ранее. Ваше первое число должно быть одним из 43 невыпавших, второе число – одним из остающихся 42 и т. д. Это дает 43 × 42 × 41 × 40 × 39 × 38 разных комбинаций. Но каждая из комбинаций была учтена 6 × 5 × 4 × 3 × 2 × 1 раз. Итак, число всех комбинаций, в которых нет ни одного правильного числа, равно 43 × 42 × 41 × 40 × 39 × 38, поделенному на 6 × 5 × 4 × 3 × 2 × 1, или 6 096 454. Итак, у чуть менее чем половины всех возможных выборов нет ни одного выигрышного числа. Чтобы сосчитать ваш шанс не угадать ни одного числа, нужно разделить 6 096 454 на 13 983 816. Это приблизительно равно 0,436, другими словами, вероятность того, что вы не угадаете ничего, составляет 43,6 %.

Итак, у вас есть шанс 56,4 % угадать хотя бы одно число. А каков шанс, что у вас будет ровно два верных числа? Чтобы найти его, нужно сначала определить количество комбинаций с двумя верными числами. У вас есть выбор из шести для одного правильного числа и выбор из пяти для второго правильного числа. Получается 6 × 5, но это число опять нужно разделить на 2 в силу двойного учета. Для четырех неверных чисел у вас имеется 43 × 42 × 41 × 40 комбинаций, что нужно разделить на 4 × 3 × 2 × 1 из-за многократного учета. Значит, количество комбинаций, в которых верны ровно два числа, составляет

В таблице 3.01 приведены ваши шансы угадать правильно от 0 до шести чисел, все вероятности рассчитаны таким же способом. Чтобы представить эти числа в перспективе, отметим, что если вы будете покупать билет национальной лотереи каждую неделю, то примерно через год вы можете ожидать, что у одного из ваших билетов будут по крайней мере три правильных числа. Примерно через двадцать лет вы могли бы увидеть билет по крайней мере с четырьмя верными числами. Король Альфред, покупай он билет каждую неделю, смог бы к настоящему времени увидеть один билет с пятью выигравшими числами. А если бы первой мыслью, появившейся в голове первого Homo sapiens, была бы идея зайти в ближайший киоск и начать покупать один лотерейный билет каждую неделю, то к настоящему времени он мог бы выиграть один большой приз.

Таблица 3.01. Шанс правильно угадать от 0 до 6 номеров национальной лотереи

Почему числа любят собираться вместе

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

Сначала выберите любые шесть чисел от 1 до 44 (заметьте, что разрешается выбирать именно до 44, а не до 49, вскоре вы поймете почему). Назовите ваш выбор чисел А (1), …, А (6), причем число А (1) – меньшее из выбранных, а А (6) – самое большое. Хотя числа А (1) и А (2) могут быть последовательными, числа А (1) и А (2) + 1 уже не будут таковыми. Так что, если вы возьмете шесть чисел A (1), A (2) + 1, A (3) + 2, A (4) + 3, A (5) + 4 и A (6) + 5, никакие два из них не будут последовательными. (Ограничение на выбор чисел до 44 теперь становится понятным, потому что если А (6) равно 44, то А (6) + 5 равняется 49.)

Используя этот трюк, вы можете сгенерировать все билеты без последовательных чисел. То есть вы просто выбираете шесть чисел от 1 до 44 и разрежаете их, увеличивая каждое из них. Значит, мы найдем число возможных комбинаций, в которых нет последовательных чисел, и оно будет таким же, как число возможных комбинаций по выбору шести чисел от 1 до 44. Последнее равно

Итак, полное количество билетов с последовательными числами будет

13 983 816 – 7 059 052 = 6 924 764.

Если вам когда-либо настолько повезет, что вы выиграете большой приз, вам не захочется, чтобы произошло то, что случилось в Великобритании 14 января 1995 г. Тогда шла лишь девятая неделя национальной лотереи, а джекпот превзошел немалую сумму в £ 16 миллионов. Когда шесть шаров выпали из лототрона, то победители наверняка прыгали у диванов и кричали от счастья. Но когда они пришли за выигрышем, то каждый из них обнаружил, что ему придется поделить джекпот с другими 132 обладателями счастливых билетов. Каждый из победителей получил пустяк в £ 122 510.

Но как получилось, что так много людей угадали правильную комбинацию? Дело заключается в том обстоятельстве, которое я отметил, когда мы рассматривали игру «Камень, ножницы, бумага»: мы, люди, печально известны своим неумением выбирать случайные числа. Нужно принять во внимание, что 14 миллионов человек играют в национальную лотерею, и многих из них притягивают схожие числа, например число удачи 7 либо дни рождений или юбилеев (что исключает числа 32–49). Также для выбора многих людей характерно то, что они стремятся распределить свои числа равномерно.

Вот выигравшие числа девятой недели лотереи:

Рис. 3.03

Такое равномерное распределение чисел не слишком-то характерно для случайных процессов: числа могут собираться вместе и отталкиваться с одинаковой вероятностью. Из 13 983 816 различных возможных комбинаций лотерейных билетов у 6 924 764 будут хотя бы два последовательных номера. Это составляет 49,5 %, что очень близко к половине всех комбинаций. Например, в предшествовавшую неделю выпали номера 21 и 22. А в последовавшую неделю были 30 и 31.

Однако не привязывайтесь слишком к последовательным числам. Вы могли бы решить, что комбинация 1, 2, 3, 4, 5, 6 будет умным выбором. В любом случае, как я надеюсь, к настоящему времени вы понимаете, что эта комбинация столь же вероятна, как и любая другая (то есть крайне маловероятна). Если вы сорвете джекпот с этой комбинацией, вы, наверное, рассчитываете получить выигрыш целиком. Но, оказывается, более 10 000 человек в Великобритании используют эту комбинацию каждую неделю – что лишь показывает, насколько разумно британское население. Единственная проблема состоит в том, что в случае выигрыша вам придется делиться джекпотом с другими 10 000 умными людьми.

 

Как обманывать в покере и показывать фокусы, используя задачу о простых числах на миллион долларов

Игроки-шулеры и фокусники тасуют карты не так, как прочие люди. Но после нескольких часов тренировки можно освоить прием, называемый совершенной тасовкой. При этом колода карт делится на две равные части, и потом карты из разных половин чередуются одна за другой. Если вы играете в покер, такая тасовка очень опасна.

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

Совершенная тасовка крайне эффективна и в руках фокусника, который может использовать ее интересное свойство. Если вы возьмете колоду из 52 карт и выполните совершенную тасовку 8 раз, то чудесным образом карты в колоде вернутся к своему первоначальному положению. Человеку со стороны кажется, что тасовка совершенно разупорядочивает колоду. В конце концов, восемь тасовок – более чем достаточно для среднестатистического игрока перед началом игры. Действительно, математики доказали, что для обычного игрока достаточно семи тасовок, чтобы колода полностью потеряла свою первоначальную структуру и стала случайной. Но совершенная тасовка – вовсе не обычная тасовка. Представьте, что колода карт в чем-то соответствует монете восьмиугольной формы и совершенная тасовка поворачивает ее на одну восьмую полного оборота. После восьми таких поворотов монета возвращается к своему первоначальному положению.

Но сколько раз потребуется сделать совершенную тасовку с колодой, в которой более 52 карт, чтобы они вернулись к своему первоначальному положению? Если вы добавите двух джокеров и начнете делать совершенные тасовки, то понадобится 52 манипуляции для полного оборота. Однако когда вы добавите еще десять карт и их станет 64, то потребуется сделать лишь шесть совершенных тасовок, чтобы карты в колоде возвратились к исходному положению. Так что же нам говорит математика о количестве совершенных тасовок, необходимых для того, чтобы карты в колоде из 2N карт (число должно быть четным) вернулись к исходному положению?

Пронумеруйте карты 0, 1, 2 и так далее вплоть до 2N – 1, и вы увидите, что совершенная тасовка, по существу, удваивает номер карты. Карта 1 (которая на самом деле является второй картой в колоде) становится картой 2. После еще одной совершенной тасовки она становится картой 4, затем картой 8. Математика будет проще, если мы припишем первой карте номер 0.

Но куда пойдут карты, находящиеся дальше в колоде? Чтобы разобраться в этом, представим часы с часовыми делениями от 1 до 2N – 1. Так, колода с 52 картами соответствует циферблату с делениями от 1 до 51. Если вы хотите знать, куда переместилась карта 32, то удвойте 32. Это означает, что вы стартуете с 32-го часа и отсчитываете 32 часа вперед, что приводит вас к 13 часам. Чтобы понять, сколько раз нужно сделать совершенную тасовку для возвращения всех карт к исходному положению, я должен понять, сколько раз я должен удвоить числа на циферблате для их возвращения к первоначальной позиции. В действительности я должен проследить за числом 1 и понять, сколько раз я должен удвоить его, чтобы вернуться к 1. Вот что происходит на циферблате с 51 часом при последовательном удвоении 1:

1 → 2 → 4 → 8 → 16 → 32 → 13 → 26 → 1

То, что срабатывает для 1, также будет срабатывать для всех остальных чисел. По существу, выполнение 8 совершенных тасовок соответствует умножению номеров карт на 28 = 256. Можно понять, что данная операция означает умножение номера на 1, то есть карта остается на своем месте.

Но как долго вам придется выполнять совершенные тасовки с колодой из 2N карт, чтобы те приняли первоначальное положение? Пьер де Ферма доказал, что если 2N – 1 является простым числом и вы будете продолжать удваивать числа на циферблате с 2N – 1 часом, то после 2N – 2 удвоений числа обязательно вернутся на прежнее место. Итак, для колоды из 54 карт, поскольку 54 – 1 = 53 является простым числом, 52 совершенных тасовок будет наверняка достаточно.

Однако в случае, когда 2N – 1 не является простым, нам понадобится несколько более сложная формула для расчета количества необходимых совершенных тасовок. Если 2N – 1 = p × q, где p и q – простые числа, то (p –  1) × (q – 1) совершенных тасовок будет заведомо достаточно, чтобы колода приняла свой прежний вид. Так, для колоды из 52 карт, поскольку 52–1 = 3 × 17, наверняка хватит (3–1) × (17–1) = 2 × 16 = 32 совершенных тасовок. Но в действительности вам достаточно совершить лишь 8 таких манипуляций. (В следующей главе я докажу этот фокус Ферма и объясню, что та же самая математика лежит в основе шифров, которые должны защищать секреты в интернете.)

Подсказка для покера

В популярной версии покера, называемой «техасский холдем», каждому игроку раздаются по две карты картинками вниз. Затем дилер поочередно выкладывает пять карт на стол картинками вверх. Вы должны собрать как можно лучшую комбинацию из пяти карт, выбирая из двух имеющихся у вас и пяти на столе, которая превзошла бы комбинации соперников. Если вам достались две последовательные карты (скажем, 7 треф и 8 пик), вы можете войти в азарт из-за возможности стрита (пяти последовательных карт любых мастей, например 6, 7, 8, 9, 10).

Стрит – весьма сильная комбинация. Поскольку ее вероятность довольно низка, вы можете счесть, что наличие у вас двух последовательных карт – достаточное основание для повышения ставок, потому что вы находитесь на пути к стриту. И вот сейчас вам надлежит вспомнить лотерейную подсказку. Два последовательных числа довольно часто выпадают в лотерее, то же относится и к покеру. Знаете ли вы, что в 15 % раздач техасского холдема имеются две последовательные карты? Однако чуть меньше трети из них дойдут до стрита, когда дилер выложит пять карт на столе.

Математический вопрос, который восходит к работе Гаусса двухсотлетней давности, состоит в следующем: существует ли бесконечно много чисел N, обладающих тем свойством, что колода из 2N карт на самом деле требует полного числа совершенных тасовок? Этот вопрос, как оказывается, связан с гипотезой Римана, задачей на миллион долларов о простых числах, завершающей главу 1. Если простые числа распределены так, как предсказывает гипотеза Римана, то будет бесконечное число колод карт, требующих максимального числа совершенных тасовок. Разумеется, нельзя сказать, что The Magic Circle и картежники по всему миру затаили дыхание в ожидании ответа. Но математикам любопытно знать, как простые числа могут быть связаны с вопросами тасовки карт. Не окажется удивительным, будь они связаны, – простые числа настолько фундаментальны в математике, что появляются в самых странных местах.

 

Математика в казино: удвоить или обанкротиться?

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

Прежде чем анализировать эту задачу, вы должны уяснить, что каждый раз, когда делаете ставку, вы, по существу, платите казино небольшой взнос за игру. Это станет понятно, когда вы усредните данные по всем своим выигрышам и проигрышам. Если вы ставите на 17 черное и выпадает это число, то казино возвращает вам вашу фишку и дает в придачу 35. Если бы на колесе рулетки было 36 чисел, то игра была бы справедливой, поскольку 17 черное в среднем выпадало бы один раз из 36. Так что, будь у вас 36 фишек и продолжай вы ставить на 17, то за 36 вращений колеса вы в среднем проигрываете 35 раз и один раз выигрываете, в результате вы остаетесь с теми же 36 фишками, с которыми начали игру. Но на самом деле на европейской рулетке 37 чисел, на которые можно делать ставки (от 1 до 36 и 0, который ни черный, ни красный), но казино платит вам выигрыш, как будто на колесе 36 чисел.

Поскольку на колесе 37 чисел, каждый раз, когда вы ставите £ 1, казино зарабатывает 1/37 × £ 1, что приблизительно составляет 2,7 пенса. Время от времени казино приходится делать большие выплаты какому-то игроку, но в конечном счете оно будет зарабатывать деньги благодаря законам вероятности. А в США шансы игроков еще более неблагоприятны, поскольку там на колесе рулетки 38 чисел: от 1 до 36, а также 0 и 00. Мы уже видели, что ставка на одно число обходится вам в конечном счете в 2,7 пенса. Но вы не обязаны ставить на одно число: вы можете, например, делать ставки, что число будет красное или черное, четное или нечетное, или в диапазоне от 1 до 12. Ваши шансы можно рассчитать таким же способом: по существу, какую бы ставку вы ни делали, она обойдется вам в 2,7 пенса за вложенный £ 1.

Итак, что же вам делать, чтобы повысить ваш шанс удвоения денег? Начнем с того, что, поскольку вы платите за каждую игру, оптимальная стратегия состоит в том, чтобы играть как можно меньше раз. Есть вероятность 18/37, чуть меньше 50 %, что вы уйдете, удвоив свои деньги. Так что, пусть это и будет короткий визит в казино, наилучшая стратегия состоит в том, что поставить все свои деньги на красное одним махом. Вероятность удвоения денег, если вы будете ставить одну фишку за фишкой, составляет

и у вас получается шанс 25,3 %. Значит, вы уменьшаете ваши шансы в 2 раза, если будете ставить каждый раз одну фишку.

Но в каком казино и каким образом лучше всего играть в рулетку? Некоторые заведения при выпадении 0 применяют правило en prison и возвращают вам половину вашей ставки, если вы поставили на красное. По сути это означает, что ваши шансы более благоприятны – в рулетку в таком казино играть дешевле.

При достаточно долгой игре она обойдется вам в

что нужно сопоставить с 2,7 пенса, которые требуется заплатить за какую-либо другую ставку на столе. Итак, если казино использует правило en prison, то при достаточно долгой игре стоимость ставки на красное/черное составляет половину стоимости других ставок.

Вместо того чтобы вернуть назад половину вашей ставки при выпадении 0, казино может предложить вам другой вариант: вы заключаете вашу ставку en prison. Тогда крупье кладет на ставку фишку еn prison – и при выпадении красного при следующем розыгрыше вы получаете прощение и казино возвращает вам вашу ставку (но без какого-либо выигрыша). В ином случае вы теряете свою ставку. Поскольку вероятность того, что вы получите назад свои деньги, составляет 18/37 (чуть меньше 50 %), то вам будет лучше взять половину своих денег, если представится такая возможность, чем заключать вашу ставку в тюрьму и надеяться на выпадение красного.

Итак, очевидно, что обстоятельства складываются не в вашу пользу. Но существует ли какой-нибудь математический прием, чтобы обыграть казино? Вот идея стратегии, называемой мартингейлом. Начните с того, что поставьте одну фишку на красное. Если выпадет красное, вы вернете вашу фишку и в придачу к ней получите еще одну фишку. Если красное не выпадет, то поставьте в следующем раунде две фишки на красное. Если при розыгрыше выпадет красное, то вы вернете свои две фишки и плюс к ним еще две. Вы потеряли одну фишку при первой ставке, так что теперь ваш выигрыш составляет одну фишку. Если же и во второй раз не выпадет красное, то в следующий раз поставьте четыре фишки. Если выпадет красное, то вы получите четыре фишки сверх вашей ставки. Но вы уже проиграли одну фишку в первом раунде, две фишки во втором, поэтому ваш выигрыш составляет… одну фишку.

Данная система игровых ставок состоит в том, что вы каждый раз удваиваете их, пока не выпадет красное. Ваш итоговый выигрыш всегда будет составлять одну фишку, потому что, если красное выпадет в раунде N, то ваш выигрыш в данном раунде будет составлять 2N  – 1 фишек (поставленное вами количество), но в предыдущих N – 1 раунде вы потеряли L = 1 + 2 + 4 + 8 + … + 2N  – 2 фишек. Вот эффективный способ сосчитать, насколько велик ваш проигрыш L. Разумеется, L равен 2L – L. Но как можно переписать 2L?

2 L  = 2 × (1 + 2 + 4 + 8 + … + 2 N  – 2 ) = 2 + 4 + 8 + 16 … + 2 N  – 2  + 2 N  – 1

Теперь вычтем L  = 1 + 2 + 4 + 8 + … + 2 N  – 2 . Мы придем к

L  = 2 L  –  L  = (2 + 4 + 8 + 16 … + 2 N  – 2  + 2 N  – 1 ) – (1 + 2 + 4 + 8 + … + 2 N  – 2 ) = 2 N  – 1  – 1.

Все числа из первой пары скобок (кроме 2N  – 1 ) появляются во второй паре скобок, вот почему они исчезают из ответа! (Мы уже встречались с данным вычислением, когда складывали рисинки на шахматной доске в нашем поиске простых чисел в главе 1.) Итак, вы выиграли 2N  – 1 фишек, а проиграли 2N  – 1  – 1. Ваш итоговый выигрыш будет составлять одну фишку.

Конечно, это немного, но данная система ставок на первый взгляд гарантирует вам выигрыш – в конце концов, когда-то ведь должно выпасть красное, не так ли? Так почему же игроки не извлекают свою выгоду в казино, пользуясь этой стратегией? Одна проблема состоит в том, что вам необходимы бесконечно большие финансовые возможности, чтобы гарантировать выигрыш, потому что существует теоретическая возможность того, что всю ночь будет выпадать черное за черным. И, даже если у вас была целая гора фишек, повторяющееся удвоение вашей ставки может очень быстро исчерпать ваш запас (как и в случае рисинок). Кроме того, в большинстве казино устанавливается порог максимальной ставки, именно для того, чтобы не дать игрокам использовать эту стратегию. Например, если максимальная ставка составляет 1000 фишек, ваша стратегия даст сбой после десяти раундов, потому что в одиннадцатом вам нужно будет поставить 210 = 1024 фишки, что уже превосходит порог.

Но даже при наличии максимальной ставки многие игроки поддаются заблуждению, полагая, что если черное выпало восемь раз кряду, то вероятность того, что в следующий раз выпадет красное, должна возрасти. Конечно, шанс увидеть восемь черных кряду довольно невелик, он составляет 1 из 256. Но это никоим образом не увеличивает шанс того, что в следующем раунде выпадет красное: он по-прежнему будет пятьдесят на пятьдесят. Как и у подкидываемой монеты, у колеса рулетки нет памяти.

Если вы хотите сыграть в рулетку, то помните, что говорит математика вероятности: в конечном счете заведение всегда выигрывает – хотя мы увидим в главе 5, что существует возможность использовать другую математику, которая посодействует вам в получении миллионов. Если вы не любите покер или рулетку, то вам может подойти стол для крэпса. Как мы сейчас увидим, у игральных костей очень долгая история.

 

Сколько граней было у первых игральных костей?

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

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

Она называлась «Царской игрой Ура». Несколько ее игральных полей и пирамидальные кости были найдены британским археологом сэром Леонардом Вулли во время раскопок захоронений в древнем шумерском городе Уре (сейчас он находится на территории Южного Ирака). Гробницы относятся примерно к 2600 г. до н. э., игральные комплекты помещались туда, по всей вероятности, чтобы развлекать обитателей в их жизни после смерти. Замечательный образец этого комплекта представлен в экспозиции Британского музея в Лондоне. На игровом поле 20 клеток, по которым соперники, должно быть, перемещали свои фишки в соответствии с броском тетраэдрических игральных костей.

Правила этой игры оставались неизвестными вплоть до начала 1980-х гг., когда Ирвинг Финкель из Британского музея натолкнулся в его архиве на клинописную табличку, относящуюся к 177 г. до н. э. На обратной стороне таблички имелась зарисовка этой игры. Она была предшественником нард, каждый из игроков располагал определенным количеством фишек, которые он перемещал по полю. Но именно использовавшиеся игральные кости наиболее интересны с математической точки зрения.

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

Рис. 3.04. Тетраэдрические кости из «Царской игры Ура»

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

Ход «Царской игры Ура» сильно зависит от случайного исхода броска костей. В противоположность этому нарды, ее потомок, предоставляют соперникам возможность проявить искусство и стратегию, а не только полагаться на удачу при броске. Но первоначальная игра не исчезла полностью: недавно было обнаружено, что евреи в городе Коччи на юге Индии до сих пор играют в вариант «Царской игры Ура», 5000 лет спустя после состязаний в Древнем Шумере.

 

Нашли ли «Подземелья и драконы» все игральные кости?

Одной из новинок «Подземелий и драконов» (Dungeons & Dragons), настольной ролевой игры в жанре фэнтези, появившейся в 1970-х гг., был впечатляющий набор игральных костей. Но открыли ли изобретатели игры все возможные игральные кости? Когда мы изучаем, из каких форм получились бы хорошие кости, мы снова возвращаемся к вопросу из главы 2. Если все грани игральной кости представляют собой одинаковую симметричную фигуру и эти грани соединены так, что все вершины и ребра выглядят одинаково, то эта кость является одной из пяти форм: тетраэдром, кубом, октаэдром, додекаэдром или икосаэдром – Платоновым телом (с. 63). Вы можете найти все эти кости в игральном наборе «Подземелий и драконов» (и в PDF-файле, который можно загрузить с веб-сайта «Тайн 4исел»), но у нескольких из этих костей значительно более древнее происхождение.

Например, в 2003 г. на аукционе Christie’s была продана стеклянная игральная кость с двадцатью гранями, относящаяся к римским временам. Ее грани были покрыты странными символами, наводящими на мысль, что она скорее использовалась для предсказания судьбы, чем для игры. Икосаэдр лежит в основе одного из самых популярных в наши дни приспособлений для предсказания судьбы: магического шара 8 (Magic 8 Ball). Внутри шара, наполненного жидкостью, плавает икосаэдр с нанесенными на грани ответами на ваши вопросы. Вы задаете вопрос, трясете шар и, когда икосаэдр приближается к поверхности шара, читаете ответ. Диапазон ответов простирается от «бесспорно» до «даже не думай».

Если же вам нужны всего лишь честные игральные кости, то не нужно быть придирчивым из-за расположения граней. Например, в «Подземельях и драконах» есть игральная кость, представляющая собой две пирамиды с пятиугольными основаниями, соединенными друг с другом. Эта игральная кость имеет одинаковый шанс 1 из 10 приземлиться на любую из ее десяти треугольных граней. Она не является Платоновым телом, потому что вершина у макушки каждой из пирамид отличается от остальных вершин: в ней сходятся пять треугольников, в то время как в вершинах на соединенных основаниях сходится по четыре треугольника. Тем не менее данная игральная кость справедлива: она с равной вероятностью приземляется на каждую из своих десяти граней.

Математики исследовали, из каких других форм получатся честные игральные кости. Относительно недавно было доказано, что если у игральной кости по-прежнему остается какая-то симметрия, то в дополнение к Платоновым телам имеется 20 других форм плюс пять бесконечных семейств игральных костей.

Рис. 3.05. Симметричные формы, из которых получаются хорошие игральные кости

13 из этих дополнительных 20 форм связаны с теми, из которых выходят замечательные футбольные мячи, – Архимедовыми телами из главы 2. Напомним, что грани Архимедовых тел симметричны, но могут быть разной формы. Из них получаются хорошие мячи, но они не совсем подходят для игральных костей. У классического футбольного мяча 32 грани: 12 пятиугольников и 20 шестиугольников. Не получится ли честная игральная кость, если просто написать на этих гранях числа от 1 до 32? Проблема состоит в том, что каждый пятиугольник имеет вероятность быть избранным приблизительно 1,98 %, в то время как каждый шестиугольник – приблизительно 3,81 %. Лишь в последнее десятилетие математики вывели точную формулу для вероятности того, что у игральной кости при ее приземлении наверху окажется какой-либо из пятиугольников. Впечатляющий геометрический расчет привел к следующему устрашающему ответу:

где r = ½ [2+sin²(π/5)] –1/2.

Архимедовы тела сами по себе не будут честными игральными костями, но их можно использовать для построения различных форм, которые предоставят на выбор азартных людей новые игральные кости. Ключевым является понимание того, что, хотя в Архимедовом теле грани могут быть разными, вершины в нем одинаковы. Далее используется прием под названием дуальность, переводящий вершины в грани и наоборот. Чтобы представить, какой будет грань у дуального (двойственного) многогранника, вообразите листы картона, помещенные в каждой вершине, затем нужно проследить за пересечением различных листов. Каждый лист картона должен быть ориентирован так, что он перпендикулярен линии, проходящей из центра формы в данную вершину. Например, дуальным многогранником к додекаэдру будет икосаэдр (рис. 3.06).

Рис. 3.06

Процедура применения этого приема к Архимедовым телам приводит к 13 новым игральным костям. У классического футбольного мяча 60 вершин, и у игральной кости, получающейся при замене каждой вершины гранью, будет 60 граней, каждая из которых имеет форму не равностороннего, а равнобедренного треугольника (то есть только две стороны равны). Хотя этот многогранник, дуальный к классическому футбольному мячу, и не является Платоновым телом, каждая его грань имеет равный шанс 1 из 60 выпасть после подбрасывания, поэтому он будет честной игральной костью. Его техническое название пентакисдодекаэдр (рис. 3.07).

Рис. 3.07

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

Бесконечные семейства игральных костей получаются благодаря обобщению идеи слепления вместе двух пирамид, основания которых могут иметь какое угодно число ребер. Хотя математики сумели разобраться во всем диапазоне честных игральных костей, у которых имеется симметрия, несимметричные формы, из которых получаются честные кости, по-прежнему окутаны тайной. Например, если я возьму октаэдр и обрежу немного одну вершину, а также противоположную ей вершину, то появятся две новые грани. Если я подкину эту форму, маловероятно, что она приземлится на одну из этих новых граней. Однако, если я отрежу бо́льшие куски от двух вершин, одна из двух новых граней скорее окажется внизу, чем восемь остающихся граней. Значит, должно быть некое промежуточное положение, когда при обрезании двух углов каждая из двух новых граней и первоначальных восьми будет выпадать с равной вероятностью, что создаст честную игральную кость с десятью гранями.

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

 

Как математика помогает выиграть в «Монополию»

«Монополия» кажется довольно случайной игрой. Вы подкидываете два кубика и мчитесь по игровому полю на машине либо расхаживаете в цилиндре. Где-то вы покупаете собственность, а где-то строите отели. То и дело вы можете занять второе место в конкурсе красоты благодаря карте из благотворительного фонда города, либо вам приходится раскошелиться на £ 20 за «вождение в пьяном виде». Всякий раз, когда вы проходите поле GO, вы пополняете свои карманы на £ 200. И каким же образом математика может дать вам преимущество в такой игре?

На каком поле участники чаще всего оказываются в ходе игры? Будет ли им поле GO, где вы стартуете, либо находящаяся от него по диагонали «Бесплатная автостоянка», а может быть, Оксфорд-стрит или район Мейфэр в лондонском издании «Монополии»? Но на самом деле ответом будет поле «Тюрьма». Почему? Что же, вы можете подкинуть кубики и оказаться на поле «Просто посетить» (Just Visiting) либо очутиться на расположенном от него по диагонали поле, где полицейский скажет вам «Отправиться в тюрьму». Вам также может не повезти, и доставшаяся случайная карта предпишет отправиться прямиком в тюрьму. И это отнюдь не все возможности оказаться в заключении. Если вы выбросите дубль, то опять-таки нужно отправляться туда. Если вы выбросите три дубля подряд, то вас вовсе не наградят за это впечатляющее достижение в кидании игральных костей, а накажут тюремным сроком на три хода.

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

На каждом кубике может с равной вероятностью выпасть любая из шести граней. Когда у нас имеется две игральных кости, то получается 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 Família), до сих пор не достроенную церковь в Барселоне, проект которой был разработан Антонио Гауди. Магическим числом этого квадрата размером 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 исходит только одна линия, которая соединяет ее с А, так что вершины А и С совпадают? Но мы можем видеть, что в основе доказательства существования Эйлерова пути лежит красивая идея продвижения шаг за шагом. Подобно тому как я методично поднимаюсь вверх по лестнице, я могу воспользоваться данным приемом для сколь угодно большой карты.

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

Я недавно совершил паломничество в Кёнигсберг, который был переименован в Калининград после Второй мировой войны. Город неузнаваемо изменился со времен Эйлера – он был разрушен бомбардировками союзников. Однако три довоенных моста по-прежнему на месте: Деревянный мост (Holzbrücke), Медовый мост (Honigbrücke) и Высокий мост (Hohebrücke). Два моста исчезли полностью: Потроховой мост (Köttelbrücke) и Кузнечный мост (Schmiedebrücke). Оставшиеся мосты – Зеленый мост (Grünebrücke) и Лавочный мост (Krämerbrücke) – также были разрушены во время войны, но были перестроены и стали частью гигантской автострады с четырьмя полосами движения, проходящей через город.

Новый железнодорожный мост, по которому также могут ходить пешеходы, соединяет два берега Прегеля к западу от города. Также новый пешеходный Юбилейный мост, построенный на опорах разрушенного Императорского моста, позволил мне перейти реку подобно старому Высокому мосту. Я всегда думаю как математик и первым делом задался вопросом, можно ли совершить путешествие по сегодняшним мостам в духе игры 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