Неожиданные решения задач на составление и перечисление комбинаций

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

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

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

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

Самая первая задача в нашей книге также имеет непосредственное отношение к теории вероятностей: ведь, в ней требуется указать комбинацию цветных шариков, которая с полной гарантией (то есть с вероятностью, равной 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 последовательностей возможных исходов.

Обобщение задачи на случай, когда требуется определить наименьшее число монет, при котором из выданных автоматом шаров заведомо можно выбрать k шариков одного цвета, приводит к следующему решению. Если имеются шары n цветов (шаров каждого цвета не меньше k), то для получения k шаров одного цвета необходимо выбрать не более n(k − 1) + 1 шаров. Читателю доставит удовольствие самостоятельно исследовать, что произойдет в том случае, если шаров одного или нескольких цветов будет меньше k.

Задачи этого типа можно промоделировать не только на автоматах для продажи жевательной резинки, но и многими другими способами. Например, сколько карт необходимо вытащить из колоды в 52 листа, чтобы 7 карт заведомо были одной масти? Здесь n = 4, k = 7, и наша формула дает ответ? 4(7–1)+1=25.

Мы рассмотрели лишь очень простые комбинаторные задачи, но и они приводят к интересным и трудным вопросам теории вероятностей. Например, какова вероятность извлечь 7 карт одной масти, если вы вытаскиваете из колоды, не возвращая, n карт, где n — любое число от 7 до 24? (Вероятность извлечь 7 карт одной масти, очевидно, равна 0, если из колоды вытащить менее 7 карт, и равна 1, если вытащить более 24 карт). Как изменятся вероятности, если мы условимся возвращать каждую извлеченную карту и тщательно тасовать колоду перед тем, как вытягивать из нее очередную карту? Более трудный вопрос: каково математическое ожидание (среднее по длинной серии испытаний) числа карт, которые необходимо извлечь (с возвратом или без возврата) из колоды, чтобы k из них заведомо были одной масти?

 

Турнир по настольному теннису

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

Тренер составил таблицу розыгрыша турнира, снабдив ее следующими пояснениями.

Тренер. Пять — число нечетное, поэтому в первой круге один участник турнира свободен от игры. Еще один участник свободен от игры во втором круге. Таким образом, всего за турнир будет сыграно 4 партии.

На следующий год в спортивный клуб записалось 37 школьников. Тренер снова составил таблицу розыгрыша турнира, постаравшись свести до минимума число участников, которые переходят в следующий круг без игры. Сколько партий было сыграно за весь турнир на этот раз?

Как, вы еще не сосчитали? А ведь задача решается просто! В каждой партии проигравший выбывает, а поскольку дли того, чтобы определить победителя, следует исключить всех участников, кроме одного, то за весь турнир должно состояться 36 партий. Не правда ли, все очень просто?

Сколько участников турнира перейдут в следующий круг без игры?

Если вы пытались решить задачу о турнире по настольному теннису «в лоб», составляя различные варианты таблиц розыгрыша турнира с 37 участниками, то, должно быть, заметили, что независимо от способа составления таблицы число участников, переходящих в следующий круг без игры, всегда равно 4. В общем случае число участников, для которых в очередном круге не хватает партнера, есть функция от числа n всех участников турнира. Кате установить, сколько участников вынуждены будут перейти в следующий круг без игры?

При заданном n число участников, остающихся без партнера, можно определить следующим образом. Вычтем из n наименьшую степень числа 2, которая больше или равна n. Полученную разность запишем в двоичной системе. Число единиц в двоичной записи и будет равно числу участников турнира, вынужденных перейти в следующий круг без игры из-за нехватки партнера. В нашей задаче мы вычтем 37 из 64 (то есть из 26) и получим разность, равную 27. Десятичное число 27 в двоичной системе имеет вид 11011. Поскольку в его записи 4 единицы, то за весь турнир без игры в следующий круг перейдут 4 игрока. Обоснование этого алгоритма для определения числа участников, которым не хватает партнера, мы предоставляем читателю в качестве интересного упражнения.

Описанный в задаче тип турнира иногда называют «игрой на вылет». Он аналогичен алгоритму, который вычислители, работающие на современных ЭВМ, используют для нахождения наибольшего элемента в множестве из n элементов: наибольший элемент находят, сравнивая попарно элементы множества и отбрасывая при очередном сравнении тот из двух элементов, который не больше другого. Как мы уже знаем, чтобы найти наибольший элемент, достаточно произвести ровно n − 1 попарных сравнений. При автоматической сортировке сравнивать можно не только по 2, но и по 3, 4 и т. д. элемента.

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

 

Стаканчики профессора Квиббла

Как-то раз продавец прохладительных напитков Барни предложил двум покупателям следующую задачку.

Барни. Перед вами 10 бумажных стаканчиков, расставленных в ряд. В первые 5 стаканчиков я наливаю кинки-колу, остальные 5 стаканчиков остаются пустыми. Можно ли переставить 4 стаканчика так, чтобы пустые и полные стаканчики чередовались?

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

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

Проф. Квиббл. Переставлять 4 стаканчика совсем не обязательно. Я берусь решить задачу, переставив лишь 2 стаканчика. Как, по-вашему, это возможно?

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

Глубокая мысль

Хотя предложенное профессором Квибблом шуточное решение основано на неоднозначном толковании слова «переставить» (означающего не только «поменять местами», как полагал Барни, но и «поставить по-другому», чем и воспользовался профессор Квиббл), исходная задача не столь тривиальна, как может показаться. Рассмотрим, например, аналогичную задачу для случая, когда из 200 стаканчиков, выстроенных в ряд, в первые 100 налита кинки-кола, а 100 остальных оставлены пустыми. Сколько пар стаканчиков следует поменять местами, чтобы пустые и полные стаканчики чередовались?

Поскольку следить за 200 стаканчиками довольно трудно, разберем сначала ту же задачу при меньших значениях n, где n — число полных (или пустых) стаканчиков, и попытаемся подметить общую закономерность. Стаканчики можно «моделировать» фишками двух цветов, игральными картами, выложенными на столе рубашкой либо вверх, либо вниз, монетами и тому подобными предметами, наделенными каким-нибудь «двузначным» признаком. При n = 1 для решения задачи не требуется переставлять ни одной пары стаканчиков. При n = 2 решение очевидно и сводится к перестановке одной пары стаканчиков. Возможно, вы удивитесь, когда узнаете, что при n = 3 чередование пустых и полных стаканчиков достигается перестановкой одной пары стаканчиков. Еще немного усилий, и вам откроется довольно простая общая закономерность. При четном n для решения задачи требуется поменять местами n/2 пар, а при нечетном n соответственно (n − 1)/2 пар стаканчиков. Следовательно, если имеется 100 пустых и 100 полных стаканчиков, то задачу можно решить, переставив 50 пар стаканчиков.

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

Существует одна классическая головоломка, очень похожая на только что рассмотренную нами задачу, но несколько более трудную. Начнем с 2n предметов, выстроенных в ряд. Пусть по-прежнему n предметов, составляющих первую половину ряда, будут одного типа, а n предметов, составляющих вторую половину ряда, будут другого типа. (Как и прежде, их можно «моделировать» стаканчиками, фишками, игральными картами и т. п.) Требуется переместить предметы так, чтобы предметы одного типа чередовались с предметами другого типа, но в отличие от предыдущей задачи слову «переместить» придается строго определенное значение. На этот раз слово «переместить» означает, что любые два соседних предмета разрешается, не изменяя их последовательности, изъять из ряда и пристроить к любому свободному концу (после одного или нескольких ходов ряд может распасться на несколько звеньев).

Вот как это делается, например, при n = 3:

Как выглядит общее решение? При n = 1 решение тривиально. При n = 2 задача, как нетрудно выяснить, неразрешима. При всех n > 2 головоломка допускает решение не менее чем за n ходов.

Найти решение при n = 4 не так-то просто, и поиск его, несомненно, доставит вам немало удовольствия. Может быть, вам удастся сформулировать алгоритм решения головоломки за n ходов при любом n > 3.

Не меньший вызов любознательному читателю таят в себе многие необычные варианты той же головоломки. Приведем лишь некоторые из них.

1. Правила перемещения пар остаются теми же за одним исключением: если пара образована предметами различных типов, то перед тем, как пристроить ее к свободному концу, последовательность предметов в паре следует изменить. Например, перемещая две фишки, первая из которых (левая) красная, а вторая (правая) черная, их необходимо поменять местами, после чего первой станет черная, а второй красная фишка, и лишь после этого пристраивать к свободному концу. При 8 фишках существует решение в 5 ходов. При 10 фишках 5 ходов также оказывается достаточно. Общее решение неизвестно. Может быть, вам удастся найти его.

2. Правила такие же, как в исходной задаче, но фишек одного цвета на 1 меньше, чем другого, то есть фишек одного цвета n, а фишек другого n + 1. Доказано, что при любом n задачу можно решить за n² ходов, причем это число минимально.

3. Имеются фишки трех различных цветов. Пары соседних фишек перемещаются по обычному правилу с тем, чтобы фишки каждого цвета оказались выстроенными подряд. При n = 3 (всего 9 фишек) существует решение в 5 ходов. И в этом, и во всех предыдущих вариантах головоломки предполагается, что после последнего перестроения фишки стоят в ряд «сомкнутым строем» (без пробелов). Если ряд может содержать пробелы, то существует необычное решение всего лишь в 4 хода.

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

Что произойдет, если на первом ходу переместить фишку, на втором — 2 фишки, на третьем — 3 фишки и т. д.? Если в ряд выстроены n фишек одного цвета и затем п фишек другого цвета, то всегда ли правильного чередования цветов можно добиться за n ходов?

 

Дороги, которые мы выбираем

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

Станки. Эй, Сьюзен! Можно, я пойду с тобой?

Сьюзен. Нет, очень тебя прошу, уйди!

Сьюзен. Я придумала, что мне делать. Буду ходить в школу каждое утро другой дорогой. Тогда Станки ни за что не догадается, где меня можно подстеречь.

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

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

Сьюзен. Хотела бы я знать, сколько различных дорог ведет от моего дома к школе. Подумаем! Сосчитать их, должно быть, не просто. Впрочем… Есть идея! Сосчитать дороги совсем не трудно! Очень даже просто!

Какая идея пришла в голову Сьюзен?

Вот как она рассудила.

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

Сьюзен. У этого перекрестка я поставлю число 2, так как к нему от моего дома ведут 2 различные дороги.

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

Сьюзен. Еще четыре перекрестка пометила числами. Скоро закончу.

Не поможете ли вы Сьюзен? Не подскажете ли ей, сколько различных дорог ведет от ее дома к школе?

Сколько путей?

Три перекрестка на ближайшей вертикали справа следует пометить (сверху вниз) числами 1, 4, 9, а два перекрестка на следующей вертикали — числами 4 и 13. Число 13, стоящее на карте у самого правого нижнего перекрестка, показывает, что Сьюзен может выбрать кратчайшую дорогу в школу 13 различными способами.

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

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

Чему равно число кратчайших путей, по которым ладья может перейти из одного углового поля на шахматной доске в другое, диагонально противоположное? Эта задача легко решается, если каждому полю на шахматной доске приписать по числу так же, как Сьюзен приписывала числа перекресткам на карте города. Ладья ходит только по горизонтали и вертикали. Следовательно, кратчайший путь из любой клетки в любую другую состоит в преодолении разделяющего клетки расстояния по горизонтали и по вертикали. Если числа расставлены верно (см. рис. 2), то они указывают число кратчайших путей, ведущих из нижнего угла в любое поле. Например, поле в правом верхнем углу помечено числом 3432. Следовательно, ладья может перейти с поля, стоящего в левом нижнем углу доски на диагонально противоположное поле 3432 кратчайшими путями.

Разрезав шахматную доску по диагонали и повернув половину, мы получим треугольник, изображенный на рис. 3. Числа, стоящие в клетках любого ряда, указывают число кратчайших путей, ведущих в них из самой верхней клетки. Расставленные в клетках числа образуют знаменитый арифметический треугольник Паскаля, и это не удивительно: алгоритм для подсчета числа кратчайших путей, ведущих от вершины, в точности совпадает с процедурой построения треугольника Паскаля. Этот изоморфизм позволяет считать исходную головоломку прологом к изучению необычайно разнообразных и красивых свойств треугольника Паскаля.

Треугольник Паскаля позволяет находить биномиальные коэффициенты (то есть коэффициенты при любом члене разложения (a + b)n , где n — любое целое число) и решения многих задач элементарной теории вероятностей. Заметим, что на рис. 3 число кратчайших путей, ведущих из вершины треугольника в самую левую или самую правую клетку нижнего ряда, равно 1 и что по мере приближения к середине ряда число кратчайших путей возрастает. Возможно, вам случалось видеть одно из устройств, действие которых основано на свойствах треугольника Паскаля: по наклонной доске, в которую в шахматном порядке вбиты колышки, скатываются шарики и скапливаются в отсеках под колышками нижнего ряда. Распределение шариков имеет форму колоколообразной кривой, а число шариков в каждом отсеке пропорционально соответствующему биномиальному коэффициенту, потому что число кратчайших путей, ведущих в каждый отсек, в точности совпадает с определенным биномиальным коэффициентом.

Алгоритм, предложенный Сьюзен, как нетрудно понять, остается в силе и для трехмерных сетей, в которых ячейки («кварталы») имеют форму прямоугольных параллелепипедов. Представьте себе куб с длиной ребра 3 единицы, разделенный на 27 единичных кубов. Будем считать его пространственной шахматной доской и в угловую «клетку» поместим ладью, которая может двигаться параллельно любому из ребер куба. Сколькими способами ладью можно перевести кратчайшим путем в клетку, расположенную на другом конце диагонали куба?

 

Перепутали

В одном родильном доме по чьему-то недосмотру перепутали карточки с именами 4 младенцев. У двух детей оказались их карточки, а карточки остальных двух малюток были разложены неправильно.

Сколько существует различных вариантов путаницы?

Подсчитать число вариантов совсем нетрудно, если составить таблицу. Оказывается, что карточки с именами 2 детей из 4 можно перепутать лишь 6 различными способами.

Предположим теперь, что после того, как карточки перепутали, у трех детей оказались карточки с их именами, а одному младенцу досталась карточка с чужим именем. Сколько вариантов путаницы существует в этом случае?

Как бы вы стали решать эту задачу? Составили бы таблицу? А может быть, у вас есть идея, как решить эту задачу проще?

«Птичка в клетке»

Многим кажется, что ответить на вопрос задачи довольно трудно. Те, кто так думает, ошибочно полагают, будто перепутать карточки так, чтобы 3 младенцам из 4 достались карточки с их именами, можно многими способами. Но стоит лишь обратиться к принципу «птичка в клетке» и сформулировать задачу несколько иначе, как ответ сразу становится очевидным. Предположим, что перед нами 4 клетки и на каждой из них укреплена карточка с названием одного из 4 предметов. Если 3 предмета попали в клетки со своими названиями, то четвертому предмету не остается ничего другого, как попасть в клетку, к которой прикреплена карточка с его названием. Таким образом, мы имеем дело лишь с одним вариантом: каждый из 4 предметов оказывается в своей клетке.

Во многих книгах по занимательной математике встречается следующая задача, в которой речь идет лишь о 3 предметах. На столе расставлены 3 закрытые коробки. В одной из них находятся 2 монеты по 5 центов, в другой — 2 монеты по 10 центов и в третьей — 1 пятицентовая и 1 десятицентовая монета. На крышках коробок написано: 10 центов; 15 центов и 20 центов, но ни одна из надписей не соответствует содержимому коробки. Предположим, что из коробки с надписью «15 центов» (напомним, что надпись не соответствует содержимому коробки) извлекли 1 монету и положили на стол перед коробкой. Можно ли, взглянув на эту монету, сказать, какие монеты находятся в каждой из 3 коробок?

Как и в предыдущей задаче, многих вводит в заблуждение кажущаяся неоднозначность выбора: они думают, будто существует довольно много вариантов решения, тогда как на самом деле задача допускает единственное решение. Монета, извлеченная из коробки с надписью «15 центов» (не соответствующей содержимому), может быть монетой достоинством либо в 5 центов, либо в 10 центов. Если извлечена монета достоинством в 5 центов, то в коробке первоначально находились 2 монеты по 5 центов. Если извлечена монета достоинством в 10 центов, то в коробке первоначально находились 2 монеты по 10 центов. И в том и в другом случае содержимое остальных двух коробок восстанавливается однозначно. Нетрудно видеть, что не соответствующие содержимому каждой коробки надписи оставляют лишь 2 варианта распределения монет по: коробкам. После того как из коробки с ложной надписью «15 центов» извлечена 1 монета, один вариант исключается, и остается единственный допустимый вариант, соответствующий правильному решению.

Иногда встречается несколько более сложная разновидность той же задачи. Содержимое всех трех коробок требуется определить, извлекая наименьшее число монет (из любой коробки). Единственное решение задачи состоит в том, чтобы из коробки с надписью «15 центов» извлечь 1 монету. Может быть, вам удастся придумать более сложные варианты задачи: в одной коробке могут находиться более 2 монет, да и самих коробок может быть более 3.

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

Вопрос о «по крайней мере одном» — независимо от того, о чем идет речь, — один из классических вопросов занимательной математики. Довольно часто его облекают в форму задачи об n посетителях ресторана, сдавших шляпы в гардероб. Рассеянный гардеробщик выдал посетителям номера наугад, нимало не заботясь о том, кому достанется номерок от шляпы — ее владельцу или кому-нибудь другому. Какова вероятность, что по крайней мере один посетитель получит свою шляпу? Оказывается, что при возрастании n эта вероятность быстро стремится к 1 — (1/e), то есть немногим больше ½. Здесь e — знаменитая иррациональная константа (число Эйлера), равная 2,71828… В задачах теории вероятностей она встречается так же часто, как число π в геометрических задачах.

 

Стаканы профессора Квиббла

У профессора Квиббла имеется для вас задача-головоломка.

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

Проф. Квиббл. Задачка не из трудных, не так ли? И решений она допускает много. Например, в один стакан можно положить 3 монеты, в другой — 7 монет, а в третий — 1 монету.

Проф. Квиббл. А сумеете ли вы разложить по тем же 3 стаканам 10 монет так, чтобы число монет в каждом стакане было нечетным? Сделать это можно, хотя и не просто!

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

Подмножества Квиббла

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

Найти все остальные решения мы предоставляем читателю. Додуматься до 10 решений, одно из которых предложил проф. Квиббл, не составит особого труда, но найти еще 5 решений (всего существует 15 решений задачи) не так-то просто: необходимо «озарение».

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

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

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

— Я сплю 8 часов в сутки. Это составляет 8 × 365 = 2920 часов в году, или, так как в сутках 24 часа, 2920: 24 (около 122) суток.

По субботам и воскресеньям школа не работает, что составляет за год 104 дня.

60 дней в году приходятся на летние каникулы.

На завтрак, обед и ужин у меня уходит 3 часа в день, то есть 3 × 365 = 1095 часов, или 1095: 24 (около 45 суток) в год.

По крайней мере 2 часа в день мне необходимы для отдыха, что составляет 2 × 365 = 730 часов, или 730: 24 (около 30 суток) в год.

Школьник выписал названные им числа в столбец и просуммировал:

На сон — 122

Субботы и воскресенья — 104

Летние каникулы — 60

Завтраки, обеды и ужины — 45

Отдых — 30

Итого — 361 день

— Видите, — продолжал школьник, — у меня остается всего-навсего 4 дня в год на болезни, а о праздниках я и не говорю!

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

 

Как поджарить ромштексы?

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

Мистер Джонсон. Чтобы поджарить с двух сторон 1 ромштекс, требуется 20 мин (по 10 мин на каждую сторону). Значит, за 20 мин можно приготовить 2 ромштекса. Еще 20 мин мне понадобится, чтобы поджарить третий ромштекс, поэтому всего на приготовление 3 ромштексов придется затратить 40 мин.

Бетси. Папочка, ромштексы можно поджарить гораздо быстрее! Я только что придумала, как можно сэкономить 10 мин.

Какая удачная мысль позволила Бетси сократить приготовление обеда на 10 мин?

Чтобы объяснить предложенное Бетси решение, обозначим ромштексы A, B и C, а их стороны — цифрами 1 и 2. За первые 10 мин следует поджарить стороны А1 и В1.

Отложим ромштекс B в сторону и поджарим за следующие 10 мин стороны A2 и C1. К концу 20-й минуты ромштекс A будет готов.

Еще через 10 мин поджарятся стороны B2 и C2. Таким образом, на приготовление всех 3 ромштексов уйдет всего 30 мин, что и утверждала Бетси.

Общая стратегия

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

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

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

Из длинного списка хлопотливых домашних дел мистеру и миссис Джонс осталось выполнить три пункта:

1) произвести уборку на первом этаже (у семейства Джонсов имеется 1 пылесос, на уборку первого этажа уходит 30 мин);

