La construcción de $2n$ puntos sin tres puntos colineales

Question

Para cualquier entero $n \ (n \geq 2)$, hay un camino para la construcción de $2n$$(x_1, y_1), (x_2, y_2), \cdots, (x_{2n}, y_{2n})$, con las siguientes condiciones?

• Para cada entero $i \ (1 \leq i \leq 2n)$, $x_i$ y $y_i$ son enteros entre el $1$ $n$
• Todos los puntos son diferentes, es decir, para todos los enteros $1 \leq i < j \leq 2n$, satisface $x_i \neq x_j$ o $y_i \neq y_j$
• Para todos los enteros $i, j, k \ (1 \leq i < j < k \leq 2n)$, $(x_i, y_i), (x_j, y_j), (x_k, y_k)$ no son colineales

Pequeños ejemplos:
Si $n=2$, si los puntos son $(1, 1), (1, 2), (2, 1), (2, 2)$, cumple con todas las condiciones.
Si $n=3$, si los puntos son $(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3)$, cumple con todas las condiciones.
Si $n=4$, si los puntos son $(1, 1), (1, 2), (2, 3), (2, 4), (3, 1), (3, 2), (4, 3), (4, 4)$, cumple con todas las condiciones.

Hay algunas construcción de todas las $n$, incluyendo a $n \geq 5$? Si hay, cómo se construye?

Answer 1

Es un problema abierto para buscar un determinado $n\gt 1$ donde es imposible elegir a $2n$ puntos de una $n\times n$ cuadrícula con no hay tres colineales. (Por una evidente encasillar el argumento de que nunca se puede obtener más de $2n$ puntos de la cuadrícula.)

Los comentarios y referencias para OEIS A000769 dar un resumen de lo que se sabe acerca de este problema, que se atribuye a Henry Dudeney en 1917.

Soluciones (con $2n$ puntos en un $n\times n$ cuadrícula, no hay tres en una línea) se han encontrado para$n=2,\ldots,46$$n=48,50,52$, por lo que se remite al Lector a Achim Flammenkamp el sitio web de La No-Tres-en-Problema en la Línea. Cuentas de resumen de las soluciones conocidas para $n$, considerando especialmente aquellos con diedro simetrías, en este texto de la tabla. Una ilustración se utiliza para $n=24$ con simetría izquierda-derecha:

Estas soluciones fueron encontrados por la combinatoria de búsqueda (branch-and-bound algoritmo) de tomar ventaja de ciertas simetrías. Algunos métodos constructivos se sabe que proporcionan menos de $2n$ puntos por arbitrariamente grande,$n$. P. Erdös señaló que para el prime $n$, $n$ $(x,x^2)\bmod n$ forman un conjunto de tres puntos colineales (porque esta es una ecuación cuadrática "curva"). Más tarde Hall, Jackson, Sudberry, y Salvaje (J. Peine. Th. La Ser. Un v. 18, 1975, pp 336 - 341) se extiende la presente para construir $3n/2$ puntos con no hay tres colineales al $n$ es el doble de una prima.

Así que sabemos que el número máximo de puntos que nos pueden llevar a elegir en un $n\times n$ cuadrícula se entre $(3n/2\; - \epsilon)$$2n$. Chico y Hall (1968) dio un argumento heurístico y conjeturó que como $n$ tiende a infinito, el número máximo de puntos es asintótica a $cn$ donde $c=\pi/\sqrt{3}\approx 1.8138$.

Ver estas notas de una charla por Nathan Kaplan (2016) para un sketch de los últimos acontecimientos (alrededor de la mitad de la presentación).

Answer 2

Una solución para $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

Y otra solución para $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

Las soluciones que se encontraron con la siguiente MiniZinc solver de restricciones del modelo:

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 ]
       ;