Текст книги "Математические головоломки и развлечения"

Автор книги: Мартин Гарднер

сообщить о нарушении

Текущая страница: 11 (всего у книги 30 страниц)

Глава 19. ЦИФРОВЫЕ КОРНИ

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

Рис. 108 Волшебные знаки для фокуса с телефонным номером.

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

Нетрудно понять, на чем основан этот нехитрый фокус. Он может служить отличным введением в понятие сравнения двух чисел, сформулированное Гауссом. Если два числа при делении на любое заданное число k дают одинаковые остатки, то про такие числа говорят, что они сравнимы по модулю к, а само число k называют модулем сравнения. Например, 16 и 23 при делении на 7 дают остаток 2, следовательно, эти числа сравнимы по модулю 7.

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

Например, 4157 при делении на 9 дает остаток 8. Сумма цифр числа 4157 равна 17 и тоже дает при делении на 9 остаток 8. Сумма цифр числа 17 равна 8. Последнее однозначное число, равное самому остатку, назовем цифровым корнем исходного числа. Оно совпадает с остатком от деления исходного числа на 9, если только этот остаток отличен от 0. Для чисел, сравнимых с 0 по модулю 9, цифровой корень равен не 0, а 9.

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

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

Посмотрим, какое отношение имеет все сказанное к фокусу с телефонным номером. Перестановка цифр номера не меняет его цифрового корня, поэтому, вычитая из большего числа меньшее, мы берем разность двух чисел с одинаковыми цифровыми корнями. Такая разность делится на 9 без остатка. Чтобы понять, почему так происходит, представим большее число как некоторое кратное девяти, к которому прибавлен цифровой корень (остаток при делении числа на 9). Меньшее число состоит из меньшего кратного 9, к которому прибавлен тот же самый цифровой корень. При вычитании из большего числа меньшего одинаковые цифровые корни взаимно уничтожаются и остается число, кратное 9:

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

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

Предположим, например, что вам нужно найти наименьшее из чисел, запись которых состоит из одних лишь нулей и единиц, делящееся без остатка на 225. Цифровой корень числа 225 равен 9, поэтому вы сразу же знаете, что искомое число должно иметь цифровой корень, равный 9. Наименьшее из чисел, записанных с помощью одних лишь единиц и имеющих цифровой корень 9, очевидно, равно 111 111 111. Дописывая нули, мы лишь увеличиваем число, но не изменяем его цифровой остаток. Наша задача заключается в том, чтобы, увеличив число 111 111 111 как можно меньше, превратить его в кратное 225. Поскольку число 225 делится на 25, искомое число также должно быть кратно 25. Все кратные 25 оканчиваются цифрами 00, 25, 50 или 75. По условию задачи в записи числа разрешается использовать только нули и единицы, поэтому числа, оканчивающиеся цифрами 25, 50 и 75, отпадают. Следовательно, к 111 111 111 справа нужно приписать 00. Это и дает ответ задачи: 11111111100.

Понятие цифрового корня позволяет проанализировать и многие математические игры, например следующую игру в кости.

Играют вдвоем. Прежде всего задумывают какое-нибудь число (чтобы игра была интересной, обычно берут число, большее 20).

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

Ключом к оптимальной стратегии служат числа, имеющие те же цифровые корни, что и задуманное число. Если вы сможете так изменить счет игры, чтобы он совпал с одним из таких чисел, или сумеете постоянно препятствовать аналогичному намерению своего противника, то вас непременно ожидает выигрыш. Поясним сказанное на примере. Предположим, что противники условились вести игру до 31 очка. Цифровой корень числа 31 равен 4. Единственный способ выиграть для первого игрока заключается в том, чтобы при бросании кости получить на верхней грани 4 очка, а при последующих ходах стараться либо довести счет до одного из чисел 4—13–22—31, либо помешать противнику сделать то же самое.