2) подстричь газон перед домом (у семейства Джонсов имеется 1 машинка для стрижки газона, на выполнение этого задания необходимо затратить 30 мин);

3) накормить и уложить спать ребенка (на это также требуется затратить 30 мин).

Как следует распределить обязанности супругам Джонс, чтобы завершить все работы по дому в кратчайший срок? Если предположить, что мистер и миссис Джонс работают одновременно, то трудно удержаться от искушения дать ответ: «На выполнение 3 пунктов программы у супругов Джонс уйдет 60 мин». Но если одну из работ, например уборку первого этажа, разделить на 2 равные части и выполнение второй половины отложить (как в задаче с поджариванием ромштексов) до завершения другой работы, то на выполнение намеченной программы у супругов Джонс уйдет лишь ¾ времени (по сравнению с первым вариантом), или 45 мин.

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

Чтобы положить ломтик хлеба в тостер, требуется затратить 3 с. Еще 3 с уходит на то, чтобы вынуть каждый ломтик из тостера, и 3 с требуется для того, чтобы повернуть ломтик на другую сторону, не вынимая его из тостера. Каждую из этих операций необходимо производить двумя руками. Это означает, что ли одну из них нельзя выполнить одновременно над двумя ломтиками хлеба. Кроме того, пока мы кладем ломтик хлеба в тостер, вынимаем его оттуда или переворачиваем, его нельзя намазать маслом. Ломтик хлеба поджаривается с одной стороны за 30 с. Намазать ломтик хлеба маслом можно за 12 с.

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

