Пятьсот двадцать головоломок - Генри Дьюдени

432. Две! Требуются четыре цвета. Если у мальчика в ящике имеется лишь три краски (красная, голубая и желтая), то он может получить оранжевый, зеленый и фиолетовый цвета, смешивая их между собой. Но он не может получить четыре цвета менее, чем из трех красок. Следовательно, у него в ящике две краски («не хватает одной краски»). «Цветом» считается красный, оранжевый, желтый, зеленый, голубой или фиолетовый. Различные оттенки, вроде голубовато-зеленого или желто-зеленого, не допускаются.

433. Умножьте 2 столько раз на себя, сколько всего картин, и вычтите 1. Так, 2 в десятой степени равно 1024. Вычитая 1, мы получаем 1023 — правильный ответ. Предположим, что у нас только три картины. Тогда одну из них можно выбрать тремя способами, две — тоже тремя способами и три — одним, что в сумме дает 7 способов. Но 7 как раз и равняется 23 - 1[43].

434. Всего имеется 39 147 416 разных способов. Прибавьте 3 к числу членов (что даст 618) и вычтите 1 из числа партий (что даст 3). Тогда ответом будет число способов, которыми можно выбрать 3 предмета из 618, то есть

Общее решение таково. Пусть p — число партий, а m — число членов парламента. Число способов равно числу сочетаний из m + p - 1 объектов по p - 1.

435. Если нет никаких ограничений, то 10 человек могут разместиться на прямой 10! = 3 628 800 способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек одной национальности, заключенных в скобки, как единое целое.

1. Тогда (Ан, Аи) (Ш, Ш) (У, У) Ф Ит Ис Ам можно переставить 7! × 23 = 40 320 способами. Помните, что два Ан могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для Ш и У. Отсюда и появляется 23.

2. Однако мы можем рассмотреть (Ан, Ан) (Ш, Ш) У У Ф Ит Ис Ам, где два У не объединены скобками, а «свободны». Это даст нам 8! × 22 вариантов, но мы должны исключить отсюда результат пункта 1, чтобы не сосчитать некоторые перестановки дважды. Получаем 120 960.

3. Поступим аналогичным образом с двумя «свободными» Ш. Получим 120 960.

4. Поступим так же с двумя «свободными» Ан. Получим 120 960.

5. Но мы можем рассмотреть (Ан, Ан) Ш Ш У У Ф Ит Ис Ам, где и Ш, и У «свободны». Это даст нам 9! × 2 случаев, из которых мы должны вычесть результаты пунктов 1, 2 и 3 по очевидным теперь причинам. Получим 443 520.

6. Когда в скобки заключены только Ш, вычтем результаты пунктов 1, 2 и 4. Получим 443 520.

7. Когда в скобках оставлены только У, вычтем результаты пунктов 1, 3 и 4. Получим 443 520.

Сложим результаты семи пунктов и получим при этом 1 733 760. Теперь из самого первого результата вычтем полученное число, что даст нам верный ответ, равный 1 895 040 способам.

436. Головоломку можно решить за 9 переправ следующим образом:

1) мистер и миссис Вебстер переправляются вместе;

2) миссис Вебстер возвращается;

3) переправляются мать и невестка;

4) возвращается мистер Вебстер;

5) переправляются тесть и сын;

6) возвращается невестка;

7) переправляются мистер Вебстер с невесткой;

8) возвращается мистер Вебстер;

9) мистер и миссис Вебстер переправляются вместе.

437. Обозначим трех миссионеров через М м м, а трех каннибалов через К к к; прописными буквами обозначены миссионер и каннибал, умеющие грести. Тогда переправляются К к; К возвращается на лодке; переправляются К к; К возвращается; переправляются М м; возвращаются М к; переправляются М К; возвращаются М к; переправляются М м; возвращается К; переправляются К к; К возвращается; переправляются К к; при этом все переправляются через реку, не нарушая заданных условий.

[Задачи о переправах через реку этого и предыдущего типа решаются с помощью простого метода из теории графов. См. гл. 35 книги М. Гарднера «Математические досуги» (М., изд-во «Мир», 1972). — М. Г.]

438. Двое детей гребут к другому берегу. Один из них вылезает, а другой возвращается назад. Один солдат переправляется, вылезает, а мальчик возвращается назад. Таким образом, чтобы переправить на другой берег одного взрослого, лодка должна 4 раза проплыть от берега до берега. Поэтому ей пришлось сделать 4 × 358 = 1432 рейса, чтобы переправить офицера и 357 солдат, причем лодка в конце концов снова оказалась у детей.

