Нет проблемы с тремя рядами

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

Задача «нет трёх рядов» в дискретной геометрии спрашивает, сколько точек можно разместить в $n\times n$ сетку так, чтобы никакие три точки не лежали на одной прямой. Проблема касается линий всех уклонов, а не только тех, которые совпадают с сеткой. Он был введен Генри Дьюдени в 1900 году. Брасс, Мозер и Пах называют его «одним из старейших и наиболее широко изученных геометрических вопросов, касающихся точек решетки».

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

Также были изучены несколько связанных проблем поиска точек, в которых нет трех в строке, среди других наборов точек, отличных от сетки. возникла в развлекательной математике Хотя проблема «нет трех рядов» , она находит применение в рисовании графиков и в задаче о треугольнике Гейльбронна .

Небольшие экземпляры

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

Задача была впервые поставлена ​​Генри Дьюдени в 1900 году как головоломка из развлекательной математики, сформулированная в виде размещения 16 пешек шахматной доски на доске так, чтобы никакие три не оказались в линии. Это как раз и есть проблема отсутствия трёх рядов, для случая $n=8$. В более поздней версии головоломки Дьюдени модифицировал задачу, сделав ее решение уникальным, задав решение, в котором две пешки находятся на полях d4 и e5 и атакуют друг друга в центре доски.

Многие авторы опубликовали решения этой проблемы для малых значений $n$, и к 1998 году стало известно, что $2n$ точки могут быть размещены на $n\times n$ сетка без трех в строкедля всех $n$ до 46 и некоторых больших значений. Количество решений с $2n$ баллы за небольшие значения $n$, начиная с $n=2$, являются

1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (последовательность A000755 в OEIS ).

Числа классов эквивалентности решений с $2n$ точки под отражениями и вращениями

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

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

Точное количество точек, которые можно разместить, как функция $n$, не известно. Однако как доказанные, так и предполагаемые границы ограничивают это число диапазоном, пропорциональным $n$.

Общие методы размещения

Субоптимальное размещение $11$ указывает на $12\times 12$ сетке, используя метод Эрдёша. Самое большое простое число $p$ меньше размера сетки $p=11$; решение помещает точки в координаты $(i,i^{2}$ против $p)$ для $i=0,1,\dots p-1$. Например, $(4,5)$ включен, потому что $4^{2}=16\cong 5$ ( ${\displaystyle }$против $11$).

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

Впоследствии граница Эрдеша была улучшена: Hall et al. (1975) показывают, что, когда $n/2$ является простым, можно получить решение с $3(n-2)/2$ точки, помещая точки в несколько копий гиперболы $xy=k$ (против $n/2$), где $k$ может быть выбрано произвольно, если это ненулевой мод. $n/2$. Опять же, для произвольного $n$ это построение можно выполнить для простого числа вблизи $n/2$ чтобы получить решение с ${\tfrac {3}{2}}n-o(n)$ точки.

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

Максимум $2n$ точки могут быть размещены в сетке любого размера $n$. Ведь если разместить больше точек, то по принципу «ячейки» некоторые три из них будут лежать на одной горизонтальной линии сетки. Для $n\leq 46$, эта тривиальная оценка, как известно, является точной.

Предполагаемые границы

Хотя именно $2n$ точки могут быть размещены на маленьких сетках, Гай и Келли (1968) предположили, что для больших сеток существует значительно меньшая верхняя граница количества точек, которые можно разместить. Точнее, они предположили, что количество точек, которые можно разместить, не более чем на сублинейную величину, большую, чем $cn$, с

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

После того, как была обнаружена ошибка в эвристических рассуждениях, приведших к этой гипотезе, Гай исправил ошибку и выдвинул более сильную гипотезу о том, что нельзя сделать больше, чем сублинейно лучше, чем $cn$ с

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

Приложения

