About the problem
The no three-in-a-line problem asks for the maximum number of points that can be placed on an \(n \times n\) grid such that no three of them are in a line.
Since there are \(n\) possible \(x\)- and \(y\)- coordinate values, if there are more than \(2n\) points, then at least three of them lie on a horizontal or a vertical line by the pigeonhole principle. So \(2n\) is an upper bound for the no-three-in-a-line problem for all \(n\).
The upper bound of \(2n\) is known to be tight for \(n \leq 70\), and many of the tight constructions are from very recently. See a running list of progress here. The best known asymptotic construction, from 1975 by Hall, Jackson, Sudbery, and Wild, gives \((1.5-o(1))n\) points.
This problem asks for an infinite family of constructions of points on an \(n \times n\)-grid that improves on the \(1.5n\) asymptotic bound. In July 2026, the analogous no-\((k+1)\)-in-a-line problem was solved for \(k > 2\) (and shown to be equal to \(kn\)). But their argument does not apply to \(k=2\), i.e. the no-three-in-a-line problem, suggesting that improving on the no-three-in-a-line results may require a new idea.
The verifier checks, for a finite number of values for \(n\), that the submitted solution has more than \((1.5 + \varepsilon)n\) points, no three of which are in a line. Therefore, there is a risk that a solution is accepted even if it only achieves \(1.5n\) asymptotically, by generating a construction that achieves \(1.5n + c\) for some \(c\) which exceeds \(\varepsilon*n\) for the largest value of \(n\) that the verifier samples.
Prompt
Let G_n be the n x n grid of lattice points {1, 2, ..., n} x {1, 2, ..., n}.
A no-three-in-a-line set is a subset S of G_n such that no three points of S lie on a common straight line. Let t(n) be the maximum possible size of such a set.
The trivial upper bound is t(n) <= 2n (more than 2n points force three in some row).
Sets of size 1.5 * n - O(1) are classical, so it is the ratio 3/2 that is the barrier: it is not known whether t(n) / n can exceed 3/2 for arbitrarily large n. Your task is to beat that ratio, which means beating it by a constant factor -- shaving an additive constant off a 1.5 * n - O(1) construction leaves the ratio at 3/2 and does not count.
Concretely: give an algorithm that produces, for arbitrarily large n, a no-three-in-a-line set of MORE than 1.55 * n points.
Solution format:
* Write a Python script defining a function `solution(min_n: int) -> tuple[int, list[list[int]]]`.
* Given a lower bound `min_n`, `solution(min_n)` must return a pair `(n, points)` where:
- `n` is an integer with `min_n <= n <= 2 * min_n` (you may choose any such n; your family need not include every n),
- `points` is a list of `[x, y]` pairs of integers with `1 <= x <= n` and `1 <= y <= n`,
- the points are distinct,
- no three of the points are collinear, and
- `len(points) > 1.55 * n` (strictly).
* The verifier calls `solution(min_n)` for many increasing lower bounds `min_n`. The n you return must be STRICTLY INCREASING across these calls.
* Each call to `solution(min_n)` must complete within 1 minute when run on a typical laptop.
* Do not include any code at the file level. You may include a `main` block for testing, but it will not be executed by the verifier.
* An example showing the required format is provided in the file "/solution_example.py". (That example returns only a handful of points, far below the threshold; it is there to illustrate the interface, not to solve the problem.)