The no-three-in-line problem: 2N points in the N × N grid
A subset of the grid $[N]^2$ has at most $2N$ points if no three of its points are collinear, since each row holds at most two. Sets of $2N$ such points are known for every $N \le 60$ (up to $N = 60$ by Prellberg's 2026 computer search), and Hall, Jackson, Sudbery and Wild constructed sets of $(\frac32 + o(1))N$ such points for every $N$, which Green suspects is optimal.
Problem. How large can a subset of $[N]^2$ be if no three of its points are collinear? In particular, for all sufficiently large $N$, is it impossible to have $2N$ such points?
Source: Special cases go back to H. E. Dudeney (over a century ago); see R. K. Guy, Unsolved Problems in Number Theory, F4. Listed as Problem 72 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- collinear points, discrete geometry, lattice points, no-three-in-line problem
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{guy1968kelly,
author = {Guy, Richard K. and Kelly, Patrick A.},
title = {The no-three-in-line problem},
journal = {Canadian Mathematical Bulletin},
volume = {11},
number = {4},
pages = {527--531},
year = {1968},
doi = {10.4153/CMB-1968-062-3}
}
@article{hall1975advances,
author = {Hall, R. R. and Jackson, T. H. and Sudbery, A. and Wild, K.},
title = {Some advances in the no-three-in-line problem},
journal = {Journal of Combinatorial Theory, Series A},
volume = {18},
number = {3},
pages = {336--341},
year = {1975},
doi = {10.1016/0097-3165(75)90043-6}
}
@article{grebennikov2026kwan,
author = {Grebennikov, Alexandr and Kwan, Matthew},
title = {No-$(k+1)$-in-line problem for large constant $k$},
journal = {Bulletin of the London Mathematical Society},
volume = {58},
number = {10},
pages = {e70510},
year = {2026},
doi = {10.1112/blms.70510},
eprint = {2510.17743},
archivePrefix = {arXiv}
}
@misc{ghosal2026nok,
author = {Ghosal, Anubhab and Goenka, Ritesh and Grebennikov, Alexandr and Keevash, Peter and Kwan, Matthew and Pham, Huy Tuan},
title = {No-$(k+1)$-in-line problem for $k \geqslant 3$},
year = {2026},
eprint = {2607.05255},
archivePrefix = {arXiv}
}
@article{nagy2023extensible,
author = {Nagy, D{\'a}niel T. and Nagy, Zolt{\'a}n L{\'o}r{\'a}nt and Woodroofe, Russ},
title = {The extensible no-three-in-line problem},
journal = {European Journal of Combinatorics},
volume = {114},
pages = {103796},
year = {2023},
doi = {10.1016/j.ejc.2023.103796}
}
@misc{prellberg2026csp,
author = {Prellberg, Thomas},
title = {Constraint satisfaction programming for the no-three-in-line problem},
year = {2026},
eprint = {2602.07751},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 72; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00989, "The no-three-in-line problem: 2N points in the N × N grid", clopen.solutions.