Нетрудно спланировать все операции так, чтобы 3 ломтика поджаренного хлеба с маслом были готовы за 2 мин. Но 9 с можно сэкономить, если вам удастся набрести на следующую счастливую идею: ломтик хлеба можно поджарить с одной стороны не до конца, затем вынуть из тостера и дожарить позже. При таком подходе время на приготовление 3 ломтиков поджаренного хлеба с маслом удается сократить до 114 с. Но даже для тех, кому удается подобрать ключ к решению, составление оптимального графика выполненных операций остается далеко не легкой задачей. Что же касается бесчисленных проблем на составление самых экономичных последовательностей операций в различных областях человеческой деятельности, то они требуют для своего решения сложных математических методов, обращения к ЭВМ и современной теории графов.

 

Упрямые плитки

Площадка перед домом мистера Брауна выложена 40 квадратными плитками. Со временем некоторые плитки треснули, и мистер Браун решил покрыть площадку заново.

Он отправился в магазин и выбрал новые плитки, которые имели форму прямоугольников, составленных из двух квадратов размером в старую плитку.

Владелец магазина. Сколько вам нужно плиток, мистер Браун?

Мистер Браун. Мне нужно покрыть 40 квадратов. Думаю, что 20 плиток будет достаточно.

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

Бетси. Что случилось, папа? Чем ты так озабочен?

