Есть идея! - [4]

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

Комбинаторные аспекты присущи всем разделам математики, и не удивительно поэтому, что читатель обнаружит комбинаторные задачи во всех без исключения главах нашей книги. Так, существует комбинаторная теория чисел, комбинаторная топология, комбинаторная логика, комбинаторная теория множеств и даже, как мы увидим в последней главе, посвященной словесным играм, комбинаторная лингвистика. Особенно важную роль комбинаторика играет в теории вероятностей: без подсчета всех комбинаций нельзя было бы найти распределение вероятностей. Много задач по теории вероятностей собрано в книге Уитворта «Выбор и случай»[2]. Слово «выбор» в заголовке книги указывает на ее комбинаторный аспект.

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

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

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

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

Вторая задача о непригодных пилюлях вскрывает комбинаторный характер рассуждений, связанных с использованием различных систем счисления. Как будет показано, и сами числа, и их цифровая запись в позиционной системе счисления зависят от некоторых комбинаторных правил. Более того, любое дедуктивное умозаключение, будь то в математике или в формальной логике, оперирует с комбинацией символов, выстроенных в «строку» по определенным правилам. Эти правила позволяют решить, допустима ли та или иная строка символов в рассматриваемой теории или недопустима. Именно поэтому отец комбинаторики Лейбниц называл искусство строить умозаключения комбинаторным искусством — ars combinatoria.

Жевательная резинка

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

Первый близнец. Мама, купи мне жевательную резнику!

Второй близнец. И мне, и мне! Я хочу шарик такого же цвета, как у Билли.

Автомат был почти пуст. Предугадать, какого цвета шарик выпадет, если опустить в щель автомата монету в 1 пенс, невозможно. Сколько однопенсовых монет придется приготовить миссис Джонс, чтобы из купленных шариков заведомо можно было выбрать 2 шарика одного и того же цвета?

Потратив 6 пенсов, миссис Джонс заведомо могла бы извлечь из автомата 2 красных шарика; 4 пенса ушли бы на «добывание» 4 белых шариков, а 2 пенса — на 2 красных шарика. Израсходовав 8 пенсов, миссис Джонс заведомо получила бы 2 белых шарика. Следовательно, миссис Джонс необходимо приготовить 8 центов. Правильно?