Головоломка с девятью точками — математическая головоломка , задача которой состоит в том, чтобы соединить ручкой девять расположенных в квадрате точек четырьмя (или менее) прямыми линиями, не отрывая ручки.
На протяжении многих лет эта головоломка появлялась под разными названиями.
В 1867 году во французском шахматном журнале Le Sphinx появился интеллектуальный предшественник головоломки из девяти точек, приписываемый Сэму Лойду . [1] [2] Указанная шахматная головоломка соответствует «головоломке из 64 точек», т. е. обозначению всех точек квадратной решетки 8 на 8 , с дополнительным ограничением. [a]
В 1907 году головоломка из девяти точек появилась в интервью с Сэмом Лойдом в журнале The Strand Magazine : [4] [2]
В том же году головоломка появилась в книге головоломок А. Сирила Пирсона. Там она была названа очаровательной головоломкой и включала девять точек. [5] [2]
Обе версии головоломки впоследствии появились в газетах. По крайней мере с 1908 года версия Лойда с яйцом использовалась в качестве рекламы Elgin Creamery Co в Вашингтоне, округ Колумбия. , переименованной в The Elgin Creamery Egg Puzzle . [6] По крайней мере с 1910 года версия Пирсона с «девятью точками» появилась в разделах головоломок. [7] [8] [9]
В 1914 году «Энциклопедия головоломок » Сэма Лойда была опубликована посмертно его сыном (также Сэмом Лойдом). [10] В ней головоломка объясняется следующим образом: [11] [2]
Название головоломки, данное Сэмом Лойдом, является намеком на историю о Яйце Колумба . [12]
Можно разметить девять точек четырьмя линиями. [13] Чтобы сделать это, нужно выйти за пределы квадратной области, определяемой самими девятью точками. Фраза «думать вне коробки », используемая консультантами по управлению в 1970-х и 1980-х годах, является перефразированием стратегии решения. По словам Дэниела Киза, головоломка кажется сложной, потому что мы обычно представляем себе границу вокруг края массива точек. [14]
Сложность, присущая этой головоломке, изучалась в экспериментальной психологии . [15] [16]
Различные опубликованные решения нарушают неявные правила головоломки, чтобы достичь решения даже с меньшим количеством линий, чем четыре. Например, если предполагается, что точки имеют некоторый конечный размер, а не являются бесконечно малыми математическими точками сетки, то их можно соединить всего тремя слегка наклонными линиями. Или, если линия может быть произвольной толщины, то одна линия может покрыть все точки. [17]
Другой способ использования только одной линии заключается в сворачивании бумаги в трехмерный цилиндр , так что точки выровняются вдоль одной спирали (которая, как геодезическая цилиндра, может считаться в некотором смысле прямой линией). Таким образом, можно провести одну линию, соединяющую все девять точек, которая будет выглядеть как три параллельные линии на бумаге, если ее развернуть. [18] Также можно сложить бумагу в плоскую форму или разрезать ее на части и переставить их таким образом, чтобы девять точек лежали на одной линии в плоскости (см. теорему о сгибании и разрезании ). [17]
Вместо квадратной решетки 3 на 3 были предложены обобщения в виде наименьшего количества линий, необходимых для квадратной решетки n на n . Или, в математической терминологии, минимально- сегментный уникурсальный полигональный путь, покрывающий массив точек n × n .
Различные подобные расширения были сформулированы как головоломки Дьюдени и Лойдом с различными дополнительными ограничениями. [20]
В 1955 году Мюррей С. Кламкин показал, что если n > 2 , то достаточно 2 n − 2 отрезков прямой , и предположил, что это также необходимо. [21] [20] В 1956 году гипотеза была доказана Джоном Селфриджем . [22] [20] [2]
В 1970 году Соломон В. Голомб и Джон Селфридж показали, что уникурсальный многоугольный путь из 2 n − 2 сегментов существует на массиве n × n для всех n > 3 с дополнительным ограничением, что путь должен быть замкнутым , т. е. он начинается и заканчивается в одной и той же точке. [20] Более того, дополнительное ограничение, что замкнутый путь остается внутри выпуклой оболочки массива точек, может быть выполнено для всех n > 5. Наконец, доказаны различные результаты для массива точек a × b . [3]
Премия «Девять точек», названная в честь головоломки, [23] является конкурсной премией за «творческое мышление, которое решает современные общественные проблемы». [24] Она спонсируется Фондом премии Кадаса и поддерживается Издательством Кембриджского университета и Центром исследований в области искусств, социальных и гуманитарных наук Кембриджского университета . [ 25]
Placer la Dame ot l'on voudra, lui faire parcourir par des Marches suivies et régulières toutes les Cases de I'échiquier, et la ramener au quatorzième coup à son point de départ. Поместите ферзя куда хотите, заставьте его пройти регулярными шагами все клетки шахматной доски и на четырнадцатом ходу верните его в исходную точку.