Войти
Набор из 20 точек в сетке 10 × 10, без трех точек в строке. В математике, в области дискретной геометрии, задача no-three-in-line требует максимального количества точек, которые могут быть размещены в сетке n × n, чтобы никакие три точки не были коллинеарны. Это число не превосходит 2n, так как если в сетку поместить 2n + 1 точек, то по принципу «голубятни» некоторая строка и некоторый столбец будут содержать три точки. Проблема была представлена Генри Дудени в 1917 году.
Хотя проблема может быть решена с помощью 2n точек для каждого n до 46, предполагается, что менее 2n точек возможно для достаточно большие значения n. Лучшие решения, которые, как известно, работают для сколь угодно больших значений n, размещают чуть меньше 3n / 2 точек.
Пол Эрдеш (в Рот 1951) заметил, что, когда n является простым числом, набор из n точек сетки (i, i mod n), для 0 ≤ i < n, contains no three collinear points. When n is not prime, one can perform this construction for a p × p grid contained in the n × n grid, where p is the largest prime that is at most n. As a consequence, for any ε and any sufficiently large n, one can place
точек в n × n сетка без трех коллинеарных точек.
Граница Эрдеша была впоследствии улучшена: Hall et al. (1975) показывают, что, когда n / 2 простое, можно получить решение с 3 (n - 2) / 2 точками, поместив точки на гиперболу xy ≡ k (mod n / 2), где k может быть выбрано произвольно, если оно не равно нулю по модулю n / 2. Опять же, для произвольного n можно выполнить это построение для простого числа около n / 2, чтобы получить решение с
очков.
Гай и Келли (1968) предположили, что для больших n нельзя добиться большего, чем c n с
![c = {\ sqrt [{3}] {{\ frac {2 \ pi ^ {2}} {3}}}} \ приблизительно 1,874.](https://wikimedia.org/api/rest_v1/media/math/render/svg/d027b29f0708dc2927acb8f114f21ed025051989)
Пегг (2005) отметил, что Габор Эллманн обнаружил, в марте 2004 г. ошибка в исходной статье эвристических рассуждений Гая и Келли, которая, если исправить, приводит к
В задаче треугольника Хейльбронна требуется размещение n точек в единичном квадрате, который максимизирует площадь наименьшего треугольника, образованного тремя точками. Применяя построение Эрдеша множества точек сетки без трех коллинеарных точек, можно найти место, в котором наименьший треугольник имеет площадь
Неколлинеарные наборы точек в трех размерная сетка была рассмотрена Pór Wood (2007). Они доказали, что максимальное количество точек в сетке n × n × n без трех коллинеарных точек равно 
Другой аналог в более высоких измерениях - найти наборы точек, которые не все лежат в одной плоскости (или гиперплоскости). Эд Пегг, Олег567 и др. Сообщили, что для трехмерной задачи без четырех компланарностей в сетке 3x3x3 можно выбрать 8 таких точек (ровно одно решение до вращение / отражение), 10 таких точек можно найти для 4x4x4 (232 различных решения) и 13 таких точек можно найти для 5x5x5 (38 различных решений). По состоянию на 2015 год неизвестно, какое максимальное решение для сетки 6x6x6 и сколько таких решений существует. Подобно верхней границе 2n для случая 2D, существует верхняя граница 3n для случая 3D (не более 3 точек на плоскость и не более n таких плоскостей в сетке), хотя, как видно выше, не все значения числа n достигают верхней границы.
Проблема набора ограничений касается аналогичной проблемы в многомерных векторных пространствах над конечными полями.
A неколлинеарное размещение n точек также можно интерпретировать как рисунок графа из полного графа таким образом, что, хотя ребра пересекаются, никакое ребро не проходит через вершину. Приведенную выше конструкцию Эрдеша можно обобщить, чтобы показать, что каждый n-вершинный k-раскрашиваемый граф имеет такой рисунок в сетке O (n) × O (k) (Wood 2005).
Также можно рассматривать графические изображения в трехмерной сетке. Здесь условие неколлинеарности означает, что вершина не должна лежать на несмежном ребре, но нормально работать с более строгим требованием, чтобы никакие два ребра не пересекались (Pach, Thiele Tóth 1998 ; Дуймович, Морин и Вуд 2005 ; Ди Джакомо, Лиотта и Мейер 2005).
Для n ≤ 46 известно, что 2n точек могут быть размещены без трех в строке. Число решений (не считая отражений и вращений как отдельных) для малых n = 2, 3,..., составляет