М-р Браун. Никак не могу уложить эти проклятые плитки! Как ни бьюсь, два квадрата остаются непокрытыми. С ума можно сойти!

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

Бетси. Есть идея! Я поняла, почему у тебя ничего не получается, папа! Все дело в том, что каждая новая плитка должна накрывать один белый и один черный квадрат.

Какое отношение это имеет к делу? Что Бетси имеет в виду?

На плане площадки 21 черный квадрат и 19 белых квадратов. Следовательно, после того, как уложено 19 новых плиток, 2 черных квадрата неизменно остаются непокрытыми, и покрыть их одной новой плиткой невозможно. Единственный способ выйти из затруднения — расколоть новую плитку на два квадрата.

Проверка на четность

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

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

Проверка на четность в самых различных вариантах лежит в основе доказательств многих теорем «несуществования» в математике. Кто не помнит, например, знаменитое доказательство иррациональности числа √2, предложенное Евклидом. Иррациональность √2 Евклид доказывает от противного, то есть сначала предполагает, что число √2 рациональное и его можно представить в виде несократимой дроби с целым числителем и знаменателем. Числитель и знаменатель этой дроби не могут быть оба четными, так как тогда дробь не была бы несократимой. Следовательно, либо они оба нечетны, либо один из них четен, а другой нечетен. Затем Евклид доказывает, что и в том, и в другом случае дробь, которая была бы равна √2, не существует. Иначе говоря, числитель и знаменатель дроби, которая была бы равна √2, не могли бы быть ни одинаковой, ни различной четности. Но все дроби подразделяются на два непересекающихся класса: к одному относятся дроби с числителем и знаменателем одинаковой четности, к другому принадлежат дроби с числителем и знаменателем различной четности. Следовательно, число √2 непредставимо в виде дроби с целым числителем и знаменателем, то есть иррационально.

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

