Есть идея!

Комбинаторные аспекты присущи всем разделам математики, и не удивительно поэтому, что читатель обнаружит комбинаторные задачи во всех без исключения главах нашей книги. Так, существует комбинаторная теория чисел, комбинаторная топология, комбинаторная логика, комбинаторная теория множеств и даже, как мы увидим в последней главе, посвященной словесным играм, комбинаторная лингвистика. Особенно важную роль комбинаторика играет в теории вероятностей: без подсчета всех комбинаций нельзя было бы найти распределение вероятностей. Много задач по теории вероятностей собрано в книге Уитворта «Выбор и случай» [2]. Слово «выбор» в заголовке книги указывает на ее комбинаторный аспект.
Самая первая задача в нашей книге также имеет непосредственное отношение к теории вероятностей: ведь, в ней требуется указать комбинацию цветных шариков, которая с полной гарантией (то есть с вероятностью, равной 1) позволила бы удовлетворить определенным требованиям. Читая нашу книгу, нетрудно убедиться в том, что из простых вопросов о перечислении способов объединения предметов по тому или иному признаку возникает поистине безбрежное море вероятностных задач. Перечисление маршрутов, по которым Сьюзен могла бы следовать в школу, тесно связано с треугольником Паскаля и теми применениями, которые он находит при решении элементарных задач теории вероятностей.
Число комбинаций, дающих решение данной комбинаторной задачи, очевидно, может быть равно нулю, единице, любому конечному числу и даже обращаться в бесконечность. Например, нечетное число ни одним способом невозможно представить в виде суммы двух четных чисел. Число 21 представимо в виде произведения двух простых чисел одним и только одним способом. Число 7 представимо в виде суммы из двух целых положительных чисел тремя различными способами (слагаемые каждой из трех допустимых комбинаций нанесены на противоположные грани игральной кости). Существует бесконечно много пар четных чисел, сумма которых четна.
Найти «доказательство невозможности», то есть доказать, что не существует ни одной комбинации с требуемыми свойствами, в комбинаторном анализе зачастую бывает чрезвычайно трудно. Например, лишь недавно удалось, доказать, что для правильной раскраски стран на плоской карте достаточно четырех красок. «Проблема четырех красок» долгое время оставалась знаменитой нерешенной задачей комбинаторной топологии. Решить ее, то есть найти «доказательство невозможности», удалось лишь после того, как была составлена специальная, необычайно сложная программа для ЭВМ.
С другой стороны, многие комбинаторные задачи, для которых найти «доказательство невозможности» на первый взгляд кажется необычайно трудным делом, при правильном подходе решаются легко и просто. В задаче «Упрямые плитки» мы увидим, как простая «проверка на четность» сразу же приводит к доказательству неразрешимости задач, найти которое другим путем было бы нелегко.
Вторая задача о непригодных пилюлях вскрывает комбинаторный характер рассуждений, связанных с использованием различных систем счисления. Как будет показано, и сами числа, и их цифровая запись в позиционной системе счисления зависят от некоторых комбинаторных правил. Более того, любое дедуктивное умозаключение, будь то в математике или в формальной логике, оперирует с комбинацией символов, выстроенных в «строку» по определенным правилам. Эти правила позволяют решить, допустима ли та или иная строка символов в рассматриваемой теории или недопустима. Именно поэтому отец комбинаторики Лейбниц называл искусство строить умозаключения комбинаторным искусством — ars combinatoria.
  
Жевательная резинка
 
