Нет трехрядной проблемы

Набор из 20 точек в сетке 10 × 10, без трех точек на линии.

В математике , в области дискретной геометрии , задача no-three-in-line требует максимального количества точек, которые могут быть помещены в сетку $n \times n,$ чтобы никакие три точки не лежали на одной прямой . Это число не превосходит $2 n$ , так как если в сетку поместить $2 n + 1$ точки, то по принципу «ящика» некоторая строка и некоторый столбец будут содержать три точки. Проблема была представлена Генри Дудени в 1917 году.

Хотя проблема может быть решена с помощью $2 n$ точек для каждого $n$ до $46$ , предполагается, что для достаточно больших значений $n$ возможно менее $2 n$ точек . Лучшие решения, которые, как известно, работают для сколь угодно больших значений $n,$ размещают чуть меньше $3$ $n$ $/ 2$ точек.

Нижние границы [ править ]

Пол Эрдеш (в работе Roth, 1951 ) заметил, что, когда $n$ - простое число , набор из $n$ узлов сетки $(i, i 2 mod n)$ для $0 \leq i < n$ не содержит трех коллинеарных точек. Когда $n$ не является простым, это построение можно выполнить для сетки $p \times p,$ содержащейся в сетке $n \times n$ , где $p$ - наибольшее простое число, не большее $n$ . Как следствие, для любого $ε$ и для любого достаточно большого $n$ можно разместить

{\ Displaystyle (1- \ varepsilon) п}

точки в сетке

n \times n

без трех коллинеарных точек.

Граница Эрдеша впоследствии была улучшена: Hall et al. (1975) показывают, что, когда $n / 2$ простое, можно получить решение с $3 (n - 2) / 2$ точками, поместив точки на гиперболу $xy \equiv k (mod n / 2)$ , где $k$ можно выбрать произвольно до тех пор, пока он не равен нулю по модулю $n / 2$ . Опять же, для произвольного $n$ можно выполнить это построение для простого числа около $n / 2,$ чтобы получить решение с

{\ displaystyle \ left ({\ frac {3} {2}} - \ varepsilon \ right) n}

точки.

Предполагаемые верхние границы [ править ]

Гай и Келли (1968) предположили, что для больших $n$ нельзя добиться большего, чем $cn$ с

c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.

Пегг (2005) отметил, что Габор Эллманн обнаружил в марте 2004 г. ошибку в исходной статье эвристических рассуждений Гая и Келли, которая, если ее исправить, приведет к

c={\frac {\pi }{\sqrt {3}}}\approx 1.814.

Приложения [ править ]

Задача о треугольнике Хейльбронна требует размещения $n$ точек в единичном квадрате, который максимизирует площадь наименьшего треугольника, образованного тремя точками. Применяя построение Эрдеша множества точек сетки без трех коллинеарных точек, можно найти место, в котором наименьший треугольник имеет площадь

{\frac {1-\varepsilon }{2n^{2}}}.

Обобщения [ править ]

Высшие измерения [ править ]

Неколлинеарные наборы точек в трехмерной сетке были рассмотрены Пор и Вуд (2007) . Они доказали, что максимальное количество точек в сетке $n \times n \times n$ без трех коллинеарных точек равно . Подобно двухмерному построению Эрдеша, это может быть выполнено с помощью точек $($ $x$ $,$ $y$ $,$ $x$ $2$ $+$ $y$ $2$ $) по модулю$ $p$ , где $p$ - простое число, конгруэнтное $3 по модулю 4$ . $\Theta (n^{2})$

Другой аналог в более высоких измерениях - найти наборы точек, которые не все лежат в одной плоскости (или гиперплоскости). Эд Пегг , Олег567 и др. Сообщили, что для трехмерной задачи без четырех компланарностей можно выбрать 8 таких точек в сетке $3 \times 3 \times 3$ (ровно одно решение с точностью до поворота / отражения) $10.$ такие точки можно найти для $4 \times 4 \times 4$ ( $232$ различных решения), и $13$ таких точек можно найти для $5 \times 5 \times 5$ ( $38$ различных решений). ^[1]^[2] По состоянию на 2015 год ^[update]неизвестно, какое максимальное решение для $6 \times 6 \times 6.$ сетки, ни сколько таких решений существует. Подобно верхней границе $2 n$ для двумерного случая, существует верхняя граница $3 n$ для трехмерного случая (не более $3$ точек на плоскость и не более $n$ таких плоскостей в сетке), хотя, как видно выше, не все значения $n$ достигают верхней границы.

Проблема набора крышек касается аналогичной проблемы в многомерных векторных пространствах над конечными полями . ^[3]

Обобщения графов [ править ]

Неколлинеарное размещение $n$ точек также можно интерпретировать как графическое изображение всего графа таким образом, что, хотя ребра пересекаются, никакое ребро не проходит через вершину. Приведенную выше конструкцию Эрдеша можно обобщить, чтобы показать, что каждый $n$ -вершинный $k-$ раскрашиваемый граф имеет такой рисунок в сетке $O (n) \times O (k)$ ( Wood 2005 ).

