Текст книги "Магия математики: Как найти x и зачем это нужно"

Глава номер четыре
Магия счета

Математика с восклицательным знаком!

В самом начале этой книги мы говорили о том, как посчитать сумму всех чисел от 1 до 100. И мы справились – у нас получилось 5050. Также мы нашли замечательную формулу для подсчета суммы первых n. А почему бы теперь не поискать произведение чисел от 1 до 100? Даже по примерным прикидкам результат получится просто гигантским! Если вам интересно, скажу: это число, состоящее из 158 знаков. Вот оно:

93326215443944152681699238856266700490715968264381621468

59296389521759999322991560894146397615651828625369792082

7223758251185210916864000000000000000000000000

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

Когда мы перемножаем все числа от 1 до n, для обозначения произведения мы используем n! что читается как «факториал числа n». Другими словами,

n! = n × (n – 1) × (n – 2) ×… × 3 × 2 × 1

Например,

5! = 5 × 4 × 3 × 2 × 1 = 120

Мне кажется, символ восклицательного знака подходит здесь как нельзя лучше: значение числа n! увеличивается очень быстро и, как мы увидим чуть позже, таит в себе много удивительного. Для удобства математики определяют значение 0! = 1. А еще n! не определяется, когда n – отрицательная величина.

Отступление

Казалось бы, 0! должен быть равен 0. Но это почему-то не так: 0! = 1. Давайте разберемся, почему. Обратите внимание, что для n ≥ 2 n! = n × (n – 1)! а значит

Если мы хотим, чтобы наше утверждение оставалось верным для n = 1, нам понадобится

Итак, факториалы растут очень и очень быстро. Посмотрите сами:

Насколько велики эти числа? Ученые говорят, что количество всех-всех песчинок в мире равняется 10²². А количество всех-всех атомов во Вселенной – 10⁸⁰. Так вот, если вы тщательно перемешаете колоду из 52 карт (что, как мы чуть позже узнаем, может быть сделано 52! способами), шансы на то, что в таком порядке они сложатся впервые со времен изобретения карт и никогда больше не сложатся снова, близки к 100 %. И это при условии, что все люди на Земле каждую минуту на протяжении нескольких миллионов лет будут тасовать каждый свою колоду.

Отступление

В начале главы вы, скорее всего, заметили, каким огромным количеством нолей заканчивается факториал 100! Откуда они берутся? При перемножении чисел от 1 до 100 мы получаем ноль всякий раз, когда умножаем число, кратное 5, на число, кратное 2. Первых в промежутке от 1 до 100 будет 20, вторых (по сути, всех четных) – 50, что, по идее, дает нам в конце 20 нолей. Но ведь числа 25, 50, 75 и 100 дают нам дополнительные коэффициенты пятерки, поэтому 100! будет иметь в итоге 24 ноля.

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

Правило суммы и произведения

Большинство проблем с вычислением на самом деле сводятся к двум правилам – суммы и произведения. Правило суммы используется, когда нужно подсчитать общее количество имеющихся у вас вариантов выбора. Допустим, у вас есть 3 рубашки с короткими рукавами и 5 рубашек – с длинными. Но наденете-то вы только одну. Значит, вы стоите перед выбором одного из 8 вариантов. Обобщая, можно сказать, что, если у вас есть два типа объектов и количество объектов первого типа равно a, а объектов второго типа – b, всего у вас будет a + b разных объектов (естественно, предполагая, что ни один из объектов типа b не повторяется в типе a).

Отступление

Как уже было сказано, правило суммы исходит из того, что в двух типах объектов каждый объект уникален. Но если у нас все же есть несколько объектов (в количестве c), принадлежащих к обоим типам, не считать же их дважды, правда? Значит, формулу придется немного изменить: a + b – c. Например, если в классе у 12 учеников есть собаки, у 19 – кошки, а у 7 – и собаки и кошки, получается, что общее количество учеников, держащих только одно животное, будет 12 + 19 – 7 = 24. Если перевести это в плоскость чистой математики, в промежутке от 1 до 100 у нас получится 50 чисел, кратных 2; 33 числа, кратных 3; и 16 чисел, кратных как 2, так и 3 (ну или кратных 6). Значит, количество чисел, кратных либо 2, либо 3, нужно подсчитывать так: 50 + 33 – 16 = 67.

