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

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 плиток можно сложить квадрат, показанный на рисунке, в точном соответствии с заданными условиями.

448. Если вы попытались, как это часто делают, сначала расставить по местам все 6 экземпляров одной буквы, затем все 6 экземпляров другой и т. д., то обнаружите, что, расположив по 6 экземпляров каждой из четырех букв, можно еще разместить только по 2 экземпляра оставшихся двух букв, так что получится диаграмма, изображенная слева. Секрет заключается в том, чтобы заполнить клетки 6 экземплярами каждой из первых двух букв и пятью экземплярами каждой из остальных четырех букв; при этом получится вторая диаграмма, изображенная справа, только с четырьмя свободными клеточками.