Вторая задача несколько труднее, и мы не будем останавливаться на ней подробно. Скажем лишь, что добиться проигрыша противника можно, либо бросая кость так, чтобы пятерка оказалась на нижней или верхней грани, и доводя затем счет до чисел 8—17–26, либо бросая кость так, чтобы на верхней или нижней грани выпала четверка, и стараясь довести счет до одного из чисел, встречающихся в следующих трех последовательностях: 9—18–27, 1—10–19—28 и 5-14-23.

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

Если же задуманное число кратно 9 (и, следовательно, его цифровой корень равен 9), то победы всегда может добиться второй игрок.

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

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

Многие из карточных фокусов, для показа которых не требуется особой ловкости рук, зависят от свойств цифровых корней.

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

Из тщательно перетасованной колоды вы выбираете девять карт – от туза до девятки – и располагаете их по порядку так, чтобы туз оказался сверху. Показав карты зрителям, вы заявите, что сейчас разделите отобранные девять карт так, что никто не сможет с уверенностью сказать, где находится та или иная карта. Держа девять карт вверх рубашкой, вы делаете вид, что наугад разбиваете их на две части, а на самом деле перекладываете наверх три нижние карты, после чего ваши девять карт расположатся так (мы называем карты по порядку, сверху вниз; 1 соответствует тузу): 7-8-9-1-2-3-4-5-6.

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

Попросите теперь зрителя снять верхнюю часть большой колоды. Подсчитав число карт в снятой и оставшейся частях колоды, найдите цифровые корни полученных вами чисел. Сложите оба цифровых корня и, если результат окажется больше 9, замените их сумму ее цифровым корнем. Откройте теперь выбранную зрителем карту (самую верхнюю из отложенных вами карт). Ее значение в точности совпадает с полученным вами результатом и позволяет предсказывать его заранее!

Объясняется фокус очень просто. После того как вы отобрали девять карт, расположили их по порядку и переложили три нижние карты наверх, самой верхней из девяти карт будет семерка. В колоде останутся 43 карты. Цифровой корень числа 43 равен 7. Если зритель не выберет семерку вы возвращаете ее в колоду, увеличивая тем самым число карт в ней до 44. После этого верхней картой у вас в руках становится 8, и цифровой корень числа 44 также равен 8. Иначе говоря, какую бы карту зритель ни выбрал, ее значение всегда совпадает с цифровым корнем числа карт в колоде. Разбиение колоды на две части, подсчет числа карт в каждой из них и другие описанные выше действия, разумеется, приводят к числу, совпадающему с цифровым корнем числа всех карт в колоде.

* * *

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

Это утверждение нетрудно доказать. Некоторых читателей, может быть, заинтересует неформальный набросок этого доказательства.

Рассмотрим какое-нибудь четырехзначное число, например 4135. Его можно записать в виде суммы степеней числа 10:

(4 ∙ 1000) + (1 ∙ 100) + (3 ∙ 10) + (5 ∙ 1).

Вычитая по 1 из каждой степени 10, то же число можно представить в виде:

(4 ∙ 999) + (1 ∙ 99) + (3 ∙ 9) + (5 ∙ 0) + 4 + 1 + 3 + 5.

Все выражения в скобках кратны 9. Отбросив их, мы получаем сумму цифр исходного числа: 4+1+3 + 5.

В общем случае четырехзначное число abed представимо в виде

(а ∙ 999) + (Ь ∙ 99) + (с ∙ 9) + (d ∙ 0) + а + Ь + с + d,

и поэтому после вычеркивания чисел, кратных 9, должна оставаться сумма a+b+c+d. Разумеется, эта сумма не обязательно должна выражаться однозначным числом, но, записав ее так же, как исходное число, и вычеркнув все кратные 9, мы всегда можем найти ее остаток при делении на 9 и т. д. до тех пор, пока не получим однозначное число – цифровой корень. Сказанное справедливо для любого числа, как бы велико оно ни было. Поэтому цифровой корень – это число, которое остается после того, как из исходного числа вычеркнуто максимальное число девяток, то есть после деления исходного числа на 9.