Правило произведения применяется в том случае, когда вам нужно предпринять некое действие, которое состоит из двух частей. Если имеется a вариантов выполнения первой части и b вариантов второй, то для всего действия имеется a × b вариантов. То есть если у меня есть 5 разных пар брюк и 8 различных рубашек и если я (как и большинство математиков) при этом не особо озабочен вопросами стиля и сочетания цветов, общее количество возможных комбинаций составит 5 × 8 = 40. А если я еще решу надеть один из 10 своих галстуков (то есть мое действие будет состоять уже из трех частей: галстук, брюки и рубашка), комбинаций станет уже 40 × 10 = 400.

В полной колоде карт каждая карта принадлежит к одной из 4 мастей (пики, червы, бубны, трефы) и 13 достоинств (туз, 2, 3, 4, 5, 6, 7, 8, 9, 10, валет, дама и король). Значит, всего в полной колоде 4 × 13 = 52 карты. При желании все их можно разложить в виде прямоугольника со сторонами 4 на 13 – тем самым мы получим визуальное представление об общем количестве в 52.

Давайте применим правило произведения для подсчета почтовых индексов. Каково возможное количество пятизначных индексов? Каждый индекс – это пятизначное число, состоящее из цифр от 0 до 9. Наименьшее из них будет иметь вид 00000, а наибольшее – 99999[7]7
  В США почтовые индексы пятизначные (в России – шестизначные). – Прим. пер.


[Закрыть]. Значит, всего имеется 100 000 вариантов. К тому же результату можно прийти с помощью правила произведения. У нас есть 10 вариантов выбора числа для первой цифры (от 0 до 9), 10 – для второй, и дальше по 10 для третьей, четвертой и пятой. Значит, имеем 10⁵ = 100 000 вариантов.

В почтовых индексах числа могут повторяться. А если взять ситуацию, в которой объекты не могут повторяться – например, когда вы выкладываете предметы в ряд? Несложно заметить, что два объекта в каждой паре могут быть расположены двумя способами. Скажем, буквы А и B могут быть представлены либо как АВ, либо как ВА. Способов разложить 3 объекта у нас ровно 6: ABC, ACB, BAC, BCA, CAB, CBA. А можете представить в уме, без ручки и бумажки, 24 возможные комбинации 4 объектов? Начнем с выбора одного из четырех вариантов для начальной позиции (выбираем из четырех букв: А, B, C или D). Для второй позиции останется 3 варианта, для третьей – 1, для последней, четвертой, – всего лишь 1. Всего получается 4 × 3 × 2 × 1 = 4! = 24 варианта. Другими словами, для n объектов имеется n! вариантов их расположения.

А вот пример одновременного использования правил суммы и произведения. Допустим, некое государство выдает автовладельцам регистрационные номера двух типов. Номера первого типа состоят из 3 букв и 3 цифр, второго – из 2 букв и 4 цифр (в обоих случаях сначала идут буквы, потом – цифры). Сколько всего будет номеров (притом что мы можем использовать все 26 букв латинского алфавита и 10 цифр, не обращая при этом внимания на внешнее сходство, вроде О и ноль)? Сначала посчитаем количество номеров первого типа, применив правило произведения:

26 × 26 × 26 × 10 × 10 × 10 = 17 576 000

То же с номерами второго типа:

26 × 26 × 10 × 10 × 10 × 10 = 6 760 000

Так как один номер относится либо к первому, либо ко второму типу (и не повторяется), согласно правилу суммы общее количество возможных комбинаций – 24 336 000.

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

26 × 26 × 36 × 10 × 10 × 10 = 24 336 000

ведь для первых двух символов каждого номера существует 26 вариантов, для последних трех – 10, при этом третий символ может быть или буквой, или цифрой, а значит, возможных вариантов здесь будет 26 + 10 = 36.