В рассмотренной нами задаче площадку перед домом можно рассматривать как прямоугольник размером 6×7 единиц с двумя недостающими клетками одного цвета. Если из прямоугольника вырезать 2 клетки одного цвета, то ясно, что покрыть 20 костями домино 40 остальных клеток невозможно. С исходной задачей тесно связан следующий ее интересный вариант: всегда ли 20 костями домино можно покрыть прямоугольник размером 6×7 единиц, из которого вырезаны 2 клетки разного цвета? Проверка на четность не позволяет доказать неразрешимость новой задачи, но это отнюдь не означает, будто бренные останки прямоугольника всегда можно покрыть 20 костями домино. От перебора всех фигур, возникающих при удалении из прямоугольника размером 6×7 единиц двух клеток разного цвета, следует заранее отказаться, так как их слишком много, что затрудняет анализ задачи. Не существует ли простое доказательство разрешимости задачи, позволяющее разом охватить все прямоугольники размером 6×7 с двумя недостающими клетками разного цвета?

Такое доказательство, простое и изящное, действительно существует. Идею его предложил Ральф Гомори. Оно также использует проверку на четность. Предположим, что прямоугольник размером 6×7 целиком заполнен замкнутой дорожкой шириной в 1 клетку (рис. 4). Если удалить 2 клетки разного цвета, то, где бы они ни были расположены в прямоугольнике, замкнутая дорожка распадется на две части, каждая из которых состоит из четного числа клеток, цвета которых чередуются. Ясно, что каждый такой отрезок дорожки можно выложить костями домино. Следовательно, задача всегда допускает решение. Может быть вам захочется испытать свои силы и, применить остроумную идею Гомори к доказательству разрешимости аналогичных задач для прямоугольников других размеров и форм, из которых вырезано более двух клеток.