Цифровые корни часто используют для того, чтобы убедиться, что какое-нибудь очень большое число не является совершенным квадратом или кубом. Все квадраты имеют цифровые корни 1, 4, 7 или 9, а их последними цифрами могут быть 2, 3, 7 или 8. Кубы могут оканчиваться на любую цифру, но их цифровыми корнями могут быть только 1, 8 или 9. Самое любопытное, что четные совершенные числа (а до сих пор не было найдено ни одного нечетного совершенного числа) должны оканчиваться цифрой 6 или 8. Если отбросить наименьшее совершенное число 6, то у всех остальных совершенных чисел цифровой корень равен 1.

Ответы

Если при игре в кости число, до которого ведется счет, выбирает первый игрок, то ему лучше всего остановить свой выбор на каком-нибудь числе с цифровым корнем, равным 7. Как следует из приведенной здесь таблицы, именно при 7 выигрыш первого игрока обеспечен (при правильной игре) в трех случаях из шести возможных, то есть с вероятностью 1/2 при первом бросании на кости выпадает столько очков, сколько нужно первому игроку для выигрыша. При всех других цифровых остатках шансы первого игрока на победу хуже.

Глава 20. ДЕВЯТЬ ЗАДАЧ

1. Сцепленные болты. Два одинаковых болта сцеплены нарезкой (рис. 109).

Рис. 109 Сцепленные болты.

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

Будут ли головки болтов: а) сближаться, б) расходиться или в) оставаться на неизменном расстоянии друг от друга?

Использовать при решении задачи настоящие болты не разрешается.

2. Кругосветный полет. Группа самолетов базируется на небольшом острове. Баки каждого самолета вмещают столько топлива, что его хватает на облет половины земного шара. При заправке в воздухе из баков одного самолета в баки другого можно перекачивать любое количество горючего. На земле заправку можно производить только на острове. Для удобства решения задачи предполагается, что заправка на земле и в воздухе происходит мгновенно, бех потерь времени.

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

3. Окружность на шахматной доске. Сторона клетки на шахматной доске 4 см. Чему равен радиус наибольшей окружности, которую можно провести на шахматной доске так, чтобы она проходила только по черным клеткам?

4. Универсальная пробка. Во многих сборниках головоломок объясняется, как вырезать пробку, которой можно плотно заткнуть квадратное, круглое и треугольное отверстия (рис. 110).

Рис. 110 Универсальная пробка.

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

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

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

5. Повторяющееся число. Если у вас соберутся гости, вы сможете удивить их необычным фокусом. Попросите одного из гостей – назовем его А – написать на листке бумаги какое-нибудь трехзначное число два раза подряд, чтобы получилось шестизначное число (например 394 394). Отвернитесь так, чтобы вы не могли видеть написанное число, и попросите А передать листок другому гостю, В, которого попросите разделить число на 7.

«Об остатке не беспокойтесь, его не будет», – говорите вы гостю В, и он с удивлением убеждается, что вы правы (например, 394 394 при делении на 7 дает 56 342). Не сообщая вам результат, В передает листок бумаги третьему гостю, С, который делит полученный В результат на 11. Вы снова утверждаете, что остатка не будет, и снова оказываетесь правы (56 342 при делении на 11 дает 5122).

Не оборачиваясь к гостям и не зная, какие цифры написаны на листке бумаги, вы просите передать его четвертому гостю, D, который должен поделить последний результат на 13. Снова деление происходит без остатка (5122 при делении на 13 дает 394). Окончательный результат D записывает на клочке бумаги и, сложив его, передает вам. Не разворачивая листка с ответом, вы передаете его А и говорите: «Разверните листок и вы увидите свое трехзначное число».

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

6. Столкновение ракет. Две ракеты летят навстречу друг другу, одна – со скоростью 9000 миль/час, а другая – со скоростью 21 000 миль/час. Их стартовые площадки находятся на расстоянии 1317 миль одна от другой. Не пользуясь карандашом и бумагой, подсчитайте, какое расстояние будет между ракетами за минуту до столкновения.

7. Как передвинуть монеты. На ровной гладкой поверхности (например на столе) выложен треугольник из шести монет (рис. 111).

Рис. 111 Как передвинуть монеты?

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

