¿Cuántas líneas están definidas por puntos de la cuadrícula de 8x8 puntos?

Question

Tengo una tarea para formular el enfoque y calcular cuántas líneas diferentes se definen por los puntos en 8x8 cuadrícula (por lo que 2 o más puntos se encuentra en la línea). Los puntos están distribuidos uniformemente ([0,0], [0,1], ..., [1,0], [1,1], ..., [7,7]).

He intentado dividir en grupos, usar la simetría, pensar en ello como secuencias de números y luego usar la combinatoria pero siempre explota en un montón de combinaciones y obtengo resultados diferentes cada vez. ¿Puede alguien indicarme cómo abordar esta tarea?

Answer 1

EDIT: Encontrado A018808 $0, 0, 6, 20, 62, 140, 306, 536, \color{green}{938}, 1492, 2306$

Mis cuentas eran incorrectas más allá de 7x7.

Answer 2

Numerar los puntos de la red desde $1$ a $N$ . Cuenta el número de líneas que pasan por los puntos de la red $i$ y $j$ que no pasan por ningún punto de la red $k$ , $1 \le i \lt j \lt k \le N$ .

Evidentemente, esto no es más que una repetición del requisito original, y no aprovecha las simetrías de la red regular, ni la naturaleza combinatoria del problema.

---

Para una rejilla rectangular regular, me di cuenta de que hay un enfoque mucho mejor, al despertar esta mañana. (Tu subconsciente es tu amigo; ¡deja que haga todo el trabajo duro! :)

Empecemos por el caso más sencillo, una cuadrícula de 2×2. Ésta tiene seis líneas únicas: dos horizontales, dos verticales y dos diagonales. (La cuadrícula de 1×1 no tiene líneas porque no hay suficientes puntos, y las cuadrículas de una fila o una columna tienen exactamente una línea).

A continuación, averigua cuántas líneas adicionales obtienes al aumentar la anchura o la altura en una. Suponga que ya conoce el número de líneas de un $N \times K$ y averiguar el número de líneas únicas añadidas cuando $N$ se incrementa en uno. (Debido a las simetrías, este es el único caso que hay que averiguar).

Digamos que encuentras ese número en forma analítica, digamos $\tau(N, K)$ cuando el tamaño de la cuadrícula era $N \times K$ y $N$ se incrementa en uno; y $N, K \ge 2$ . La forma/dirección en que crezca la red no importa, y $\tau(N, K)$ es obviamente simétrica con respecto a $N$ y $K$ . Así, el número total de líneas es $$\bbox{ T(N, K) = \begin{cases} 0, & N \le 1, K \le 1 \\ 1, & N = 1 \text{ and/or } K = 1 \\ 6, & N = 2, K = 2 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2), & N \ge 3, K = 2 \\ \displaystyle 6 + \sum_{k=2}^{K-1} \tau(k,2), & N = 2, K \ge 3 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2) + \sum_{k=2}^{K-1} \tau(k,N), & N \ge 3, K \ge 3 \\ \end{cases} }$$

Queda la parte "difícil", $\tau(N, K)$ (pero sólo hay que tenerlo en cuenta para $N \ge 2$ , $K \ge 2$ a medida que el tamaño de la cuadrícula aumenta de $N \times K$ a $(N + 1) \times K$ ; para simplificar, vamos a suponer que crece una nueva columna, que $N$ es el número de columnas de la cuadrícula antigua, y $K$ es el número de filas).

Siempre hay al menos una línea añadida, la que va a lo largo de la nueva columna de puntos de la cuadrícula. Todas las demás líneas únicas nuevas $i$ tiene una pendiente $s_i \ne 0$ . Debido a las simetrías, encontrarás que para cada positivo $s_i$ hay una línea correspondiente con la misma pendiente pero negativa, y viceversa. Por lo tanto, $\tau(N, K) = 1 + 2 p(N, K)$ y sólo hay que contar las nuevas líneas únicas con pendiente positiva, $p(N, K)$ .

Una forma de definir $p(N, K)$ es como una suma, donde cada sumando indica si la línea es nueva: $$\bbox{ p(N, K) = \sum_{n=1}^N \sum_{k=1}^{K} \sum_{i=1}^K U\bigr((n, k), (N + 1, i)\bigr) }$$ donde $U\bigr((a, b), (c, d)\bigr)$ es 0 si la línea entre $(a,b)$ y $(c,d)$ pasa por cualquier punto de la red $(i, j)$ y 1 en caso contrario (por lo que dicha línea es nueva y única).

Para no encontrar la respuesta completa, me detendré aquí. (Más honestamente, aquí es donde me desperté, justo cuando mi subconsciente estaba murmurando algo sobre $U$ y utilizando los mayores denominadores comunes para encontrar si existe $j/i = h/w$ , a través de $j = i h / w$ o algo así).