439. Можно составить следующую таблицу:

440. Из таблицы можно сразу определить, что Англия победила Ирландию и сыграла вничью с Уэльсом. Поскольку А сыграла в этих матчах с общим счетом 2 : 0, то она должна была победить со счетом 2 : 0, а вничью сыграть со счетом 0 : 0. Таким образом, нам все известно про А и остается только определить результаты трех матчей: У с И, Ш с И и Ш с У. Шотландия пропустила только 1 гол от У или И. И забила только 1 гол в ворота У или Ш. Допустим, что в ворота Ш. Тогда У не забил ни одного гола в ворота Ш. Но У всего забил 3 гола; следовательно, все они были забиты в ворота И. Получается, что в ворота И было забито 6 голов: 2 — А, 3 — У (если принять, что И забила гол в ворота Ш) и оставшийся гол — Ш. Но поскольку мы приняли, что И забила 1 гол в ворота Ш, матч между этими командами должен был закончиться вничью. Однако из таблицы видно, что в этом матче выиграла Ш и, следовательно, И не могла забить гол в ворота Ш. Таким образом, гол в ворота Ш забил У. А поскольку У всего забил 3 гола, то остальные 2 были забиты в ворота И, которая свой единственный гол забила в ворота У. Окончательно мы получаем, что Ш выиграла у У со счетом 2 : 1, у И со счетом 2 : 0, а У выиграл у И со счетом 2 : 1.

441. Пусть 8 делений разбивают 33-сантиметровую линейку на 9 частей длиной 1, 3, 1, 9, 2, 7, 2, 6, 2 см. Тогда с их помощью можно измерить любое целое число сантиметров от 1 до 33 см. Разумеется, сами деления находятся на расстояниях 1, 4, 5, 14, 16, 23, 25 и 31 см от одного из концов линейки. Другим решением будет 1, 1, 1, 1, 6. 6, 6, 6, 5 см.

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

[Хотя общего правила не найдено до сих пор, все же с того момента, как Дьюдени поставил эту задачу, отмечен существенный прогресс. Обнаружено, что восьми делений достаточно также и для линейки в 36 см. — М. Г.]

442. Если расположить коттеджи по кругу через промежутки 1, 1, 4, 4, 3, 14 км, то для любого целого числа километров от 1 до 26 включительно найдутся два коттеджа, отстоящие друг от друга на такое расстояние.

[Эта задача, очевидно, представляет собой разновидность предыдущей. Как и ранее, Дьюдени мог бы увеличить длину «линейки» (в нашем случае — дороги), не меняя остальных условий задачи. Оказывается, что 6 коттеджей можно расположить на круглой дороге в 31 км таким образом, чтобы любое целое расстояние от 1 до 30 км совпадало с расстоянием по кругу между некоторой парой домов. Нетрудно заметить, что для п домов максимальнее число различных способов измерения расстояний между ними равно n(n - 1). Для n = 6 мы получаем 30; следовательно, в этом случае можно расположить 6 домов на дороге в 31 км так, чтобы ни одно из расстояний между парами домов не повторялось. Точно так же оптимальные решения можно получить и в случае n = 1, 2, 3, 4 или 5. См. решение задачи Е176 Михаелем Гольдбергом, приведенное в журнале American Mathematical Monthly, September 1966, p. 786. — M. Г.]

443. Существует 9 основных решений, представленных на рисунке. Решение A — это то самое решение, которое давалось при формулировке задачи. Из данных 9 решений D, E и J порождают по 8 решений каждое с помощью поворотов и отражений, как объяснялось ранее, а остальные дают только по 4 решения каждое. Следовательно, всего существует 48 различных решений данной головоломки.

Читателю, быть может, будет небезынтересно узнать, что на шахматной доске 8 × 8 пять фишек можно расположить вдоль прямой при тех же самых условиях четырьмя основными способами, порождающими 20 различных решений.

444. Три мухи переменили позицию, как показано стрелками на рисунке, и при этом никакие две мухи не оказались на одной прямой.

445. Если бы у Пилкинса было 11 клерков, а у Рэдсона 12, то они могли бы сесть за стол 165 и 495 способами соответственно, что как раз и являлось бы решением задачи. Однако нам известно, что у той и другой фирмы клерков было поровну. Следовательно, ответом будет 15 клерков, садившихся по трое в течение 455 дней, и 15 клерков, садившихся по четыре в течение 1365 дней.

446. В первом случае существует 88 200 способов. Есть один простой метод, с помощью которого можно получить ответ, но объяснение его потребовало бы слишком много места. Во втором случае ответ уменьшается до 6300 способов.

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