No-three-in-line problem

Remarks

Henry Dudeney posed the problem in 1900. Each of the $n$ rows can contain at most $2$ chosen points, so by the pigeonhole principle at most $2n$ points can be chosen. The bound $2n$ is attained for all $n$ up to at least $46$, by solutions found with computer searches. For a prime $p$, the $p$ points $(x, x^2 \bmod p)$ with $0 \le x < p$ have no three in a line, an observation of Erdős. Indeed, three of them on a line would give three roots in the field $\F_p$ of a nonzero polynomial of degree at most $2$. Hall, Jackson, Sudbery and Wild refined such constructions in 1975. They showed that for every $\varepsilon > 0$ and all large $n$, at least $(3/2 - \varepsilon)n$ points can be chosen. It is conjectured that for large $n$ the maximum is strictly less than $2n$.