8. Рукопожатия и графы. Докажите, что число участников последнего конгресса биофизиков, обменявшихся рукопожатиями нечетное число раз, четно. Та же задача допускает и графическую интерпретацию. На листке бумаги поставьте любое число точек (каждая точка изображает участника конгресса). Между любыми двумя точками разрешается проводить сколько угодно линий. Каждая точка может неограниченное число раз «обмениваться рукопожатиями» с другими точками или быть необщительной и не здороваться ни с кем. Докажите, что число точек, из которых исходит нечетное число линий, четно.

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

Все три участника знают, что Смит никогда не промахивается, Браун попадает в цель в 80 % случаев, а Джонс, стреляющий хуже всех, промахивается так же часто, как и попадает в цель.

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

Более трудный вопрос: чему равна вероятность остаться в живых для каждого из дуэлянтов?

Ответы

1. Головки болтов не сближаются и не расходятся. Движение болтов можно сравнить с движением человека, идущего вверх по спускающемуся эскалатору со скоростью эскалатора.

2. Чтобы обеспечить кругосветный полет одного самолета, достаточно двух самолетов. Сделать это можно многими способами.

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

Самолеты А, В и С стартуют одновременно. Пролетев 1/8 намеченного расстояния (то есть длины окружности большого круга), С перекачивает 1/4 исходного запаса горючего в баки А и 1/4 – в баки В, после чего у него остается 1/4 заправки. Этого количества горючего ему хватает, чтобы вернуться на базу.

Самолеты А а В, продолжая полет, проходят еще 1/8 кругосветного маршрута, после чего В перекачивает 1/4 заправки в баки А.

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

Полностью заправленный самолет А продолжает лететь до тех пор, пока у него не кончится горючее. К этому моменту он находится на расстоянии 1/4 всего пути от базы, и его встречает самолет С, успевший перезаправиться на острове. С перекачивает в баки А 1/4 заправки и вслед за А берет курс на базу. На расстоянии 1/8 окружности земного шара горючее у А и С кончается, но тут их встречает побывавший на базе В, который отдает каждому из них по 1/4 полной заправки. После этого топлива в баках каждого самолета хватает как раз на то, чтобы благополучно вернуться на свою базу (правда, садиться приходится с пустыми баками).

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

Рис. 112 К задаче о кругосветном полете самолета.

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

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

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

Пробка той формы, которая описана в условии задачи, имеет наименьший объем по сравнению с любым выпуклым телом, способным заткнуть те же три дырки. Пробку наибольшего объема нетрудно получить, если обрезать цилиндрическую пробку так, как показано на рис. 113.

Рис. 113 Как сделать универсальную пробку наибольшего объема.

Именно эту форму пробки обычно имеют в виду составители сборников головоломок, предлагая читателям найти универсальную затычку, подходящую к круглому, треугольному и квадратному отверстиям. Ее объем равен 2π – 4/3.

5. Написать подряд два раза трехзначное число – все равно что умножить это число на 1001. Число 1001 разлагается на простые множители 7, 11 и 13, поэтому, приписав к трехзначному числу его же еще раз справа, задумавший просто умножает свое число на 7 х 11 х 13. Разделив шестизначное число на 7, 11 и на 13, он, естественно, получает снова исходное трехзначное число. Эта задача заимствована из книги Я. И. Перельмана.[40]40
  Перельман Я. И. Живая математика: 9-е изд. – М.: Наука, 1970.


[Закрыть]

6. Две ракеты сближаются со скоростью 30 000 миль/час, или 500 миль/мин. Отсчитывая время назад, от момента столкновения, мы получаем, что за минуту до столкновения ракеты должны были бы находиться на расстоянии 500 миль друг от друга.

7. Рассмотрим исходное расположение монет в виде треугольника. Обозначим цифрой 1 верхнюю монету, цифрами 2 и 3 – монеты в следующем ряду и цифрами 4, 5, 6 – монеты в нижнем ряду. Следующие четыре хода позволяют получить представление о множестве других решении: передвинем монету 1 так, чтобы она коснулась монет 2 и 4; монету 4 передвинем так, чтобы она коснулась монет 5 и 6; монету 5 передвинем так, чтобы она коснулась монет 1 и 2 снизу; и, наконец, монету 1 передвинем так, чтобы она коснулась монет 4 и 5.

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

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

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

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

