Número máximo de puntos que puedes poner en la parrilla $ n\times m$ ¿sin equidistancia?

Question

Supongamos que tenemos una red de $n\times m$ puntos. y la distancia entre dos filas o dos columnas es de 1 ( unidad ). Tengo un par de preguntas relacionadas con esta cuadrícula

1. ¿Cuál es la lista de posibles longitudes entre puntos?

2. ¿Cuál es el número máximo de puntos que no tienen equidistancia entre ningún par?

   • Para la pregunta número uno, sé que si tenemos tenemos $n \times m$ por lo que tenemos una longitud de tamaño $1,2 \dots \mbox{max}\{m,n\}$ en adicción a esto tenemos $\sqrt{2},\sqrt{5}$ y algunos otros. pero me interesa toda esta distancia.
   • Para la pregunta número 2 intuitivamente parece que para $n\times n$ caso que el punto máximo sin equidistante es n.

Tengo la sensación de que esto se ha estudiado en algunos libros, pero no estoy seguro de dónde o cómo responder al caso general de este problema. se agradecería cualquier pista y/o respuesta.

Hay solución de $5 \times 4$ por ejemplo esto es dos de la solución de la misma ( hay 5 puntos no equidistantes):-

Referencia:- He encontrado este problema desde el twitter y lo puedes encontrar aquí .

Answer 1

Las longitudes al cuadrado son de la forma $i^2 + j^2$ para $i \in [0,n]$ y $j \in [0,m]$ asumiendo (sin pérdida de generalidad) que $n \ge m$ podemos considerar sólo los casos en los que $i \ge j$ de los cuales hay $$(m+1)(n-m)+\frac{1}{2}(m+1)(m+2)=\frac{1}{2}(m+1)\left(m+2(n-m+1)\right).$$ Por otra parte, la colocación de $k$ puntos crea $k(k+1)/2$ pares, por lo que si todos estos pares deben tener distancias distintas, $$ k(k+1) \le (m+1)\left(m + 2(n-m+1)\right). $$ Así que para $n=m$ esto implica $k \le m+1$ y en general $$ k \le \sqrt{(m+1)\left(m + 2(n-m+1)\right)}. $$

Un límite más estricto, al menos en el límite de grandes $n$ La mejora de la estimación del número de distancias distintas en la cuadrícula. Sabemos que el número de enteros positivos menores que $2n^2+1$ que son la suma de dos cuadrados es $O\left(n^2 / \sqrt{\log n}\right)$ (véase el Constante de Landau-Ramanujan ); es decir, crece más lentamente que $n^2$ . Para $n=m$ entonces, la tasa de crecimiento de $k$ es necesariamente en $O\left(n / \sqrt[4]{\log n}\right)$ . Así que $k=n$ no es correcto: de hecho, $k/n \rightarrow 0$ para grandes $n$ .