Упаковка штатива

Нерешенная задача по математике :

Сколько штативов можно уместить в одном кубе?

(еще нерешенные задачи по математике)

Штативная упаковка и соответствующая ей монотонная матрица. Этот пример соответствует 2-сравнимому множеству {(1,1,1), (1,3,3), (2,1,2), (2,4,3), (3,1,4), (3,4,5), (4,2,1), (4,5,3), (5,2,2), (5,3,4), (5,5,5)}.

В комбинаторике . упаковка штатива — это проблема поиска множества непересекающихся штативов в трехмерной сетке, где штатив — это бесконечный поликуб , объединение кубов сетки вдоль трех положительных лучей, выровненных по осям, с общей вершиной

Некоторые проблемы укладки и упаковки штативов и связанных с ними форм были сформулированы в 1967 году Шерманом К. Стейном . Первоначально Штейн назвал штативы этой задачи «полукрестами», а Соломон В. Голомб назвал Штейна их углами . Совокупность непересекающихся штативов можно компактно представить как монотонную матрицу , квадратную матрицу, ненулевые элементы которой увеличиваются вдоль каждой строки и столбца и чьи равные ненулевые элементы помещаются в монотонную последовательность ячеек. и проблему также можно сформулировать в терминах поиска наборов троек, удовлетворяющих условию совместимости, называемому «2-сравнимостью», или поиска совместимых наборов треугольников в выпуклом многоугольнике.

Лучшая нижняя граница, известная для количества штативов, вершины которых можно упаковать в $n\times n\times n$ сетка $\Omega (n^{1.546})$, а лучшая верхняя граница равна $n^{2}/\exp \Omega (\log ^{*}n)$, оба выражены в большой нотации Omega .

Эквивалентные проблемы

Координаты $(x_{i},y_{i},z_{i})$ вершин решения задачи о штативе образуют 2-сравнимые множества троек , где две тройки определяются как 2-сравнимые, если существуют либо хотя бы две координаты, в которых одна тройка меньше другой, либо хотя бы две координаты, в которых одна тройка больше другой. Это условие гарантирует, что триподы, определенные из этих троек, не будут иметь пересекающихся лучей.

Другая эквивалентная двумерная версия вопроса спрашивает, сколько ячеек в $n\times n$ массив квадратных ячеек (индексируется из $1$ к $n$) можно заполнить числами из $1$ к $n$ таким образом, что непустые ячейки каждой строки и каждого столбца массива образуют строго возрастающую последовательность чисел, а позиции, занимающие каждое значение $i$ образуют монотонную цепочку внутри массива. Массив с такими свойствами называется монотонной матрицей. Коллекция непересекающихся штативов с вершинами. $(x_{i},y_{i},z_{i})$ можно преобразовать в монотонную матрицу, поместив число $z_{i}$ в ячейке массива $(x_{i},y_{i})$ и наоборот.

Проблема также эквивалентна поиску как можно большего количества треугольников среди вершин выпуклого многоугольника, чтобы никакие два треугольника, имеющие общую вершину, не имели вложенных углов в этой вершине. Эту задачу о подсчете треугольников поставил Петер Брасс. и ее эквивалент упаковке штатива был обнаружен Ароновом и др.

Нижние границы

Легко найти решение проблемы упаковки штатива с помощью $\Omega (n^{3/2})$ штативы. Например, для $k=\lfloor {\sqrt {n}}\rfloor$, $\Omega (n^{3/2})$ тройки $${\bigl \{}(ak+b+1,bk+c+1,ak+c+1){\big |}a,b,c\in [0,k-1]{\bigr \}}$$2-сравнимы.

После нескольких предыдущих улучшений этой наивной границы, Гауэрс и Лонг нашли решение проблемы мощности штатива. $\Omega (n^{1.546})$.

Верхние границы

Из любого решения проблемы упаковки штатива можно получить сбалансированный трехдольный граф, вершины которого представляют собой три копии чисел из $0$ к $n-1$ (по одной на каждую из трех координат) с треугольником ребер, соединяющим три вершины, соответствующие координатам вершины каждого штатива. Других треугольников в этих графах нет (это локально линейные графы ), поскольку любой другой треугольник привел бы к нарушению 2-сравнимости. Следовательно, согласно известным верхним оценкам задачи Ружи–Семереди (одна из версий которой заключается в нахождении максимальной плотности ребер в сбалансированном трехдольном локально линейном графе), максимальное число непересекающихся треноги, которое можно упаковать в $n\times n\times n$ сетка $o(n^{2})$, а точнее $n^{2}/\exp \Omega (\log ^{*}n)$. Хотя Тискин пишет, что «более тщательный анализ параметров» может дать оценку, которая будет меньше квадратичной на полилогарифмический коэффициент, он не предоставляет подробностей и доказательств того, что это число $o(n^{2})$ использует только те же методы, которые известны для задачи Ружи – Семереди, поэтому это более сильное утверждение кажется ошибкой.

Аргумент Дина Хикерсона показывает, что, поскольку штативы не могут заполнить пространство с постоянной плотностью, то же самое справедливо и для аналогичных задач в более высоких измерениях.

Маленькие экземпляры

Для небольших случаев проблемы со штативом точное решение известно. Количество штативов, которые можно упаковать в один $n\times n\times n$ куб, для $n\leq 11$, являются:

1, 2, 5, 8, 11, 14, 19, 23, 28, 32, 38, ...

Например, на рисунке показаны 11 штативов, которые можно упаковать в один $5\times 5\times 5$ куб.

Количество различных монотонных матриц порядка $n$, для $n=1,2,3,\dots$ является

2, 19, 712, 87685, 31102080, 28757840751, ...