Теория «покрытия» — обширный раздел комбинаторной геометрии, интерес к которому все возрастает. Области, которые требуется покрыть, могут быть любой формы, конечными или бесконечными. Форма фигур, которыми требуется покрыть заданную фигуру, варьируется от задачи к задаче. Иногда требуется покрытие не конгруэнтными фигурами, а фигурами нескольких различных форм. Доказательство несуществования решения таких задач нередко удается получить, раскрасив клетки покрываемой фигуры специальным образом в несколько цветов.

Трехмерным аналогом домино служит кирпич размером 1×2×4 единиц. Такими кирпичами нетрудно заполнить ящик размером 4×4×4 единиц (заполнение пространственных тел принято называть упаковкой). Можно ли заполнить кирпичами ящик размером 6×6×6 единиц? Решение этой задачи аналогично решению задачи о покрытии площадки перед домом мистера Брауна. Представим себе, что ящик разделен на 27 кубиков размером 2×2×2 единиц. Раскрасим кубики в шахматном порядке в черный и белый цвет («шахматная доска» при этом получится не обычная, а трехмерная). Подсчитав, сколько черных и белых кубиков вмещает ящик, мы обнаружим, что кубиков одного цвета на 8 больше, чем кубиков другого.

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

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

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

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

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

Фокус можно показывать и по-другому. Пусть ваш помощник закроет рукой не одну, а две монеты. Вы сможете безошибочно сказать, лежат ли они обе вверх гербом или «решкой», или же одна монета лежит гербом вверх, а другая — гербом вниз. Аналогичные проверки на четность лежат в основе многих хитроумных карточных фокусов.

 

Проф. Квиббл и его домашние животные

Перед вами снова проф. Квиббл.

Проф. Квиббл. У меня есть для вас новая головоломка. Сколько у меня домашних животных, если все они, кроме двух, собаки, все оии, кроме двух, кошки и все они, кроме двух, попугаи?

Ну как, решили?

У проф. Квиббла всего 3 домашних животных: собака, кошка и попугай. Все они, кроме двух, собаки, все они, кроме двух, кошки, и все они, кроме двух, попугаи.

Один за «всех» и «все» за одного

Эту задачу-головоломку, кажущуюся на первый взгляд неприступной, легко решить «в уме», если понять, что слово «все» может относиться и к одному-единственному животному. Требуемое решение мы получаем в простейшем случае, когда имеется 1 собака, 1 кошка и 1 попугай. Однако решение задачи полезно представить в алгебраическом виде.

Пусть x — число собак, y — число кошек, z — число попугаев, а n — общее число животных. Тогда условия задачи позволяют записать следующую систему из 4 уравнений:

n = x + 2

n = y + 2

n = z + 2

n = x + y + z

Решить ее можно многими стандартными способами. Из первых трех уравнений видно, что x = y = z. Так как n = x + 2 и n = Зx (из последнего уравнения), то x + 2 = 3x, откуда x = 1, и мы получаем полный ответ задачи: x = y = z = 1.

Поскольку x, y и z в таких задачах принимают, как правило, целые положительные значения (кто станет держать у себя треть кошки или четверть попугая?), то задачу о домашних животных проф. Квиббла можно отнести к так называемым диофантовым задачам. Так принято называть задачи, сводящиеся к решению алгебраических уравнений в целых числах. Иногда диофантовы уравнения не имеют решений или допускают только одно решение. Существуют также диофантовы уравнения, имеющие более одного решения и даже бесконечно много решений. Вот, например, еще одна несколько более трудная диофантова задача о трех видах домашних животных, также сводящаяся к решению системы линейных уравнений.

Корова стоит 10 долларов, свинья — 3 доллара, а овца — 50 центов. Фермер купил по крайней мере 1 корову, 1 свинью и 1 овцу, израсходовав на покупку всего 100 долларов. Сколько и каких животных он купил?

Пусть x — число коров, y — число свиней и z — число овец. Тогда условия задачи можно записать в виде двух уравнений:

10x + 3y + z/2 = 100,

x + y + z = 100.

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

19x + 5y = 100.

Какие целочисленные значения могут принимать x и y? Один из способов получить ответ на этот вопрос состоит в том, чтобы преобразовать уравнение, оставив в левой части только член с наименьшим коэффициентом при неизвестном: 5y = 100 − 19x. Разделив обе части уравнения на 5, получим у = (100 − 19x)/5. Разделим теперь 100 и 19x на 5, выделив заведомо целую часть и дробный остаток (если он существует):

y = 20 − Зx − 4x/5.

Ясно, что выражение 4x/5 должно принимать целочисленные значения. Следовательно, x должен быть кратен 5. Наименьшее кратное 5 равно 5, что соответствует y = 1 и (если вернуться к любому из двух исходных уравнений) z = 94. При остальных значениях x, кратных 5 (и больших 5), у принимает отрицательные значения. Значит, наша задача допускает единственное решение: фермер купил 5 коров, 1 свинью и 94 овцы.

