Есть идея!

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

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

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

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

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

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

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

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

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

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

По крайней мере 2 часа в день мне необходимы для отдыха, что составляет 2 x 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 равные части и выполнение второй половины отложить (как в задаче с поджариванием ромштексов) до завершения другой работы, то на выполнение намеченной программы у супругов Джонс уйдет лишь 3/4 времени (по сравнению с первым вариантом), или 45 мин.

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

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