Задача «никакие три на прямой» ({g;gcg «untgtny mjn ug hjxbkw»)

Множество из 20 точек в решётке 10 × 10, никакие три из которых не находятся на одной прямой.

Задача «никакие три точки не лежат на одной прямой» — одна из задач комбинаторной геометрии, состоящая в нахождении количества точек, которые можно расположить на решётке $n\times n$ так, чтобы никакие три точки не находились на одной прямой.

Брасс, Мозер и Пах назвали задачу «одним из самых старых и интенсивно изучаемых геометрических вопросов, касающихся точек решётки»^[1].

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

Хотя первоначально проблема появилась как задача занимательной математики, она имеет приложение в визуализации графов и в проблеме треугольников Хайльбронна^[англ.].

Малые размеры

Задачу впервые опубликовал Генри Эрнест Дьюдени^[англ.] в 1900 году как головоломку занимательной математики в терминах размещения 16 пешек на шахматной доске так, что никакие три пешки не находятся на одной прямой^[2]. Это в точности проблема «никакие три на прямой» для $n=8$ ^[3]. В более поздних версиях головоломки Генри изменил задачу, делающее решение единственным, требуя найти решение, когда две пешки уже на доске поставлены в клетки d4 и e5 в центре доски^[4].

Много авторов публиковали решения задачи для малых значений $n$ ^[5]^[6]^[7]^[8]^[9]^[10]^[11] и к 1998 году было известно, что $2n$ точек может быть размещено на решётке $n\times n$ без трёх точек на прямой для всех $n$ до 46 и некоторых бо́льших значений^[11]. Число решений (не включая отражения и вращения) для малых значений $n$ , начиная с $n=2$ , равно^[3]

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$ по модулю $11$ .

Решение Пала Эрдёша, опубликованное Ротом^[12], основано на факте, что, когда $n$ является простым числом, множество из $n$ точек решётки $(i,i^{2}$ по модулю $n)$ для $0\leqslant i<n$ не содержит трёх коллинеарных точек. Если $n$ является простым числом, можно осуществить такое построение для решётки $p\times p$ , содержащейся в решётке $n\times n$ , где $p$ является наибольшим простым числом, меньшим $n$ . Поскольку интервалы между простыми числами много меньше самих простых чисел, $p$ будет всегда близко к $n$ , так что этот метод может быть использован, чтобы поместить $n-o(n)$ точек на $n\times n$ решётке при условии, что никакие три точки не коллинеарны^[13].

Граница впоследствии была улучшена — Холл, Джексон, Садбери и Уилд^[14] показали, что в случае простого $n/2$ можно получить решение с $3(n-2)/2$ точками, размещая точки в копиях гиперболы $xy=k$ (по модулю $n/2$ ), где $k$ можно задать произвольным образом с ограничением, что оно не должно равняться нулю по модулю $n/2$ . Снова, для произвольного $n$ можно осуществить это построение для простого числа, близкого к $n/2$ , чтобы получить решение с ${\tfrac {3}{2}}n-o(n)$ точками^[14].

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

На решётке любого размера $n$ может быть размещено не более $2n$ точек, так как при размещении большего количества по принципу Дирихле какие-то три из них окажутся на какой-то горизонтальной линии решётки. Для $n\leqslant 46$ , известно, что эта тривиальная граница точна^[3].

Гипотетические границы

Хотя в точности $2n$ точек можно разместить в небольших решётках^[15], есть гипотеза, что для больших решёток существует существенно меньшая верхняя граница на число точек, которые можно разместить в решётке. Точнее, есть предположение, что максимальное число точек, которые могут быть размещены на решётке, не более чем сублинейно больше значения $cn$ при^[15] $c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1{,}874.$ После обнаружения ошибки в эвристических рассуждениях, приведших к данной гипотезе, Гай исправил ошибку и высказал предположение, что граница не может быть сублинейно лучше значения $cn$ для^[16] $c={\frac {\pi }{\sqrt {3}}}\approx 1{,}814.$

Приложения

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

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

Обобщения и варианты

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

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

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

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

Жадный алгоритм размещения

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

Более высокие размерности

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

В более высоких размерностях множества точек решётки, в которых нет трёх точек на прямой, получаемые путём выбора точек близ гиперсферы, используются для нахождения больших множеств Салема — Спенсера^[англ.], множеств целых чисел, не образующих арифметических прогрессий^[30]. Однако это не работает, если использовать ту же идею выбора точек, близких к окружности в двухмерном пространстве — этот метод находит точки, образующие выпуклый многоугольник, который удовлетворяет требованиям отсутствия трёх точек на одной прямой, но он слишком мал. Максимальный выпуклый многоугольник с вершинами на решётке $n\times n$ имеет только $O(n^{2/3})$ вершин^[31]. Задача множества колпаков^[англ.] рассматривает аналогичную проблему к проблеме «никакие три на прямой» в пространствах более высокой размерности, базирующихся на векторных пространствах над конечными полями^[32].

Тор

Другой вариант проблемы использует преобразование решётки в дискретный тор с помощью периодических граничных условий^[англ.], в которых левая сторона тора соединена с правой частью, а верхняя сторона соединена с нижней стороной. Это приводит к тому, что на косых линиях на решётке находится больше точек, а потому труднее выбрать точки с условием не более двух точек на прямой Эти расширенные прямые можно также интерпретировать как нормальные прямые через бесконечную решётку на евклидовой плоскости, взятые по модулю размерностей тора. Для тора на основе решётки $m\times n$ максимальное число точек, которые можно выбрать, чтобы никакие три точки не лежали на прямой, не превосходит $2\gcd(m,n)$ ^[33]. Если обе размерности одинаковы и являются простыми числами, невозможно разместить ровно по одной точке в каждой строке и столбце без формирования линейного числа коллинеарных троек^[34]. Изучалась также версия для тора высокой размерности^[35].

Примечания

↑ Brass, Moser, Pach, 2005.
↑ The Weekly Dispatch, 1900.
↑ ¹ ² ³ ⁴ Gardner, 1976.
↑ Dudeney, 1917.
↑ Craggs, Hughes-Jones, 1976.
↑ Kløve, 1978.
↑ Kløve, 1979.
↑ Anderson, 1979.
↑ Harborth, Oertel, Prellberg, 1989.
↑ Flammenkamp, 1992.
↑ ¹ ² Flammenkamp, 1998.
↑ ¹ ² Roth, 1951.
↑ Эрдёш не публиковал это наблюдение, оно появилось у Рота Roth, 1951.
↑ ¹ ² Hall, Jackson, Sudbery, Wild, 1975.
↑ ¹ ² Guy, Kelly, 1968.
↑ Как сообщил Пегг (Pegg, 2005). Обнаружение ошибки Пегг приписывает Габору Эллманну.
↑ Brass et al., 2007.
↑ Wood, 2005.
↑ Komlós, Pintz, Szemerédi, 1982.
↑ ¹ ² ³ Eppstein, 2018.
↑ Froese, Kanj, Nichterlein, Niedermeier, 2017.
↑ Payne, Wood, 2013.
↑ Adena, Holton, Kelly, 1974.
↑ Cooper, Pikhurko, Schmitt, Warrington, 2014.
↑ Aichholzer, Eppstein, Hainzl, 2023.
↑ ¹ ² Pór, Wood, 2007.
↑ Pach, Thiele, Tóth, 1998.
↑ Dujmović, Morin, Wood, 2005.
↑ Di Giacomo, Liotta, Meijer, 2005.
↑ Elkin, 2011.
↑ Jarník, 1926.
↑ Klarreich, 2016.
↑ Misiak, Stępień, Szymaszkiewicz, Zwierzchowski, 2016.
↑ Cooper, Solymosi, 2005.
↑ Ku, Wong, 2018.

Литература

Michael A. Adena, Derek A. Holton, Patrick A. Kelly. Some thoughts on the no-three-in-line problem // Combinatorial Mathematics: Proceedings of the Second Australian Conference (University of Melbourne, 1973) (англ.) / Derek A. Holton. — 1974. — Vol. 403. — P. 6–17. — (Lecture Notes in Mathematics). — doi:10.1007/BFb0057371.
Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl. Geometric dominating sets – a minimum version of the No-Three-In-Line Problem (англ.) // Computational Geometry. — Elsevier, 2023. — January (vol. 108). — doi:10.1016/j.comgeo.2022.101913.
David Brent Anderson. Update on the no-three-in-line problem (англ.) // Journal of Combinatorial Theory. — 1979. — Vol. 27, iss. 3. — P. 365–366. — doi:10.1016/0097-3165(79)90025-6.
Peter Brass, Eowyn Cenek, Christian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings (англ.) // Computational Geometry^[англ.]. — 2007. — Vol. 36, iss. 2. — P. 117–130. — doi:10.1016/j.comgeo.2006.05.006.
Peter Brass, William Moser, János Pach. Section 10.1: Packing lattice points in subspaces // Research Problems in Discrete Geometry (англ.). — Springer, New York, 2005. — P. 417–421. — ISBN 978-0-387-29929-7.
Alec S. Cooper, Oleg Pikhurko, John R. Schmitt, Gregory S. Warrington. Martin Gardner's minimum no-3-in-a-line problem (англ.) // American Mathematical Monthly. — 2014. — Vol. 121, iss. 3. — P. 213–221. — doi:10.4169/amer.math.monthly.121.03.213. — arXiv:1206.5350. — JSTOR 10.4169/amer.math.monthly.121.03.213.
Joshua N. Cooper, József Solymosi. Collinear points in permutations (англ.) // Annals of Combinatorics. — 2005. — Vol. 9, iss. 2. — P. 169–175. — doi:10.1007/s00026-005-0248-4. — arXiv:math/0408396.
Craggs D., Hughes-Jones R. On the no-three-in-line problem (англ.) // Journal of Combinatorial Theory. — 1976. — Vol. 20, iss. 3. — P. 363–364. — doi:10.1016/0097-3165(76)90030-3.
Henry Dudeney^[англ.]. 317. A puzzle with pawns // Amusements in Mathematics (англ.). — Edinburgh: Nelson, 1917. — P. 94. Решение p. 222. Первоначально изложено в лондонской газете Tribune 7 ноября 1906.
- Задачу можно найти под номером 144 в книге Генри Э. Дьюдени. 200 знаменитых головоломок мира (англ.). — М.: ООО «Фирма «Издательство АСТ», 1999. — ISBN 5-237-02035-6.
Emilio Di Giacomo, Giuseppe Liotta, Henk Meijer. Computing straight-line 3d grid drawings of graphs in linear volume (англ.) // Computational Geometry: Theory and Applications^[англ.]. — 2005. — Vol. 32, iss. 1. — P. 26–58. — doi:10.1016/j.comgeo.2004.11.003.
Vida Dujmović, Pat Morin, David Wood. Layout of graphs with bounded tree-width (англ.) // SIAM Journal on Computing^[англ.]. — 2005. — Vol. 34, iss. 3. — P. 553–579. — doi:10.1137/S0097539702416141. — arXiv:cs/0406024.
Michael Elkin. An improved construction of progression-free sets (англ.) // Israel Journal of Mathematics. — 2011. — Vol. 184. — P. 93–128. — doi:10.1007/s11856-011-0061-1. — arXiv:0801.4310.
David Eppstein. Chapter 9: General position // Forbidden Configurations in Discrete Geometry (англ.). — Cambridge University Press, 2018. — P. 72–86.
Achim Flammenkamp. Progress in the no-three-in-line problem (англ.) // Journal of Combinatorial Theory. — 1992. — Vol. 60, iss. 2. — P. 305–311. — doi:10.1016/0097-3165(92)90012-J.
Achim Flammenkamp. Progress in the no-three-in-line problem, II (англ.) // Journal of Combinatorial Theory. — 1998. — Vol. 81, iss. 1. — P. 108–113. — doi:10.1006/jcta.1997.2829.
Vincent Froese, Iyad Kanj, André Nichterlein, Rolf Niedermeier. Finding points in general position (англ.) // International Journal of Computational Geometry & Applications. — 2017. — Vol. 27, iss. 4. — P. 277–296. — doi:10.1142/S021819591750008X. — arXiv:1508.01097.
Martin Gardner. Combinatorial problems, some old, some new and all newly attacked by computer (англ.) // Scientific American. — 1976. — October (vol. 235, iss. 4). — P. 131–137. — JSTOR 24950467.
Guy R. K., Kelly P. A. The no-three-in-line problem (англ.) // Canadian Mathematical Bulletin^[англ.]. — 1968. — Vol. 11, iss. 4. — P. 527–531. — doi:10.4153/CMB-1968-062-3.
Hall R. R., Jackson T. H., Sudbery A., Wild K. Some advances in the no-three-in-line problem (англ.) // Journal of Combinatorial Theory. — 1975. — Vol. 18, iss. 3. — P. 336–341. — doi:10.1016/0097-3165(75)90043-6.
Heiko Harborth, Philipp Oertel, Thomas Prellberg. No-three-in-line for seventeen and nineteen (англ.) // Discrete Mathematics. — 1989. — Vol. 73, iss. 1–2. — P. 89–90. — doi:10.1016/0012-365X(88)90135-5.
Vojtěch Jarník. Über die Gitterpunkte auf konvexen Kurven (нем.) // Mathematische Zeitschrift^[англ.]. — 1926. — Bd. 24, H. 1. — S. 500–518. — doi:10.1007/BF01216795.
Erica Klarreich. Simple Set Game Proof Stuns Mathematicians (англ.) // Quanta. — 2016. — May 31.
Torleiv Kløve. On the no-three-in-line problem. II (англ.) // Journal of Combinatorial Theory. — 1978. — Vol. 24, iss. 1. — P. 126–127. — doi:10.1016/0097-3165(78)90053-5.
Torleiv Kløve. On the no-three-in-line problem. III (англ.) // Journal of Combinatorial Theory. — 1979. — Vol. 26, iss. 1. — P. 82–83. — doi:10.1016/0097-3165(79)90055-4.
Komlós J., Pintz J., Szemerédi E. A lower bound for Heilbronn's problem (англ.) // Journal of the London Mathematical Society. — 1982. — Vol. 25, iss. 1. — P. 13–24. — doi:10.1112/jlms/s2-25.1.13.
Donald E. Knuth. Answer to exercise 242 // The Art of Computer Programming, Fascicle 1b: A Draft of Section 7.1.4: Binary Decision Diagrams (англ.). — 2008. — P. 130.
- Дональд Э. Кнут. Искусство программирования (рус.). — Москва, Санкт-Петербург, Киев: ООО «И. Д. Вильямс», 2013. — Т. 4, А – Комбинаторные алгоритмы Часть 1. — С. 479 (упражнение 242). — ISBN 978-5-8459-1744-7 Б Б К 3 2 . 9 7 3 . 2 6 - 0 1 8 . 2 . 75.
The Weekly Dispatch. — 1900. — Вып. April 29, May 13. как процитировано у Кнута
Cheng Yeaw Ku, Kok Bin Wong. On no-three-in-line problem on m-dimensional torus (англ.) // Graphs and Combinatorics. — 2018. — Vol. 34, iss. 2. — P. 355–364. — doi:10.1007/s00373-018-1878-8.
Aleksander Misiak, Zofia Stępień, Alicja Szymaszkiewicz, Lucjan Szymaszkiewicz, Maciej Zwierzchowski. A note on the no-three-in-line problem on a torus (англ.) // Discrete Mathematics. — 2016. — Vol. 339, iss. 1. — P. 217–221. — doi:10.1016/j.disc.2015.08.006. — arXiv:1406.6713.
János Pach, Torsten Thiele, Géza Tóth. Three-dimensional grid drawings of graphs // Graph Drawing, 5th Int. Symp., GD '97 (англ.). — Springer-Verlag, 1998. — Vol. 1353. — P. 47–51. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-63938-1_49.
Michael S. Payne, David R. Wood. On the general position subset selection problem (англ.) // SIAM Journal on Discrete Mathematics. — 2013. — Vol. 27, iss. 4. — P. 1727–1733. — doi:10.1137/120897493. — arXiv:1208.5289.
Ed Pegg Jr. Chessboard Tasks (англ.). — Mathematical Association of America, 2005. — April.
Attila Pór, David R. Wood. No-three-in-line-in-3D (англ.) // Algorithmica^[англ.]. — 2007. — Vol. 47, iss. 4. — P. 481. — doi:10.1007/s00453-006-0158-9.
Roth K. F. On a problem of Heilbronn (англ.) // Journal of the London Mathematical Society. — 1951. — Vol. 26, iss. 3. — P. 198–204. — doi:10.1112/jlms/s1-26.3.198.
David R. Wood. Grid drawings of k-colourable graphs (англ.) // Computational Geometry: Theory and Applications^[англ.]. — 2005. — Vol. 30, iss. 1. — P. 25–28. — doi:10.1016/j.comgeo.2004.06.001.

Ссылки

Flammenkamp, Achim. The No-Three-in-Line Problem (англ.). Дата обращения: 4 сентября 2024. Архивировано 3 июля 2002 года.
Weisstein, Eric W. No-Three-in-a-Line-Problem (англ.) на сайте Wolfram MathWorld.

[_3a80094bf19a4653-1] Brass, Moser, Pach, 2005.

[_ee499c90537879cd-2] The Weekly Dispatch, 1900.

[_dd64369712a0a229-3] ¹ ² ³ ⁴ Gardner, 1976.

[_145b5ab14bb7d835-4] Dudeney, 1917.

[_5d6125d01896c6ed-5] Craggs, Hughes-Jones, 1976.

[_51f5940b6b1fa4f3-6] Kløve, 1978.

[_9457cd98e4cd127e-7] Kløve, 1979.

[_85589fb98118837d-8] Anderson, 1979.

[_2a884549a138590c-9] Harborth, Oertel, Prellberg, 1989.

[_f8d7686f8bcb7d69-10] Flammenkamp, 1992.

[_8488df7288b165d3-11] ¹ ² Flammenkamp, 1998.

[_5e07b542dafcff16-12] ¹ ² Roth, 1951.

[13] Эрдёш не публиковал это наблюдение, оно появилось у Рота Roth, 1951.

[_89def660ca62ccb7-14] ¹ ² Hall, Jackson, Sudbery, Wild, 1975.

[_df457a7757c5ebef-15] ¹ ² Guy, Kelly, 1968.

[16] Как сообщил Пегг (Pegg, 2005). Обнаружение ошибки Пегг приписывает Габору Эллманну.

[_3d7abcdd54a44ce7-17] Brass et al., 2007.

[_121acfb58635f9e3-18] Wood, 2005.

[_ca3171306ecbcd01-19] Komlós, Pintz, Szemerédi, 1982.

[_04b29f0c98095008-20] ¹ ² ³ Eppstein, 2018.

[_8ffb33e2f4f00c57-21] Froese, Kanj, Nichterlein, Niedermeier, 2017.

[_2cedd49b08435493-22] Payne, Wood, 2013.

[_a77233993bd506be-23] Adena, Holton, Kelly, 1974.

[_fc8faa026ce1b64e-24] Cooper, Pikhurko, Schmitt, Warrington, 2014.

[_48f883fc9bab8375-25] Aichholzer, Eppstein, Hainzl, 2023.

[_f3be0e9547bd5851-26] ¹ ² Pór, Wood, 2007.

[_abc4d0648c16e18b-27] Pach, Thiele, Tóth, 1998.

[_2054fcec9accfd7b-28] Dujmović, Morin, Wood, 2005.

[_b4eae67c17f9ef8d-29] Di Giacomo, Liotta, Meijer, 2005.

[_0a5f87252de9ea9a-30] Elkin, 2011.

[_4893b1885a773767-31] Jarník, 1926.

[_654bb5aa61d2728b-32] Klarreich, 2016.

[_119ea0a6bc9624f1-33] Misiak, Stępień, Szymaszkiewicz, Zwierzchowski, 2016.

[_f791c51f779fd5d5-34] Cooper, Solymosi, 2005.

[_6235376d24c1edfd-35] Ku, Wong, 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]