Легче всего подсчитать вероятность остаться в живых для Смита. В дуэли с Брауном с вероятностью 1/2 он стреляет первым. В этом случае он убивает Брауна. Браун, который попадает в цель в 4-х случаях из 5, стреляет первым также с вероятностью 1/2. В этом случае Смит остается в живых с вероятностью 1/5. Таким образом, Смит с вероятностью 1/2 + 1/2х1/5 = 3/5 переживает Брауна. Если Смит остается в живых, то в него стреляет Джонс, который в 1/2 всех случаев промахивается. Но если Джонс промахивается при своем первом выстреле, то Смит, дождавшись своей очереди стрелять, убивает его. Поэтому с вероятностью 1/2 Смит выходит из дуэли с Джонсом живым и невредимым. Итак, вероятность остаться в живых после дуэли с обоими своими противниками для Смита равна 3/5х1/2 = 3/10.

Случай с Брауном более сложен, потому что требует рассмотрения бесконечного множества случаев. Вероятность остаться в живых после дуэли со Смитом для Брауна равна 2/5 (мы только что показали, что Смит в дуэли с Брауном имеет вероятность уцелеть, равную 3/5; так как в живых должен остаться лишь один из дуэлянтов, искомую вероятность для Смита мы находим, вычитая 3/5 из 1).

Затем в Брауна стреляет Джонс, который попадает в цель лишь в половине случаев. Если Джонс промахивается, то Браун с вероятностью 4/5 убивает его. Итак, на этом этапе дуэли Браун с вероятностью 1/2х4/5 = 4/10 выходит победителем из поединка с Джонсом. Но с вероятностью 1/5 Браун может промахнуться, после чего Джонс имеет право выстрелить еще раз. С вероятностью 1/2 Браун останется в живых, и тогда он в свою очередь сможет выстрелить в Джонса и с вероятностью 4/5 убить его. Шансы Брауна остаться в живых во время второго тура поединка составляют 1/2х1/5х1/2х4/5=4/100.

Если Браун снова промахнется, то во время третьего тура он может убить Джонса лишь с вероятностью 4/1000. В случае повторного промаха во время четвертого тура он попадет в Джонса с вероятностью 4/10000 и т. д. Таким образом, шансы Брауна пережить Джонса равны сумме бесконечного ряда 4/10+4/100+4/1000+4/10000+…

Это не что иное, как бесконечная периодическая десятичная дробь 0,44444…, равная 4/5.

Ранее мы видели, что Браун с вероятностью 2/5 может пережить Смита. Только что мы показали, что с вероятностью 4/9 он останется в живых после дуэли с Джонсом. Вероятность того, что именно Браун переживет обоих своих противников, равна, следовательно,

2/5х4/9=8/45

Аналогичным способом можно было бы подсчитать и вероятность уцелеть для Джонса, но проще получить ее вычитанием из 1 соответствующих вероятностей 3/10 для Смита и 8/45 для Брауна.

Она оказывается равной 47/90.

Весь поединок удобно изобразить с помощью специального графа—дерева дуэли (рис. 114).

Рис. 114 Дерево дуэли Смита, Джонса и Брауна.

Вначале ствол дерева раздваивается.

Это происходит потому, что если первым стреляет Джонс, то он производит свой выстрел в воздух, после чего остаются две равновероятные возможности: стреляет либо Смит, либо Джонс (эти двое стреляют «вполне серьезно», с твердым намерением убить своего противника). Одна из ветвей дерева простирается до бесконечности. Подсчет вероятности для того или иного дуэлянта остаться в живых производится следующим образом:

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

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

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

3. Сложить все вычисленные в п. 2 вероятности. Их сумма будет интересующей нас вероятностью выживания того или иного дуэлянта.

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

Различные варианты этой задачи включены во многие сборники головоломок.