Миссис Джонс не повезло: ее близнецы заметили автомат для продажи разноцветных шариков жевательной резинки прежде, чем миссис Джонс успела миновать его.
Первый близнец. Мама, купи мне жевательную резнику!
Второй близнец. И мне, и мне! Я хочу шарик такого же цвета, как у Билли.
Автомат был почти пуст. Предугадать, какого цвета шарик выпадет, если опустить в щель автомата монету в 1 пенс, невозможно. Сколько однопенсовых монет придется приготовить миссис Джонс, чтобы из купленных шариков заведомо можно было выбрать 2 шарика одного и того же цвета?
Потратив 6 пенсов, миссис Джонс заведомо могла бы извлечь из автомата 2 красных шарика; 4 пенса ушли бы на «добывание» 4 белых шариков, а 2 пенса — на 2 красных шарика. Израсходовав 8 пенсов, миссис Джонс заведомо получила бы 2 белых шарика. Следовательно, миссис Джонс необходимо приготовить 8 центов. Правильно?
Нет, не верно! Если бы первые два шарика, выкатившиеся из автомата, были разного цвета, третий шарик непременно совпал бы по цвету с одним из них. Следовательно, миссис Джонс необходимо приготовить всего лишь 3 пенса.
Предположим теперь, что в автомате осталось 6 красных, 4 белых и 5 синих шариков. Сможете ли вы подсчитать, сколько монет в 1 пенс следует приготовить миссис Джонс, чтобы среди выкатившихся из автомата шариков заведомо нашлось 2 шарика одного и того же цвета?
По-вашему, ей хватит 4 центов? А что вы скажете о бедной миссис Смит, которая безуспешно пыталась отвлечь от автомата для продажи жевательной резинки внимание своей тройни?
На этот раз в автомате находились 6 красных, 4 белых шарика и лишь 1 синий шарик. Сколько монет достоинством в 1 пенс следует приготовить миссис Смит, чтобы среди купленных шариков заведомо были 3 шарика одного цвета?
Сколько центов?
Вторая задача о шариках жевательной резинки лишь незначительно отличается от первой. Идея решения второй задачи по существу та же: первые три шарика могут быть разного цвета (например, один шарик может быть красным, один синим и один белым). Это наименее благоприятный случай, так как к достижению желаемого результата ведет самая длинная последовательность испытаний. Четвертый шарик заведомо совпадает по цвету с одним, из трех первых шариков. Итак, чтобы 2 шарика оказались одного и того же цвета, необходимо купить 4 шарика. Следовательно, миссис Джонс следует приготовить 4 цента.
Обобщение на случай n множеств шариков (каждое множество составляют шарики одного цвета) очевидно: если имеется n множеств шариков, то следует быть готовым к тому, что придется купить n + 1 шариков (чтобы 2 шарика заведомо были одного и того же цвета).
Третья задача потруднее двух предыдущих. У миссис Смит не близнецы, а тройня. В автомате находятся б красных, 4 белых шарика и 1 синий шарик. Сколько монет достоинством в 1 цент должна приготовить миссис Смит, чтобы среди шариков, выданных автоматом, заведомо были 3 шарика одного цвета?
Как и прежде, начнем с рассмотрения наименее благоприятного случая. Миссис Смит может получить из автомата 2 красных, 2 белых шарика и 1 синий шарик, то есть всего 5 шариков. Шестой шарик должен быть либо красным, либо белым и, следовательно, подходить по цвету к ранее выпавшим из автомата либо 2 красным, либо 2 белым шарикам. Значит, миссис Смит должна приготовить 6 центов. Если бы синих шариков в автомате было не меньше двух, то в наименее благоприятном случае миссис Смит могла бы сначала извлечь из автомата по 2 шарика каждого цвета, и, чтобы получить 3 шарика одного и того же цвета, ей непременно понадобился бы седьмой шарик.
«Неожиданное» решение — это своего рода «прозрение», позволяющее оценить длину серии испытаний в наименее благоприятном случае. Ту же задачу можно было бы решить и более сложным способом: обозначить каждый из 11 шариков «своей» буквой, выписать все возможные варианты выдачи шариков из автомата и установить, в каком случае длина цепочки испытаний до появления трех шаров одного цвета имеет наибольшую длину. Но при таком решении потребовалось бы перебрать 11! = 39 916 800 последовательностей всех возможных исходов испытаний. Если мы условимся не различать шары одного цвета, то и тогда при таком подходе пришлось бы перебрать 2310 последовательностей возможных исходов.