Решения проблемы отсутствия трех строк можно использовать, чтобы избежать определенных видов вырождений при построении графов . Проблема, к которой они применяются, включает в себя размещение вершин данного графа в целочисленных координатах на плоскости и рисование ребер графа в виде отрезков прямых линий . Для некоторых графов, таких как граф полезности , пересечения между парами ребер неизбежны, но все же следует избегать размещений, которые заставляют вершину лежать на ребре, проходящем через две другие вершины. Когда вершины расположены без трех в строке, такое проблемное размещение не может возникнуть, поскольку вся линия, проходящая через любые две вершины, а не только отрезок прямой, свободна от других вершин. Тот факт, что задача «нет трех в ряд» имеет решение с линейным числом точек, можно перевести в термины рисования графов, означая, что каждый граф, даже полный граф , может быть нарисован без нежелательных инцидентов вершин и ребер, используя сетку, Площадь квадратична по числу вершин, и что для полных графов такое рисование с площадью меньше квадратичной невозможно. Полные графы также требуют линейного числа цветов при любой раскраске графа , но другие графы, которые можно раскрасить меньшим количеством цветов, также можно нарисовать на сетках меньшего размера: если граф имеет $n$ вершины и раскраска графа с помощью $k$ цвета, его можно нарисовать в виде сетки с площадью, пропорциональной $nk$. Рисование полного графа без трех строк является частным случаем этого результата с $k=n$.

Проблема отсутствия трех рядов также имеет приложения к другой задаче дискретной геометрии — задаче о треугольнике Гейльбронна . В этой задаче необходимо разместить $n$ точки в любом месте единичного квадрата, не ограничиваясь сеткой. Целью размещения является избежание треугольников малой площади, а точнее, максимизация площади наименьшего треугольника, образованного тремя точками. Например, размещение с тремя точками на одной линии было бы очень плохим по этому критерию, потому что эти три точки образовывали бы вырожденный треугольник с нулевой площадью. С другой стороны, если точки можно разместить на сетке с длиной стороны $\varepsilon$ внутри единичного квадрата, без трех в строке, то по теореме Пика каждый треугольник будет иметь площадь не менее $\varepsilon ^{2}/2$, половина квадрата сетки. Таким образом, решение примера проблемы «нет трех в ряд» и последующее уменьшение целочисленной сетки, чтобы она соответствовала единичному квадрату, дает решения проблемы треугольника Гейльбронна, где наименьший треугольник имеет площадь $\Omega (1/n^{2})$. Это приложение послужило для Пола Эрдеша мотивацией найти решение проблемы отсутствия трех рядов. Она оставалась лучшей нижней границей площади, известной для задачи о треугольнике Гейльбронна с 1951 по 1982 год, когда она была улучшена с помощью логарифмического коэффициента с использованием конструкции, не основанной на задаче отсутствия трех прямых.

Обобщения и вариации

Подмножества общего положения

В вычислительной геометрии конечные множества точек, в которых нет трех на прямой, называются находящимися в общем положении . В этой терминологии задача «нет трех рядов» ищет наибольшее подмножество сетки, находящееся в общем положении, но исследователи также рассматривали проблему поиска наибольшего подмножества общего положения других несеточных наборов точек. Найти NP-трудно это подмножество для определенных входных наборов , и трудно аппроксимировать его размер с точностью до постоянного коэффициента; Этот результат сложности аппроксимации суммируется, говоря, что проблема APX-трудна . Если самое большое подмножество имеет размер $k$, решение с непостоянным коэффициентом аппроксимации $O({\sqrt {k}})$ может быть получено с помощью жадного алгоритма , который просто выбирает точки по одной, пока все оставшиеся точки не лежат на прямых, проходящих через пары выбранных точек.

Более детальное представление о времени работы алгоритмов поиска точного оптимального решения можно получить, используя параметризованную сложность , при которой алгоритмы анализируются не только с точки зрения размера входных данных, но и с точки зрения других входных параметров. В этом случае для входов, наибольшее подмножество общих позиций которых имеет размер $k$, его можно найти за промежуток времени, который является экспоненциальной функцией $k$ умножается на полином входного размера $n$, причем показатель степени полинома не зависит от $k$. Задачи с таким ограничением по времени называются управляемыми с фиксированными параметрами .

Для наборов точек $S$ имея максимум ${\textstyle \ell }$ очков на строку, с ${\textstyle \ell =O({\sqrt {|S|}})}$ почти существуют подмножества общего положения размером, пропорциональным ${\textstyle \ell =O({\sqrt {|S|}})}$. Пример сетки показывает, что эту оценку невозможно существенно улучшить. Доказательство существования этих больших подмножеств общего положения можно преобразовать в полиномиальный общего положения. алгоритм поиска подмножества $S$, размер которого соответствует границе существования, с использованием алгоритмического метода, известного как сжатие энтропии .

