Найти «доказательство невозможности», то есть доказать, что не существует ни одной комбинации с требуемыми свойствами, в комбинаторном анализе зачастую бывает чрезвычайно трудно. Например, лишь недавно удалось, доказать, что для правильной раскраски стран на плоской карте достаточно четырех красок. «Проблема четырех красок» долгое время оставалась знаменитой нерешенной задачей комбинаторной топологии. Решить ее, то есть найти «доказательство невозможности», удалось лишь после того, как была составлена специальная, необычайно сложная программа для ЭВМ.
С другой стороны, многие комбинаторные задачи, для которых найти «доказательство невозможности» на первый взгляд кажется необычайно трудным делом, при правильном подходе решаются легко и просто. В задаче «Упрямые плитки» мы увидим, как простая «проверка на четность» сразу же приводит к доказательству неразрешимости задач, найти которое другим путем было бы нелегко.
Вторая задача о непригодных пилюлях вскрывает комбинаторный характер рассуждений, связанных с использованием различных систем счисления. Как будет показано, и сами числа, и их цифровая запись в позиционной системе счисления зависят от некоторых комбинаторных правил. Более того, любое дедуктивное умозаключение, будь то в математике или в формальной логике, оперирует с комбинацией символов, выстроенных в «строку» по определенным правилам. Эти правила позволяют решить, допустима ли та или иная строка символов в рассматриваемой теории или недопустима. Именно поэтому отец комбинаторики Лейбниц называл искусство строить умозаключения комбинаторным искусством — 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 шарика заведомо были одного и того же цвета).