¿Cómo podemos contar el número de triángulos no degenerados con coordenadas enteras en un rectángulo awxh?

Este cálculo de Ignacio Larrosa Cañestro da

[matemáticas] \ frac {(w ^ 3 – w) (h ^ 3 – h)} {6} – {} [/ matemáticas]
[matemáticas] 2 \ sum_ {k = 2} ^ h \ sum_ {j = 2} ^ w [/ matemáticas] [matemáticas] (w – j + 1) (h – k + 1) \ gcd \ {k – 1 , j – 1 \} [/ matemáticas].

De: “Ignacio Larrosa Cañestro”
Asunto: RE: Tablero de damas.
Fecha: dom, 22 de octubre de 2000 18:48:25 +0200
Grupos de noticias: sci.math
Resumen: [falta]

Para una cuadrícula de 4 * 4, los cálculos son fáciles:

Peine (16, 9) = 560 tríadas de puntos

Hay 10 líneas rectas con cuatro puntos: 4 verticales, 4
horizontales y 2 diagonales principales. Hay ara 3 tríadas (es decir, peine (4, 3)) de
puntos en cada uno de ellos -> 40

Además, las cuatro diagonales (2 de las que se indican a continuación) cierran el
Las diagonales también contienen 3 puntos.

Luego, hay 44 triadas de puntos colineales, y el número de triángulos
es 560 – 44 = 516

  * * * *
      / /
 * * * *
  / /
 * * * *
      / /
 * * * *

En general, sea B (m, n) el número de triángulos en una cuadrícula de m * n puntos.

Sea C (j, k) el número de triángulos en una cuadrícula de j * k puntos que no pueden ser
poner en una cuadrícula de j ‘* k’ puntos si j ‘<j o k' <k.

Entonces,

B (m, n) = Suma (Suma ((m-j + 1) (n-k + 1) C (j, k), j, 2, m), k, 2, n)

porque en una cuadrícula de m * n puntos podemos poner una cuadrícula de j * k puntos de
(m-j + 1) (n-k + 1) formas; sin gires, la cuadrícula aj * k conectada 90º es una cuadrícula ak * j.

Bueno, C (j, k) tiene tres componentes:

i) Triángulos con dos vértices en los extremos de una diagonal. El tercero
Vertix puede ser cualquiera que no esté en diagonal. Hay ara entonces 2 (j * k – mcd (j-1,
k-1) -1), porque hay dos diagonales y hay ara gcd (k-1, j-1) + 1
puntos en cada uno de entonces.

ii) Triángulos con dos vértices en los extremos de un lado. El tercer vértice
Puede ser cualquiera dentro (sin extremos) del lado opuesto. Hay 2 ((j-2) +
(k-2)).

iii) Triángulos con un vértice en un vértice P de la cuadrícula y los otros dos
vértices dentro de los lados no concurrentes con P. Hay 4 (j-2) (k-2).

Ponemos todo junto y con algo de trabajo algebraico, obtenemos

B (m, n) = (m ^ 3-m) (n ^ 3-n) / 6 – 2 · Suma (Suma ((m-j + 1) (n-k + 1) · mcd (k-1 , j-1),
j, 2, m), k, 2, n)

Esto me recuerda los problemas del Proyecto Euler, por lo que no te robaré el placer de resolverlo.

El “cómo” que funciona para mí es calcular los resultados para los casos más simples y luego buscar patrones que conduzcan a una fórmula que describa el patrón,

Tienes (w + 1) * (h + 1) vértices posibles para los triángulos, por lo tanto ((w + 1) * (h + 1)) ^ 3 triángulos posibles, sin tener en cuenta los casos degenerados (los tres en un punto , o en una línea) y duplicados.

Esperemos que esto ayude a pasar de WTF a través de una serie de momentos WTF / LOL a un Ahhhhhhhhhh final.