Лотерея и покер

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

Допустим, вам предлагают наполнить рожок 3 шариками разных сортов мороженого. Всего можно выбирать из 10 сортов. Сколько всего можно получить разных рожков? Не забудьте: порядок шариков разных сортов имеет значение (а как же иначе? Ведь вкус-то разный!). Если повторяться можно, получается, что у нас есть 10 вариантов для каждого из трех шариков: 103 = 1000 вероятных комбинаций. Ну а если нельзя – их количество сокращается до 10 × 9 × 8 = 720, как показано на картинке чуть ниже.

Теперь кое-что поинтереснее. Как будут лежать три шарика трех разных сортов в вазочке, если их порядок не важен? Можно сказать точно: их будет меньше. А конкретно – в 6 раз меньше. Попытаемся понять, почему. Лежащие в вазочке 3 шарика мороженого 3 разных сортов (допустим, шоколадное, ванильное и мятное) можно переложить в рожок 3! = 6 способами. Значит, из 1 варианта вазочки можно собрать 6 вариантов рожков. Количество вазочек, таким образом, будет равняться

Другой способ представить 10 × 9 × 8 – 10!/7! (хотя первый пример, конечно, легче подсчитать). Значит, количество чашек – Такая запись читается как «число сочетаний из 10 по 3», обозначается символом и равняется 120. Другими словами, число вариантов при выборе определенного количества различных объектов, равного n, из общего количества различных объектов, равного k (в произвольном порядке), называется «числом сочетаний из n по k» и подсчитывается по формуле

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

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

вариантов. Кстати, если на вашем калькуляторе не предусмотрено специальной кнопки, чтобы подсчитать просто наберите в любом поисковике «число сочетаний из 20 по 5»[8]8
  Или по-английски «20 choose 5». – Прим. пер.


[Закрыть], и вы увидите веб-калькулятор с готовым ответом.

Биноминальные коэффициенты, впрочем, могут появляться и там, где порядок расположения объектов определенную роль все же играет. Если вы 10 раз подбросите монетку, сколько всего у вас будет возможных последовательностей результатов (вроде О-Р-О-Р-Р-О-О-Р-Р-Р или О-О-О-О-О-О-О-О-О-О)? Так как каждый бросок имеет два возможных исхода, правило произведения говорит нам, что их будет 210 = 1024, причем шансы выпадения каждой стороны абсолютно равны. (Некоторые, конечно, удивятся: вероятность того, что выпадет вторая комбинация, вроде бы куда ниже, чем у первой. Тем не менее шансы и у той, и у другой абсолютно равные – 1 к 1024.) С другой стороны, то, что за 10 бросков орел выпадет 4 раза, а не 10, куда вероятнее, ведь комбинаций с 4 орлами много, а с 10 – всего одна. Вот только «много» – это сколько? Подобная последовательность определяется количеством «орлиных» бросков, равным 4 из 10, соответственно, остальные броски должны закончиться выпадением решки. Количество способов определить, какие именно 4 из 10 бросков дадут нам орла, равно (все равно что выбирать 4 разных шарика мороженого из 10 сортов). Значит, наш шанс, что из 10 попыток 4 раза выпадет орел, если бросать симметричную, абсолютно уравновешенную монетку, равен

или примерно 20 % всех возможных комбинаций.

Отступление

Логично спросить, сколько можно собрать вазочек с 3 шариками из 10 сортов, если можно повторяться (10³/6 – ответ неправильный, это ведь даже не целое число). Наиболее простой способ – рассмотреть 3 отдельных случая, взяв за отправную точку количество разных сортов в вазочке. Очевидно, что в случае с 3 шариками одного сорта получится 10 вазочек. Из сказанного выше понятно, что в случае с 3 шариками 3 сортов получится вазочек. А вазочек будут с 2 сортами мороженого, ведь 2 сорта мы можем выбрать способами. И лишь потом можно решать, какие 2 из 3 шариков будут именно этого сорта. Сложив все вместе, получим 10 + 120 + 90 = 220 вазочек.

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

