Constructing $2n$ points with no three collinear points

Question

For any integer $n \ (n \geq 2)$, is there a way to construct $2n$ points $(x_1, y_1), (x_2, y_2), \cdots, (x_{2n}, y_{2n})$ with following conditions?

• For every integer $i \ (1 \leq i \leq 2n)$, $x_i$ and $y_i$ are integers between $1$ and $n$
• Every points are different, i.e. for every integers $1 \leq i < j \leq 2n$, it satisfies $x_i \neq x_j$ or $y_i \neq y_j$
• For every integers $i, j, k \ (1 \leq i < j < k \leq 2n)$, $(x_i, y_i), (x_j, y_j), (x_k, y_k)$ are not collinear

Small-case examples:
If $n=2$, if points are $(1, 1), (1, 2), (2, 1), (2, 2)$, it satisfies all conditions.
If $n=3$, if points are $(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3)$, it satisfies all conditions.
If $n=4$, if points are $(1, 1), (1, 2), (2, 3), (2, 4), (3, 1), (3, 2), (4, 3), (4, 4)$, it satisfies all conditions.

Is there some construction for all $n$, including $n \geq 5$? If there are, how to construct?

Answer 1

It is an open problem to find a specific $n\gt 1$ where it is impossible to choose $2n$ points of an $n\times n$ grid with no three collinear. (By an obvious pigeonhole argument one can never get more than $2n$ points of the grid.)

The comments and references for OEIS A000769 give a summary of what is known about this problem, attributed to Henry Dudeney in 1917.

Solutions (with $2n$ points on an $n\times n$ grid, no three in a line) have been found for $n=2,\ldots,46$ and $n=48,50,52$, for which the Reader is referred to Achim Flammenkamp's web site The No-Three-in-Line Problem. Summary counts of known solutions for $n$, especially considering those with dihedral symmetries, are in this text table there. An illustration is used for $n=24$ with left-right symmetry:

These solutions were found by combinatorial search (a branch-and-bound algorithm) taking advantage of specified symmetries. Some constructive methods are known that provide less than $2n$ points for arbitrarily large $n$. P. Erdös noted that for prime $n$, the $n$ points $(x,x^2)\bmod n$ form a set with no three collinear points (because this is a quadratic "curve"). Later Hall, Jackson, Sudberry, and Wild (J. Comb. Th. Ser. A v. 18, 1975, pp. 336 - 341) extended this to construct $3n/2$ points with no three collinear when $n$ is twice a prime.

So we know that the maximum number of points we can feasibly choose in an $n\times n$ grid is between $(3n/2\; - \epsilon)$ and $2n$. Guy and Hall (1968) gave a heuristic argument and conjectured that as $n$ tends to infinity, the maximum number of points is asymptotic to $cn$ where $c=\pi/\sqrt{3}\approx 1.8138$.

See these notes from a talk by Nathan Kaplan (2016) for a sketch of those latter developments (around the middle of the presentation).

Answer 2

A solution for $n = 5$:

n = 5 
(1;3), (1;5), (2;2), (2;3), (3;4), (3;5), (4;1), (4;4), (5;1), (5;2)

 5: xx   
 4: x  x 
 3:    xx
 2:  xx  
 1:   x x
    -----
    12345

And another solution for $n=11$:

n = 11 
(1;1), (1;2), (2;5), (2;7), (3;4), (3;6), (4;9), (4;10), 
(5;1), (5;3), (6;4), (6;8), (7;9), (7;11), (8;2), (8;3), 
(9;6), (9;8), (10;5), (10;7), (11;10), (11;11)

11:          xx
10:     x x    
 9:      x x   
 8:  xx        
 7:         x x
 6:    x   x   
 5: x x        
 4:         xx 
 3:    x x     
 2:     x x    
 1: xx         
    -----------
    12345678901

The solutions were found using the following MiniZinc constraint solver model:

int: n = 11;
set of int: Range = 1..n;
set of int: N2 = 1..2*n;
% We assume/enforce 2 points per row
array[N2] of Range: x = [(i +1 ) div 2 | i in N2];
array[N2] of var Range: y;

% For every integer i (1≤i≤2n), xi and yi are integers between 1 and n
% ==> implicit constraint expressed by domain of decision variables

% All points are different, i.e. for every integer 1≤i<j≤2n, it satisfies xi≠xj or yi≠yj
constraint forall(i, j in N2 where j > i)(
  (x[i] != x[j]) \/ (y[i] != y[j])
);

% For all integers i,j,k (1≤i<j<k≤2n), (xi,yi),(xj,yj),(xk,yk) are not collinear
constraint forall(i, j, k in N2 where (i < j) /\ (j < k)) (
  %  https://www.urbanpro.com/gre-coaching/how-to-determine-if-points-are-collinear
  %  area of the triangle != 0  <==>  non collinear
  0 != (x[i]*y[j] - x[i]*y[k] - x[j]*y[i] + x[j]*y[k] + x[k]*y[i] - x[k]*y[j])
);

% Extra constraint to keep points sorted and speed-up search
constraint forall(i in 1..2*n-1) (
  (x[i+1] > x[i]) \/
  ((x[i+1] == x[i]) /\ (y[i+1] > y[i]))
);

solve satisfy;

function string: point(Range: i, Range: j) =
  if 0 == sum(k in N2)((fix(x[k]) == i) /\ (fix(y[k]) == j)) then " " else "x" endif;

output [ "n = " ++ show(n) ++ " "] ++ 
       [ (if i == 1 then "" else ", " endif) ++ "(" ++ show(x[i]) ++ ";" ++ show(y[i]) ++ ")" 
         | i in N2] ++
       [ if j == 1 then "\n" ++ show_int(2, n - i + 1) ++ ": " else "" endif ++
         point(n - i + 1, j) | i, j in Range] ++
       [ if i == 1 then "\n    -" else "-" endif | i in Range ] ++
       [ if i == 1 then "\n    1" else show(i mod 10) endif | i in Range ]
       ;