Варьируя цены на коров, свиней и овец, можно самостоятельно открыть многие премудрости элементарной теории диофантовых уравнений. Предположим, например, что коровы продаются по 4 доллара, свиньи — по 2 доллара и овцы — по ⅓ доллара за голову. Сколько животных купил фермер на 100 долларов, если известно, что он купил по крайней мере 1 корову, 1 свинью и 1 овцу? Эта задача допускает 3 решения. А что можно сказать, если корова стоит 5 долларов, свинья — 2 доллара и овца — 50 центов? Оказывается, что в этом случае решения не существует.

Теория диофантовых уравнений представляет собой обширный раздел теории чисел, имеющий бесчисленные применения во многих областях науки и техники. Одна из знаменитых задач на решение диофантовых уравнений известна под названием великой (или последней) теоремы Ферма. В ней требуется найти при любых целых положительных n > 2 решение в целых числах уравнения x n + y n = z n (при n = 2 эти решения называются пифагоровыми тройками; существует бесконечно много пифагоровых троек, начиная с 3² + 4² = 5²). Великая теорема Ферма — наиболее известная из нерешенных проблем теории чисел. До сих пор никому еще не удалось ни найти хотя бы одно решение уравнения x n + y n = z n в целых числах (при n > 2), ни доказать, что такого решения не существует.

 

Небольшой переполох в аптеке

Как-то раз в аптеку доставили 10 флаконов лекарства. В каждом флаконе по 1000 пилюль. Не успел провизор мистер Уайт расставить флаконы на полке, как почтальон принес телеграмму.

Мистер Уайт читает телеграмму управляющей аптекой мисс Блек.

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

Мистер Уайт встревожился.

Мистер Уайт. Нечего сказать, повезло! Теперь мне придется брать по пилюле из каждого флакона и взвешивать. Веселенькое занятие!

Тяжело вздохнув, мистер Уайт хотел было приступить к неожиданно свалившейся на него работе, как мисс Блек остановила его.

Мисс Блек. Минуточку! Взвешивать 10 раз совсем не нужно! Достаточно произвести 1 взвешивание.

Каким образом при помощи 1 взвешивания можно установить, в каком флаконе пилюли содержат повышенную дозу лекарства?

Идея мисс Блек состояла в том, чтобы взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 3 пилюли из третьего флакона…, 10 пилюль из десятого флакона…

…положить 55 отобранных пилюль на одну чашу весов и взвесить их. Предположим, что пилюли весили бы 5510 мг, или на 10 мг больше, чем следует. Тогда мисс Блек заключила бы, что среди отобранных пилюль имеется 1 пилюля с повышенной дозой лекарства, а ровно 1 пилюля была извлечена из первого флакона.

Если бы вес 55 пилюль оказался на 20 мг больше нормы, то это означало бы, что среди отобранных пилюль имеются 2 пилюли с повышенной дозой лекарства. Их можно было извлечь только из второго флакона. Так мисс Блек сумела понизить число взвешиваний до 1. Меньше не бывает!

 

Большой переполох в аптеке

Через 6 месяцев в аптеку доставили еще 10 флаконов того же лекарства. И на этот раз не успели распаковать коробку с флаконами, как почтальон принес телеграмму с извещением о том, что на этот раз фармацевт допустил более серьезную ошибку.

В посылке могло оказаться от 1 до 10 флаконов с пилюлями, каждая из которых на 10 мг тяжелее нормы. Мистер Уайт был вне себя от ярости.

Мистер Уайт. Что делать, мисс Блек? Ваш метод, который позволил нам так блестяще выйти из затруднения в прошлый раз, неприменим!

Мисс Блек задумалась.

Мисс Блек. Вы правы, мистер Уайт. Но если слегка модифицировать мой метод, то при помощи 1 взвешивания и на этот раз можно определить, в каких флаконах пилюли содержат повышенную дозу лекарства.

Что имела в виду мисс Блек?

Как определить непригодные пилюли?

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

Чтобы решить вторую задачу, необходимо воспользоваться последовательностью, которая бы сопоставляла каждому флакону отличный от других номер и обладала бы еще одним дополнительным свойством: сумма членов любой ее подпоследовательности должна быть отличной от суммы членов любой другой ее подпоследовательности. Существуют ли такие последовательности? Да, существуют. Примером может служить хотя бы геометрическая прогрессия со знаменателем 2 и первым членом 1: 1, 2, 4, 8, 16… Все члены этой последовательности — степени числа 2, причем показатель возрастает от 0 с единичным шагом. Именно эта последовательность лежит в основе двоичной системы счисления.

Решение задачи состоит в том, чтобы, выстроив флаконы в ряд, взять 1 пилюлю из первого флакона, 2 пилюли из второго флакона, 4 пилюли из третьего флакона и т. д., затем собрать все отобранные пилюли и взвесить. Предположим, что пилюли оказались на 270 мг тяжелее, чем нужно. Так как каждая пилюля с повышенной дозой лекарства тяжелее нормальной на 10 мг, то, разделив 270 на 10, мы получим 27 — число более тяжелых пилюль.

Запишем число 27 в двоичной системе: 11011. Двоичные разряды, в которых стоят единицы, говорят нам, какие степени числа 2 в сумме дают двоичное число 11011 (или десятичное число 27): 1, 2, 8 и 16. Единицы стоят в первом, втором, четвертом и пятом двоичных разрядах. Следовательно, непригодные пилюли с повышенным содержанием лекарства находятся в первом, втором, четвертом и пятом флаконах.

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

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

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

