Загадка упаковки Хоффмана

Пазл-упаковка Хоффмана в разобранном виде

Пазл-головоломка Хоффмана — сборочная головоломка, названная в честь Дина Г. Хоффмана , описавшего ее в 1978 году. ^{[ 1 ]} Головоломка состоит из 27 одинаковых прямоугольных кубов , каждый из которых имеет три разные длины. Его цель — собрать их все так, чтобы они поместились в куб, длина ребра которого равна сумме трех длин. ^{[ 2 ]}^{[ 3 ]}

Хоффман (1981) пишет, что первым человеком, решившим головоломку, был Дэвид А. Кларнер , и что типичное время решения может варьироваться от 20 минут до нескольких часов. ^{[ 2 ]}

Строительство

Сама головоломка состоит всего из 27 одинаковых прямоугольных блоков кубовидной формы, хотя физические реализации головоломки также обычно включают кубическую коробку, в которую помещаются блоки. Если три длины ребер блока равны $x$ , $y$ и $z$ , то длина ребра куба должна быть $x + y + z$ . Хотя головоломку можно построить с любыми тремя разными длинами ребер, сложнее всего, когда три длины ребер блоков настолько близки друг к другу, что $x + y + z < 4 min(x, y, z)$ , поскольку это предотвращает альтернативу. решения, в которых четыре блока минимальной ширины упакованы рядом друг с другом. Кроме того, если три длины образуют арифметическую прогрессию, это может еще больше запутать ситуацию, поскольку в этом случае размещение трех блоков средней ширины рядом друг с другом дает строку правильной общей ширины, но такую, которая не может привести к правильному решению задачи. целая головоломка. ^{[ 2 ]}

Математический анализ

В каждом правильном решении головоломки блоки располагаются в сетке блоков размером примерно $3 \times 3 \times 3$ , причем все стороны блоков параллельны сторонам внешнего куба, а по одному блоку каждой ширины вдоль каждой оси, параллельной линии. из трех блоков. Считая отражения и вращения одним и тем же решением, головоломка имеет 21 комбинаторно различное решение. ^{[ 2 ]}^{[ 4 ]}

Общий объём частей, $27 xyz$ , меньше объёма $(x + y + z) 3$ куба, в который они упаковываются. Если взять кубический корень из обоих объемов и разделить на три, то число, полученное таким образом из общего объема кусков, будет средним геометрическим x $,$ y $и$ z $,$ а число, полученное таким же образом из объем куба есть их среднее арифметическое . Тот факт, что куски имеют меньший общий объем, чем куб, следует из неравенства средних арифметических и геометрических . ^{[ 2 ]}^{[ 3 ]}

Таблица решений

Здесь сведено в таблицу 21 различное решение, как описано в ссылках, цитированных выше. ^{[ 2 ]}^{[ 4 ]}.

Все поля ниже вводятся в формате (длина восток-запад) x (длина север-юг) x (длина вверх-вниз) , обозначая размер каждого поля с размерами A , B и C , где A < B < С. (В приведенном выше примере A = 4, B = 5 и C = 6).

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