Второй, снова второй и седьмой сорта – вот так:

А комбинация

будет означать, что наш выбор пал на сорта третий, пятый и десятый. То есть вазочка – это набор из 3 звездочек и 9 черточек. Всего получается 12 символов, 3 из которых обязательно должны быть звездочками. Следовательно, возможных комбинаций у нас будет Обобщая, можно сказать, что количество способов выбрать k объектов из множества n при произвольном порядке и с возможностью повторения равно количеству способов сочетания k звездочек и n – 1 черточек –

Подсчет сочетаний необходим в большинстве задач, в которых большую роль играет случайность. Представим себе лотерею, в которой вам нужно угадать 5 различных чисел от 1 до 47. Дополнительно вы выбираете еще одно, МЕГАчисло от 1 до 27 (можно выбирать любое, в том числе и одно из тех, которые уже встречались в пятерке). У нас есть 27 вариантов выбора дополнительного числа, и вариантов выбора основных 5 чисел. Таким образом, общее количество равно

Другими словами, ваш шанс выиграть главный приз в такой лотерее – примерно 1 из 40 миллионов.

Теперь давайте переключим внимание на покер. Комбинация в покере – это обычно 5 карт из 52, составляющих колоду. Все они разные, выбраны случайно, порядок их значения не имеет. Следовательно, количество комбинаций равняется

Комбинация из 5 карт одной и той же масти

называется флешем. Сколько всего может быть флешей? Чтобы посчитать, сначала выберем масть – 1 из 4 вариантов (давайте договоримся, что это будут пики). Сколько всего можно собрать комбинаций разных 5 карт этой масти? В колоде 13 пиковых карт. Значит, флешей всего

и наши шансы получить один из них составляют 5148/2 598 960, то есть примерно 1 к 500. Любители покера теперь могут вычесть из 5 148 4 × 10 = 40, чтобы узнать, какова вероятность, что собрать стрит-флеш – такой флеш, в котором карты одной масти идут подряд по старшинству.

При простом стрите масти в расчет не принимаются, главное – последовательный набор карт: Т-2-3-4-5 или 2-3-4-5-6, или…, или 10-В-Д-К-Т. Вот так, например:

Стрит может сложиться из 10 разных комбинаций (ценность которых определяется «ценностью» младшей карты). Определив ту из них, которая нужна нам (пусть будет 3-4-5-6-7), мы выбираем одну из 4 мастей, которой должны быть все карты. Следовательно, количество комбинаций стрита равняется

10 × 45 = 10 240

то есть почти в 2 раза выше, чем у флеша. А шанс его получить – 1 к 250. Именно поэтому флеш в покере ценится больше: его куда сложнее собрать.

Еще более ценен фул-хаус – 3 карты одного достоинства плюс 2 карты другого. Что-то вроде этого[9]9
  Дама (Q) в тексте обозначается как Д. – Прим. пер.


[Закрыть]:

Чтобы подсчитать свои шансы на фул-хаус, нам сперва нужно выбрать необходимое нам достоинство, которое попадется нам трижды (13 вариантов), потом – то, которое попадется дважды (12 вариантов). Допустим, нам нужны 3 дамы и 2 семерки. Определимся с мастями. Получить нужных нам дам можно способами, семерки – способами. Общее количество фул-хаусов, таким образом, равняется

13 × 12 × 4 × 6 = 3744

Следовательно, вероятность его собрать – 3744/2 598 960 или 1 к 700.

От фул-хаусов перейдем к двум парам. Здесь нам нужны две карты одного достоинства, еще две – другого, и последняя – третьего, например

Пытаясь посчитать количество возможных пар, многие ошибочно начинают с 13 × 12, как в случае с фул-хаусами. Но теперь нам нужно немного другое, ведь здесь вероятность получить две семерки после двух дам – это абсолютно то же, что и получить двух дам после двух семерок. Поэтому правильно будет начать с (имея в виду и семерки, и дам), потом выбрать новое достоинство для непарной карты (пусть это будет пятерка), затем выбрать масти. Количество комбинаций с двумя парами –