Можно также рассматривать графические изображения в трехмерной сетке. Здесь условие неколлинеарности означает, что вершина не должна лежать на несмежном ребре, но нормально работать с более строгим требованием, чтобы никакие два ребра не пересекались ( Pach, Thiele & Tóth 1998 ; Dujmović, Morin & Wood 2005 ; Ди Джакомо, Лиотта и Мейер 2005 ).

Маленькие значения $n$ [ править ]

При $n \leq 46$ известно, что $2 n$ точек могут быть размещены без трех точек в строке. Количество решений (не считая отражений и поворотов как отдельных) для малых $n = 2, 3, ...,$ равно

1 , 1 , 4 , 5 , 11 , 22 , 57 , 51 , 156 , 158 , 566, 499, 1366, ... (последовательность A000769 в OEIS ).

Заметки [ править ]

^ Вопрос Эда Пегга
^ Сайт Эда Пегга
^ Klarreich, Erica (31 мая 2016). «Доказательство простой игры ошеломляет математиков» . Quanta ..

Ссылки [ править ]

Дудени, Генри (1917). «317. Головоломка с пешками» . Занятия по математике . Эдинбург: Нельсон. п. 94.. Решение, стр. 222 .
Ди Джакомо, Эмилио; Лиотта, Джузеппе; Мейер, Хенк (2005). «Вычисление прямолинейных трехмерных сеточных чертежей графиков в линейном объеме». Вычислительная геометрия: теория и приложения . 32 (1): 26–58. DOI : 10.1016 / j.comgeo.2004.11.003 .
Дуймович, Вида; Morin, Pat ; Вуд, Дэвид Р. (2005). «Макет графов с ограниченной шириной дерева». SIAM Journal on Computing . 34 (3): 553–579. arXiv : cs / 0406024 . DOI : 10,1137 / S0097539702416141 . S2CID 3264071 .
Фельснер, Стефан; Лиотта, Джузеппе; Висмат, Стивен К. (2003). «Прямые чертежи на ограниченных целочисленных сетках в двух и трех измерениях» (PDF) . Журнал графических алгоритмов и приложений . 7 (4): 363–398. DOI : 10,7155 / jgaa.00075 .
Фламменкамп, Ахим (1992). «Прогресс в проблеме отсутствия трех рядов» . Журнал комбинаторной теории . Series A. 60 (2): 305–311. DOI : 10.1016 / 0097-3165 (92) 90012-J .
Фламменкамп, Ахим (1998). «Прогресс в проблеме« нет трех рядов », II». Журнал комбинаторной теории . Series A. 81 (1): 108–113. DOI : 10,1006 / jcta.1997.2829 .
Гай, РК ; Келли, Пенсильвания (1968). «Проблема без трех рядов». Канадский математический бюллетень . 11 (4): 527–531. DOI : 10,4153 / CMB-1968-062-3 . Руководство по ремонту 0238765 .
Холл, RR; Джексон, штат TH; Садбери, А .; Уайлд, К. (1975). «Некоторые успехи в решении проблемы отсутствия трех рядов» . Журнал комбинаторной теории . Series A. 18 (3): 336–341. DOI : 10.1016 / 0097-3165 (75) 90043-6 .
Лефманн, Ханно (2008). «Нет $l$ точек сетки в пространствах малой размерности». Алгоритмические аспекты в информации и управлении, 4-я Международная конференция, AAIM 2008, Шанхай, Китай, 23–25 июня 2008 г., Материалы . Конспект лекций по информатике. 5034 . Springer-Verlag. С. 259–270. DOI : 10.1007 / 978-3-540-68880-8_25 .
Пах, Янош ; Тиле, Торстен; Тот, Геза (1998). «Трехмерная сетка чертежей графиков». Рисование графиков, 5-е Междунар. Symp., GD '97 . Конспект лекций по информатике. 1353 . Springer-Verlag. С. 47–51. DOI : 10.1007 / 3-540-63938-1_49 .
Пегг, Эд младший (11 апреля 2005 г.). «Математические игры: задания на шахматной доске» . Проверено 25 июня 2012 года .
Пор, Аттила; Вуд, Дэвид Р. (2007). «Нет-тройка в строке в 3D». Алгоритмика . 47 (4): 481. DOI : 10.1007 / s00453-006-0158-9 . S2CID 209841346 .
Рот, KF (1951). «О проблеме Хайльбронна». Журнал Лондонского математического общества . 26 (3): 198–204. DOI : 10,1112 / jlms / s1-26.3.198 .
Вуд, Дэвид Р. (2005). « Сеточные рисунки k- раскрашиваемых графов» . Вычислительная геометрия: теория и приложения . 30 (1): 25–28. DOI : 10.1016 / j.comgeo.2004.06.001 .

Внешние ссылки [ править ]

Фламменкамп, Ахим. «Проблема отсутствия трех рядов» .
Вайсштейн, Эрик В. «Проблема №-тройки в строке» . MathWorld .

[1] Вопрос Эда Пегга

[2] Сайт Эда Пегга

[3] Klarreich, Erica (31 мая 2016). «Доказательство простой игры ошеломляет математиков» . Quanta ..

[1]