Решение	Нижний слой	Средний слой	Верхний слой
Решение 01	CxBxA AxCxB BxAxC BxCxA CxAxB AxBxC AxCxB BxAxC CxBxA	CxAxB AxBxC BxCxA AxBxC BxAxC AxCxB BxCxA CxBxA CxAxB	BxAxC CxBxA AxCxB CxAxB BxCxA CxBxA AxBxC AxCxB BxAxC
Решение 02	CxBxA AxCxB BxAxC BxCxA CxAxB AxBxC AxCxB BxAxC CxBxA	CxAxB AxBxC AxCxB AxBxC BxAxC BxCxA BxCxA CxBxA CxAxB	BxAxC BxCxA CxBxA CxAxB CxBxA AxCxB AxBxC AxCxB BxAxC
Решение 03	CxBxA AxCxB BxAxC BxCxA CxAxB AxBxC AxCxB BxAxC CxBxA	AxBxC BxAxC BxCxA CxAxB AxBxC AxCxB BxCxA CxBxA CxAxB	CxAxB CxBxA AxCxB BxAxC BxCxA CxBxA AxBxC AxCxB BxAxC
Решение 04	CxBxA AxCxB BxAxC BxCxA CxAxB AxBxC AxCxB BxAxC CxBxA	AxBxC BxAxC AxCxB CxAxB AxBxC BxCxA BxCxA CxBxA CxAxB	CxAxB BxCxA CxBxA BxAxC CxBxA AxCxB AxBxC AxCxB BxAxC
Решение 05	CxBxA AxCxB CxAxB BxCxA CxBxA BxAxC AxCxB BxAxC AxBxC	AxBxC BxCxA BxAxC BxAxC AxCxB CxBxA CxBxA CxAxB AxCxB	AxCxB BxAxC CxBxA CxAxB AxBxC AxCxB BxAxC CxBxA BxCxA
Решение 06	CxBxA AxCxB CxAxB BxCxA CxBxA BxAxC AxCxB BxAxC AxBxC	AxBxC BxCxA BxAxC CxAxB AxCxB CxBxA BxAxC CxBxA AxCxB	AxCxB BxAxC CxBxA BxAxC AxBxC AxCxB CxBxA CxAxB BxCxA
Решение 07	CxBxA AxCxB BxAxC BxCxA CxBxA CxAxB AxCxB BxAxC AxBxC	CxAxB CxBxA BxCxA BxAxC AxCxB AxBxC AxBxC BxCxA CxAxB	AxBxC BxAxC AxCxB CxAxB AxBxC BxCxA BxCxA CxAxB CxBxA
Решение 08	CxBxA AxCxB BxAxC BxCxA CxBxA CxAxB AxCxB BxAxC AxBxC	BxAxC CxBxA BxCxA CxAxB AxCxB AxBxC AxBxC BxCxA CxAxB	CxAxB AxBxC AxCxB AxBxC BxAxC BxCxA BxCxA CxAxB CxBxA
Решение 09	CxBxA AxCxB BxAxC BxCxA CxBxA CxAxB AxCxB BxAxC AxBxC	AxBxC BxCxA CxAxB BxAxC AxCxB AxBxC CxBxA CxAxB BxCxA	AxCxB BxAxC CxBxA CxAxB AxBxC BxCxA BxAxC CxBxA AxCxB
Решение 10	CxBxA AxCxB BxAxC BxCxA CxBxA CxAxB AxCxB BxAxC AxBxC	AxBxC BxCxA CxAxB CxAxB AxCxB AxBxC BxAxC CxBxA BxCxA	AxCxB BxAxC CxBxA BxAxC AxBxC BxCxA CxBxA CxAxB AxCxB
Решение 11	CxBxA AxCxB BxAxC BxCxA BxAxC AxBxC AxCxB CxBxA CxAxB	CxAxB AxBxC BxCxA AxBxC CxAxB AxCxB BxCxA BxAxC CxBxA	BxAxC CxBxA AxCxB CxAxB BxCxA CxBxA AxBxC AxCxB BxAxC
Решение 12	CxBxA AxCxB BxAxC BxCxA BxAxC AxBxC AxCxB CxBxA CxAxB	CxAxB AxBxC AxCxB AxBxC CxAxB BxCxA BxCxA BxAxC CxBxA	BxAxC BxCxA CxBxA CxAxB CxBxA AxCxB AxBxC AxCxB BxAxC
Решение 13	CxBxA AxCxB BxAxC BxCxA BxAxC AxBxC AxCxB CxAxB CxBxA	CxAxB AxBxC AxCxB AxBxC BxCxA CxAxB BxCxA CxBxA BxAxC	BxAxC CxBxA BxCxA CxAxB AxCxB CxBxA AxBxC BxAxC AxCxB
Решение 14	CxBxA AxCxB BxAxC BxCxA BxAxC AxBxC AxCxB CxAxB CxBxA	BxAxC AxBxC AxCxB AxCxB CxBxA CxAxB CxBxA BxCxA BxAxC	CxAxB CxBxA BxCxA BxAxC AxCxB CxBxA AxBxC BxAxC AxCxB
Решение 15	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	CxAxB AxBxC BxCxA AxBxC BxAxC AxCxB BxCxA CxBxA CxAxB	BxAxC AxCxB AxBxC CxAxB BxCxA CxBxA AxBxC CxAxB BxCxA
Решение 16	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	CxAxB AxBxC BxCxA AxBxC BxAxC AxCxB BxCxA CxAxB CxBxA	BxAxC AxCxB AxBxC CxAxB CxBxA BxCxA AxBxC BxCxA CxAxB
Решение 17	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	CxAxB AxCxB AxBxC AxBxC BxAxC BxCxA BxCxA CxAxB CxBxA	BxAxC AxBxC BxCxA CxAxB CxBxA AxCxB AxBxC BxCxA CxAxB
Решение 18	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	BxAxC AxCxB AxBxC CxAxB BxCxA CxBxA AxBxC CxAxB BxCxA	CxAxB AxBxC BxCxA AxBxC BxAxC AxCxB BxCxA CxBxA CxAxB
Решение 19	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	AxCxB BxAxC CxBxA BxAxC AxBxC BxCxA CxBxA CxAxB AxCxB	AxBxC AxCxB BxAxC CxAxB CxBxA AxCxB BxAxC BxCxA CxBxA
Решение 20	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	AxCxB BxAxC CxBxA BxAxC AxBxC AxCxB CxBxA CxAxB BxCxA	AxBxC AxCxB BxAxC CxAxB BxCxA CxBxA BxAxC CxBxA AxCxB
Решение 21	CxBxA BxCxA CxAxB BxCxA CxAxB AxBxC AxCxB AxBxC BxAxC	AxBxC AxCxB BxAxC BxAxC BxCxA CxBxA CxBxA CxAxB AxCxB	AxCxB BxAxC CxBxA CxAxB AxBxC AxCxB BxAxC CxBxA BxCxA