Секрет фокуса прост. Вы заранее кладете в карман туз, двойку, четверку и восьмерку. Определить на глаз недостачу четырех карт в колоде невозможно, и ваши зрители будут пребывать в уверенности, что вы попросили перетасовать полную колоду. Перетасованную колоду вы подкладываете под четыре карты, уже лежащие в кармане. После того как число названо, вы мысленно представляете его в виде суммы степеней числа 2 (например, если названо число 10, то вы мысленно разлагаете его в сумму 8 + 2=10) и, сунув руку в карман, достаете двойку и восьмерку.

На том же двоичном принципе построены и карточки «для чтения мыслей на расстоянии». На рис. 1 из гл. 3 показаны 6 карт, позволяющие безошибочно отгадывать любое задуманное число от 1 до 63. Попросите кого-нибудь, задумав любое число в этом диапазоне (например, свой возраст), отобрать и вручить вам все карточки, на которых оно встречается, и вы немедленно назовете задуманное число. Секрет этого фокуса также прост: вы просто суммируете степени числа 2, стоящие в левом верхнем углу каждой таблицы. Например, если были отобраны и вручены вам таблицы C и F, то вы суммируете числа 4 и 32 и узнаете, что было задумано число 36.

По какому принципу выбраны числа на каждой карточке? Каждое число, имеющее в двоичной записи единицу в первом разряде справа, заносится в таблицу A. Следовательно, в эту таблицу вписаны все нечетные числа от 1 до 63. В карточку B заносятся все числа, имеющие в двоичной записи единицу во втором разряде справа, в карточку C — все числа, имеющие единицу в третьем разряде справа и т. д. Заметим, что число 63 в двоичной системе записывается как 111111, то есть имеет единицы во всех шести разрядах, и поэтому встречается на всех шести карточках.

Иногда фокусники придают этому фокусу налет таинственности, окрашивая карточки в различные цвета и запоминая, какой цвет соответствует той или иной степени числа 2. Пусть, например, красная карточка означает 1, оранжевая — 2, желтая — 4, зеленая — 8, голубая — 16 и фиолетовая — 32 (мы выбрали 6 цветов радуги по порядку, пропустив синий). Фокусник становится в дальнем конце комнаты и просит кого-нибудь из зрителей отложить в сторону карточки, на которых встречается задуманное число. По цвету отложенных карточек фокусник без промедления может назвать задуманное число.

 

Распиленный браслет

Однажды юная Глория из Арканзаса отправилась в Калифорнию. Ей необходимо было снять на неделю номер в гостинице.

Портье в гостинице встретил ее весьма нелюбезно.

Портье. Могу предложить только номер за 20 долларов в сутки. Плата наличными.

Глория. Простите, сэр, у меня нет при себе денег. Есть только этот золотой браслет. Каждое из его 7 звеньев стоит дороже 20 долларов.

Портье. Так и быть, давайте сюда ваш браслет.

Глория. Не торопитесь. Я попрошу какого-нибудь ювелира распилить браслет и буду отдавать вам по 1 звену в день, а к концу недели, когда мне пришлют из дому деньги, отдам браслет в починку.

После долгих споров портье согласился. Но перед Глорией встала задача: как распилить браслет?

Глория. Торопиться не следует. Ведь ювелир потребует с меня плату за каждое распиленное и вновь запаянное звено браслета.

Поразмыслив, Глория поняла, что ей вовсе не нужно распиливать все звенья, поскольку отдельные части браслета можно комбинировать так, чтобы число оставшихся у портье звеньев каждый раз соответствовало плате за номер. Сколько звеньев вы бы приказали распилить на месте Глории?

Достаточно распилить лишь одно-единственное звено: третье с любого конца цепи. Браслет распадется на 3 части длиной в 1 звено, 2 звена и 4 звена. Отдавая их в необходимой комбинации портье и получая предыдущие, Глория сможет оставлять у портье каждый день на 1 звено больше, чем накануне.

Решающее звено

Чтобы решить эту задачу, необходимо принять во внимание два соображения. Во-первых, понять, что наименьший набор отрезков золотой цепочки, позволяющий оставить у портье любое число звеньев от 1 до 7, состоит из 3 отрезков длиной в 1, 2 и 4 звена. Как мы уже знаем из решения предыдущей задачи, эти числа — не что иное, как последовательные степени числа 2, положенные в основу двоичной системы счисления.

Во-вторых, необходимо понять, что разделить браслет на части длиной в 1, 2 и 4 звена можно распилив одно-единственное звено.

Задача допускает обобщение на случай, когда браслет или цепочка состоят более чем из 7 звеньев. Например, пусть у Глории имеется с собой золотая цепочка из 67 звеньев, которую необходимо распилить с той же целью, что и злосчастный браслет, — для уплаты за проживание в гостиничном номере от 1 до 67 суток по 1 звену за сутки. Оказывается, что в этом случае достаточно распилить лишь 3 звена. Вы знаете, какие именно? Может быть, вы можете предложить общий метод решения задачи, позволяющий распиливать минимальное число звеньев цепи произвольной длины?

Интересный вариант этой задачи возникает в том случае, если первоначально концы n-звенной цепочки соединены так, что цепочка превратилась в замкнутую петлю. Например, предположим, что у Глории есть золотая цепочка из 79 звеньев. Сколько звеньев необходимо распилить, чтобы Глория могла оплатить от 1 до 79 суток пребывания в гостинице из расчета по 1 звену за сутки?