Математики установили рекорд по плотной упаковке тетраэдров

lenta.ru/news/2009/08/14/pack/
www.princeton.edu/main/news/archive/S25/...l?section=topstories
Princeton pair sets world record in packing puzzle


Я чего-то не понимаю...
Вроде тетраэдры плотно пакуются...

Или это надо их строго в куб закатать? Тогда да, будут дыры.

Вот. Задачку придумал.

Каждый день прилетает Правильный Мух и садится на шахматную доску.
Двигается строго по прямым, проходящим через центры клеток (на то он и Правильный). Пройдя все центры, улетает.
Сегодня он решил стартовать с центра какой-нибудь клетки и двигаться строго по вертикалям и горизонталям с поворотами только в центрах, да призадумался:
какой максимальной длины может быть его маршрут при минимально возможном числе поворотов?

Отредактировано azur (2009-08-14 19:05:46)

Тут два экстремальных условия и надо бы расставить приоритеты.
Что важнее - минимум поворотов или максимальная длина ?

Оба важны. Надо среди всех возможных маршрутов с минимальным количеством поворотов найти самый длинный ..

azur написал(а):Т.е минимум важнее получается?

Vladimirovich написал(а):Да, именно так

PS. Дело в том, что максимум длины стремится к бесконечности, очевидно (можно бесконечно ходить по 63 клеткам и лишь затем пойти на последнюю, 64-ю)
В таких маршрутах искать минимум поворотов - гиблое дело

Ну в общем навскидку - два маршрута по 14 поворотов
Один по пиле - а1-а8-b8-b1-c1-c8-...
8x7+7x1 насчитал = 63

А второй спираль из центра - d5-e5-e4-c4-c5-f6-f3-....
1+1+2+2+3+3+4+4+5+5+6+6+7+7+7 = 63
Тоже

Может все равно как ходить?

длина может быть больше

azur написал(а):Ну тогда я не понял условия
Я думал по всем по одному разу почему-то

Vladimirovich написал(а):При минимуме поворотов ведь можно и пройти по одной и той же клетке дважды ..

84?
a1-a8-h8-h1-b1-b8-g8-g1-c1-c8-f8-f1-d1-d8-e8-e1.

azur написал(а):Ну тады надо подумать...
Я сразу не так понял

Vladimirovich написал(а):Кроме кубов никакие равные многогранники плотно не пакуются. В свое время Улам выдвинул гипотезу, что упаковка равных сфер (~0,74048) плотнее, чем выпуклых многогранников .. Недавно выяснилось, что уже в случае с тетраэдрами это не так .. А сейчас упаковка тетраэдров достигла плотности ~0,782

Отредактировано azur (2009-08-15 01:57:38)

87 для 14 поворотов:
d1-d8-h8-h1-c1-c8-g8-g1-b1-b8-f8-f1-a1-a8-e8-e1

Отредактировано СюгировФан (2009-08-15 22:16:08)

azur написал(а):Вот нет у меня много пирамидков под рукой...
Угол пространственный у вершины вроде кратный пространственному углу тетраэдра?
Могу ошибаться конечно...

Эээ. ув. СюгировФан , по 15-16 поворотов легко крутить
Вот по 14 - пока я такой минимум нашел. Условия были, что минимум первичен

Ув. Владимирович, у меня вроде 14 поворотов.

СюгировФан написал(а):Вах, ув.СюгировФан, прошу прощения. Я типа по ходам ладьей посчитал,а не по поворотам.
-1 мне
Тогда Ваш последний вариант не знаю пока, как превзойти ..

Попробуйте доказать, что 14 это минимум

13 поворотов-это 7 вертикальных и 7 горизонтальных ходов ладьёй. Есть вертикаль и есть горизонталь, вдоль которых ладья не ходила. В точку их пересечения ладья попасть не могла.

СюгировФан написал(а):

87 - это мой правильный ответ и тоже не вижу как превзойти ..

В свое время в сети были очень популярны флеш-игры одного японца: Toshimitsu Tagagi.
Если еще не играли, можете убить час свободного времени на первой из них - ogl.ru/flash/play/1334 красная комната

korrespondent.net/tech/science/938590

Опять прилетал Правильный Мух. Сегодня решил двигаться только по диагоналям.
Долго думал при каком минимуме числа поворотов ему удастся пройти все центры клеток одного цвета ..

15
a1-h8-g7-h6-c1-a3-f8-e7-h4-e1-a5-d8-c7-h2-g1-a7-b8.

Не нашел меньше.

СюгировФан написал(а):Обосновать попробуем?

Разобьём доску на прямоугольники a3-f8-h6-c1: a5-d8-h4-e1: a7-b8-h2-g1 и диагональ a1-h8. Каждому углу прямоугольника соответствует ход по этому прямоугольнику, после которого слон попал в этот угол. Значит, по каждому прямоугольнику сделано не меньше четырёх ходов.
Если первый и последний ход не принадлежит прямоугольнику, то:
обход начинается не с угла;
каждому углу соотв. ход;
плюс ещё ход чтобы можно было уйти с прямоугольника.Итого не меньше 5 ходов.
В противном случае можно обойтись 4 ходами.
Соответственно большая диагональ 3 и 2 хода.
Минимум ходов: 3+5+5+5-2(объекты, которым принадлежат первый и последний ходы)=16ходов, т.е. 15 поворотов.

Отредактировано СюгировФан (2009-09-01 23:17:15)

В общем правильно.

Мух же рассуждал примерно так:
Разделим все возможные повороты на внешние - на находящихся на краю доски полях a1, c1, e1, g1, h2, h4, h6, h8, f8, d8, b8, a7, a5, a3 (всего 14) - и на внутренние (не на краю доски). На внешних полях не будет поворотов только если в них начинается и заканчивается маршрут. Вопрос в том, как минимизировать количество внутренних поворотов.
А вот тут помогает представление доски в виде большой диагонали a1-h8 и прямоугольников c1-h6-f8-a3, e1-h4-d8-a5, g1-h2-b8-a7. Все возможные маршруты Муха принадлежат исключительно этим четырем фигурам. Очевидно, чтобы перейти от одной фигуры к другой необходим внутренний поворот. Всего таких поворотов минимум три (т.к. фигур - четыре).
Итого, если начинать и заканчивать маршрут на внешних полях, то минимум поворотов будет равен 14-2+3=15. При этом маршрут необходимо начинать (или заканчивать) из угла на большой диагонали, иначе поворотов будет больше.

Отредактировано azur (2009-09-02 03:45:21)