Появляются они в 5 % случаев.

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


[Закрыть], вроде может быть

с тройкой-[11]11
  Тройка – три карты одного достоинства. – Прим. пер.


[Закрыть], например,  –

с одной парой – скажем,  –

всего – 42 % всех возможных комбинаций.

Отступление

А сколько же может быть «пустых» комбинаций – без пар, без стритов и без флешей? Можете, конечно, сложить все числа, которые мы получили до этого и вычесть сумму из но я облегчу вам жизнь и просто дам ответ:

Первая часть – это количество комбинаций 5 карт разного достоинства за вычетом 10 последовательных (вроде 3-4-5-6-7). Следующая часть охватывает вероятные «расклады» этих 5 карт разного достоинства; для каждого достоинства у нас есть 4 варианта, но при этом мы должны исключить возможность того, что все они встретятся в одном «раскладе». Все это значит, что наши шансы собрать «пустую» комбинацию – 50,1 %. А еще это значит, что в 49,9 % случаев мы будем играть как минимум с одной парой.

А теперь вопрос, на который можно дать целых три прелюбопытных ответа, причем правильными из них будут сразу два! Сколько существует комбинаций, в которых есть как минимум один туз? Уверен, вас так и подмывает ответить что, само собой, неправильно. Вы же исходите (и напрасно) из того, что сначала нужно выбрать туза (4 варианта), а потом собирать любые другие 4 карты из 51 оставшейся в колоде. Неправильно здесь то, что вы таким образом просчитываете некоторые комбинации (а именно – те, в которых больше одного туза) несколько раз. Например, комбинация  будет посчитана дважды: сначала для Т♠ в качестве первой, основной карты, а затем так же для Правильный способ решить эту задачу – разбить ее на четыре задачи поменьше, в зависимости от того, сколько тузов будет в комбинации. Так, комбинаций именно с одним тузом будет (сначала выбираем туза, потом – остальные 4 карты другого достоинства). Затем отдельно же просчитываем комбинации с двумя, тремя и четырьмя тузами. В результате получаем

Но проще всего будет пойти от обратного. Сначала посчитаем количество комбинаций без туза (это легче легкого) – А количество комбинаций по крайней мере с одним тузом, таким образом, –

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

Пара

Две пары

Тройка

Стрит

Флеш

Фул-хаус

Каре (или «четверка»)

Стрит-флеш

На этот случай есть эффективная «запоминалка»: «Раз, два, три, стрит, флеш; два-три, четыре, стрит-флеш» (где «два-три» – это фул-хаус).

А теперь предположим, что в колоде появились джокеры. Всего карт у нас становится 54, причем джокеры (всего их два) могут «превращаться» в карту любой масти и любого достоинства – в зависимости от того, что вам нужно для наилучшей комбинации. То есть если у вас на руках и джокер, разумнее всего будет посчитать его тузом, чтобы получилась тузовая тройка. Можно «превратить» джокера и в короля, конечно, но тогда у вас будет две пары, что хуже, чем тройка[12]12
  A на рисунках в тексте обозначается как Т (туз); Joker – как Джокер. – Прим. пер.


[Закрыть].

Но здесь-то и начинается самое интересное. Следуя традиционному порядку карт, мы можем посчитать эту комбинацию и как тройку, и как две пары, а можем – только как тройку, исключив ее из числа двух пар. Последнее выглядит наиболее разумно, но ведь это значит, что общее количество комбинаций с тройками значительно увеличивается, а с двумя парами – уменьшается, что превращает последние в более редкие. Мы, конечно, можем сказать, что теперь две пары имеют бóльшую ценность, но проблему этим не решишь: она всего лишь «перевернется вверх ногами», ведь количество двух пар увеличится, а количество троек – уменьшится. Из этого всего следует странный на первый взгляд вывод, сделанный математиком Стивом Гэдбойсом в 1996 году: при игре в покер с джокерами невозможно ранжировать «ценность» комбинаций по частоте их появления.