1968/10/01 by Richard K. Guy, Patrick A. Kelly · 10 citations
Engineering · Mathematics · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Mathematics #Combinatorics #Conjecture #Modulo #Integer (computer science) #Prime (order theory) #Line (geometry) #Prime factor #Discrete mathematics #Geometry
paper · pdf · doi:10.4153/cmb-1968-062-3
openalex publication_date 1968/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Let S n be the set of n 2 points with integer coordinates n (x, y), 1 ≤ x, y <n. Let f n be the maximum cardinal of a subset T of S n such that no three points of T are collinear. Clearly f n < 2n. For 2 ≤ n ≤ 10 it is known ([2], [3] for n = 8, [ 1] for n = 10, also [4], [6]) that f n = 2n, and that this bound is attained in 1, 1, 4, 5, 11, 22, 57, 51 and 156 distinct configurations for these nine values of n. On the other hand, P. Erdös [7] has pointed out that if n is prime, f n ≥ n, since the n points (x, x 2 ) reduced modulo n have no three collinear. We give a probabilistic argument to support the conjecture that there is only a finite number of solutions to the no-three-in-line problem. More specifically, we conjecture that