Высшие измерения

Двумерный аналог головоломки требует упаковать четыре одинаковых прямоугольника с длиной стороны $x$ и $y$ в квадрат с длиной стороны $x + y$ ; как видно из рисунка, это всегда возможно. В $измерениях d$ головоломка требует собрать $d д$ одинаковые блоки в гиперкуб . Согласно результату Рафаэля М. Робинсона, всякий раз, когда $d = d1 снова \times d2 эта$ для двух чисел $d1 задача$ и $d2 таких ,$ что $d1- разрешима$ и $d2 -$ мерные случаи сами по себе разрешимы. Например, согласно этому результату, оно разрешимо для размерностей 4, 6, 8, 9 и других 3-гладких чисел . Во всех измерениях неравенство средних арифметических и геометрических показывает, что объём кусков меньше объёма гиперкуба, в который их следует упаковать. Однако неизвестно, можно ли решить головоломку в пяти измерениях или в измерениях с более высокими простыми числами . ^{[ 2 ]}^{[ 5 ]}

Ссылки

^ Рауш, Джон, «Собери вместе — головоломка Хоффмана об упаковке» , Puzzle World , заархивировано из оригинала 17 ноября 2019 г. , получено 16 ноября 2019 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Хоффман, Д.Г. (1981), «Проблемы упаковки и неравенства», в Кларнере, Дэвиде А. (ред.), The Mathematical Gardner , Springer, стр. 212–225, doi : 10.1007/978-1-4684-6686-7_19
^ Jump up to: ^а ^б Альсина, Клауди; Нельсен, Роджер Б. (2015), «Проблема 3.10» , «Математическая космическая одиссея: твердотельная геометрия в 21 веке» , Dolciani Mathematical Expositions, vol. 50, Математическая ассоциация Америки, с. 63, ISBN 9780883853580
^ Jump up to: ^а ^б Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2004), Пути победы в математических играх , том. IV, А. К. Петерс, стр. 913–915.
^ фон Хольк, Николай Ингеманн (январь 2018 г.), Экспериментальный подход к проблемам упаковки (PDF) , бакалаврская диссертация под руководством Сёрена Эйлерса, Копенгагенский университет, заархивировано (PDF) из оригинала 17 ноября 2019 г. , получено 11 ноября 2019 г. -17

[rausch-1] Рауш, Джон, «Собери вместе — головоломка Хоффмана об упаковке» , Puzzle World , заархивировано из оригинала 17 ноября 2019 г. , получено 16 ноября 2019 г.

[hoffman-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Хоффман, Д.Г. (1981), «Проблемы упаковки и неравенства», в Кларнере, Дэвиде А. (ред.), The Mathematical Gardner , Springer, стр. 212–225, doi : 10.1007/978-1-4684-6686-7_19

[space-3] Jump up to: ^а ^б Альсина, Клауди; Нельсен, Роджер Б. (2015), «Проблема 3.10» , «Математическая космическая одиссея: твердотельная геометрия в 21 веке» , Dolciani Mathematical Expositions, vol. 50, Математическая ассоциация Америки, с. 63, ISBN 9780883853580

[ww-4] Jump up to: ^а ^б Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2004), Пути победы в математических играх , том. IV, А. К. Петерс, стр. 913–915.

[xa-5] фон Хольк, Николай Ингеманн (январь 2018 г.), Экспериментальный подход к проблемам упаковки (PDF) , бакалаврская диссертация под руководством Сёрена Эйлерса, Копенгагенский университет, заархивировано (PDF) из оригинала 17 ноября 2019 г. , получено 11 ноября 2019 г. -17

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]