Жадное размещение

Повторяя предложение Адены, Холтона и Келли (1974) , Мартин Гарднер попросил указать наименьшее подмножество $n\times n$ сетка, которую нельзя расширить: в ней нет трех точек на линии, но в каждом правильном надмножестве есть три точки на линии. Аналогично, это наименьший набор, который может быть создан жадным алгоритмом , который пытается решить проблему отсутствия трех рядов, размещая точки по одной, пока не застрянет. Если рассматривать только осепараллельные и диагональные прямые, то каждое такое множество имеет не менее $n-1$ точки. Однако о варианте задачи, где учитываются все строки, известно меньше: каждое жадное размещение включает в себя как минимум $\Omega (n^{2/3})$ очков, прежде чем застрять, но ничего лучше, чем тривиальное $2n$ верхняя граница известна.

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

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

В гораздо более высоких измерениях наборы точек сетки без трех в строке, полученные путем выбора точек рядом с гиперсферой , использовались для поиска больших наборов Салема – Спенсера , наборов целых чисел без трех, образующих арифметическую прогрессию. Однако использовать ту же идею выбора точек рядом с кругом в двух измерениях не очень хорошо: этот метод находит точки, образующие выпуклые многоугольники, которые удовлетворяют требованию отсутствия трех в линии, но слишком малы. Самые большие выпуклые многоугольники с вершинами в $n\times n$ сетка есть только $O(n^{2/3})$ вершины. Проблема ограничения набора связана с проблемой, аналогичной проблеме отсутствия трех строк в пространствах, которые являются многомерными и основаны на векторных пространствах над конечными полями, а не над целыми числами.

Другое обобщение на более высокие измерения — найти как можно больше точек в трехмерном пространстве. $N\times N\times N$ сетки такой, что никакие четыре из них не лежат в одной плоскости. Эта последовательность начинается с 5, 8, 10, 13, 16,... OEIS : A280537 для N = 2, 3, 4 и т. д.

Тор

Другой вариант проблемы включает преобразование сетки в дискретный тор с использованием периодических граничных условий , в которых левая сторона тора соединяется с правой стороной, а верхняя сторона соединяется с нижней стороной. Это приводит к тому, что наклонные линии, проходящие через сетку, соединяются в более длинные линии через большее количество точек и, следовательно, затрудняют выбор точек, имеющих не более двух из каждой линии. Эти расширенные линии также можно интерпретировать как нормальные линии, проходящие через бесконечную сетку в евклидовой плоскости, взятую по модулю размеров тора. Для тора на основе $m\times n$ сетке максимальное количество точек, которые можно выбрать без трех в строке, не превышает $2\gcd(m,n)$. Когда оба измерения равны и просты, невозможно разместить ровно одну точку в каждой строке и столбце, не образуя линейного числа коллинеарных троек. Также изучались торические версии проблемы более высокой размерности.

См. также

• Головоломка «Восемь ферзей» о размещении точек на сетке, в которых не должно быть двух в одной строке, столбце или диагонали.

Ссылки

• Адена, Майкл А.; Холтон, Дерек А.; Келли, Патрик А. (1974). «Некоторые мысли о проблеме отсутствия трех рядов». В Холтоне, Дерек А. (ред.). Комбинаторная математика: материалы второй австралийской конференции (Мельбурнский университет, 1973) . Конспект лекций по математике. Том. 403. стр. 6–17. дои : 10.1007/BFb0057371 . МР   0349396 .
• Айххольцер, Освин; Эппштейн, Дэвид ; Хайнцль, Ева-Мария (январь 2023 г.). «Геометрические доминирующие множества – минимальная версия проблемы трех рядов» . Вычислительная геометрия . 108 . Эльзевир: 101913. arXiv : 2203.13170 . дои : 10.1016/j.comgeo.2022.101913 . S2CID   249687906 .
• Андерсон, Дэвид Брент (1979). «Обновленная информация о проблеме отсутствия трех рядов» . Журнал комбинаторной теории . Серия А. 27 (3): 365–366. дои : 10.1016/0097-3165(79)90025-6 . МР   0555806 .
• Брасс, Питер; Сенек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф С.Б. (2007). «Об одновременных вложениях планарных графов» . Вычислительная геометрия . 36 (2): 117–130. дои : 10.1016/j.comgeo.2006.05.006 . МР   2278011 .
• Брасс, Питер; Мозер, Уильям; Пах, Янош (2005). «Раздел 10.1: Упаковка точек решетки в подпространствах» . Проблемы исследования дискретной геометрии . Спрингер, Нью-Йорк. стр. 417–421. ISBN  978-0-387-29929-7 . МР   2163782 .
• Купер, Алек С.; Пихурко Олег; Шмитт, Джон Р.; Уоррингтон, Грегори С. (2014). «Задача Мартина Гарднера о минимуме № 3 в ряд». Американский математический ежемесячник . 121 (3): 213–221. arXiv : 1206.5350 . doi : 10.4169/amer.math.monthly.121.03.213 . JSTOR   10.4169/amer.math.monthly.121.03.213 . S2CID   887220 .
• Купер, Джошуа Н.; Солимоси, Йожеф (2005). «Коллинеарные точки в перестановках» (PDF) . Анналы комбинаторики . 9 (2): 169–175. arXiv : math/0408396 . дои : 10.1007/s00026-005-0248-4 . МР   2153735 . S2CID   11035679 .
• Крэггс, Д.; Хьюз-Джонс, Р. (1976). «О проблеме отсутствия трех рядов» . Журнал комбинаторной теории . Серия А. 20 (3): 363–364. дои : 10.1016/0097-3165(76)90030-3 . МР   0406804 .
• Дудени, Генри (1917). «317. Загадка с пешками» . Забавы по математике . Эдинбург: Нельсон. п. 94. Решение, с. 222 . Первоначально опубликовано в газете London Tribune 7 ноября 1906 года.
• Ди Джакомо, Эмилио; Лиотта, Джузеппе; Мейер, Хенк (2005). «Расчет прямолинейных трехмерных сеточных рисунков графиков в линейном объеме». Вычислительная геометрия: теория и приложения . 32 (1): 26–58. дои : 10.1016/j.comgeo.2004.11.003 .
• Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2005). «Компоновка графов с ограниченной шириной дерева». SIAM Journal по вычислительной технике . 34 (3): 553–579. arXiv : cs/0406024 . дои : 10.1137/S0097539702416141 . S2CID   3264071 .
• Элкин, Майкл (2011). «Улучшенная конструкция наборов без прогрессирования» . Израильский математический журнал . 184 : 93–128. arXiv : 0801.4310 . дои : 10.1007/s11856-011-0061-1 . МР   2823971 .
• Эппштейн, Дэвид (2018). «Глава 9: Общее положение». Запрещенные конфигурации в дискретной геометрии . Издательство Кембриджского университета. стр. 72–86.
• Фламменкамп, Ахим (1992). «Прогресс в решении проблемы отсутствия трех рядов» . Журнал комбинаторной теории . Серия А. 60 (2): 305–311. дои : 10.1016/0097-3165(92)90012-J .
• Фламменкамп, Ахим (1998). «Прогресс в решении проблемы отсутствия трех рядов, II» . Журнал комбинаторной теории . Серия А. 81 (1): 108–113. дои : 10.1006/jcta.1997.2829 .
• Фрёзе, Винсент; Кандж, Ияд; Нихтерляйн, Андре; Нидермайер, Рольф (2017). «Нахождение точек в общем положении». Международный журнал вычислительной геометрии и приложений . 27 (4): 277–296. arXiv : 1508.01097 . дои : 10.1142/S021819591750008X . МР   3766097 . S2CID   47260245 .
• Гарднер, Мартин (октябрь 1976 г.). «Комбинаторные задачи, некоторые старые, некоторые новые и все новые, атакованные компьютером». Математические игры. Научный американец . Том. 235, нет. 4. С. 131–137. JSTOR   24950467 .
• Гай, РК ; Келли, Пенсильвания (1968). «Проблема трех рядов» . Канадский математический бюллетень . 11 (4): 527–531. дои : 10.4153/CMB-1968-062-3 . МР   0238765 .
• Холл, РР; Джексон, Техас; Садбери, А.; Уайлд, К. (1975). «Некоторые успехи в решении проблемы отсутствия трех рядов» . Журнал комбинаторной теории . Серия А. 18 (3): 336–341. дои : 10.1016/0097-3165(75)90043-6 .
• Харборт, Хейко ; Эртель, Филипп; Прелльберг, Томас (1989). «Нет-три в очереди для семнадцати и девятнадцати» . Материалы совещания «Комбинаторик» в Обервольфахе (1986). Дискретная математика . 73 (1–2): 89–90. дои : 10.1016/0012-365X(88)90135-5 . МР   0974815 .
• Ярник, Войтех (1926). «О точках сетки на выпуклых кривых». Математический журнал (на немецком языке). 24 (1): 500–518. дои : 10.1007/BF01216795 . МР1544776   . S2CID   117747514 .
• Кларрайх, Эрика (31 мая 2016 г.). «Простое доказательство игры ошеломляет математиков» . Кванта .
• Клёве, Торлейв (1978). «О проблеме отсутствия трех рядов. II» . Журнал комбинаторной теории . Серия А. 24 (1): 126–127. дои : 10.1016/0097-3165(78)90053-5 . МР   0462998 .
• Клёве, Торлейв (1979). «О проблеме отсутствия трех рядов. III». Журнал комбинаторной теории . Серия А. 26 (1): 82–83. дои : 10.1016/0097-3165(79)90055-4 . МР   0525088 .
• Комлос, Дж .; Пинц, Дж .; Семереди, Э. (1982). «Нижняя оценка проблемы Хейльбронна». Журнал Лондонского математического общества . 25 (1): 13–24. дои : 10.1112/jlms/s2-25.1.13 . МР   0645860 .
• Кнут, Дональд Э. (2008). «Ответ к упражнению 242» . Искусство компьютерного программирования, глава 1b: Черновой вариант раздела 7.1.4: Двоичные диаграммы решений . п. 130.
• Ку, Ченг Йи; Вонг, Кок Бин (2018). «О задаче отсутствия трех прямых на m -мерном торе». Графы и комбинаторика . 34 (2): 355–364. дои : 10.1007/s00373-018-1878-8 . МР   3774457 . S2CID   3935268 .
• Мисиак, Александр; Стемпень, Зофья; Шимашкевич, Алисия; Шимашкевич, Люциан; Звержовский, Мацей (2016). «Заметка о проблеме отсутствия трех прямых на торе». Дискретная математика . 339 (1): 217–221. arXiv : 1406.6713 . дои : 10.1016/j.disc.2015.08.006 . МР   3404483 . S2CID   40210322 .
• Пах, Янош ; Тиле, Торстен; Тот, Геза (1998). «Трёхмерные сеточные рисунки графиков». Рисование графика, 5-й Межд. Симп., ГД '97 . Конспекты лекций по информатике. Том. 1353. Шпрингер-Верлаг. стр. 47–51. дои : 10.1007/3-540-63938-1_49 .
• Пейн, Майкл С.; Вуд, Дэвид Р. (2013). «О задаче выбора подмножества общего положения». SIAM Journal по дискретной математике . 27 (4): 1727–1733. arXiv : 1208.5289 . дои : 10.1137/120897493 . МР   3111653 . S2CID   7164626 .
• Пегг, Эд младший (11 апреля 2005 г.). «Задачи на шахматной доске» . Математические игры . Математическая ассоциация Америки . Проверено 25 июня 2012 г.
• Пор, Аттила; Вуд, Дэвид Р. (2007). «Нет-три в ряд-в-3D». Алгоритмика . 47 (4): 481. doi : 10.1007/s00453-006-0158-9 . S2CID   209841346 .
• Рот, К.Ф. (1951). «О проблеме Гейльбронна». Журнал Лондонского математического общества . 26 (3): 198–204. дои : 10.1112/jlms/s1-26.3.198 .
• Вуд, Дэвид Р. (2005). «Сеточные рисунки k -раскрашиваемых графов» . Вычислительная геометрия: теория и приложения . 30 (1): 25–28. дои : 10.1016/j.comgeo.2004.06.001 .

Внешние ссылки

• Фламменкамп, Ахим. «Проблема трех рядов» .
• Вайсштейн, Эрик В. «Задача «нет трех в ряд»» . Математический мир .