Dados dos puntos A y B en el plano XY, ¿cuál es el número de puntos en el segmento AB que tienen coordenadas x e y como número entero?

Answer 1

Primero, permítanme comenzar definiendo un punto de red, como se usa en la publicación vinculada. Un punto de red es un punto para el cual las coordenadas x e y son enteros.

Ahora, la fórmula es aplicable solo si A y B son puntos de la red.

Veamos cómo llegamos a la solución. Primero observe lo siguiente:

1) La respuesta es independiente de la traducción por una cantidad entera en la dirección x o y. Es decir, el no. de puntos de red entre (2, 5) y (7, 25) es lo mismo que entre (3, 1) y (8, 21). Esto se puede ver de la siguiente manera: imagine que todo el plano xy consiste en una matriz 2D infinita de puntos reticulados. AB es una línea que une dos de estos puntos. El origen se elige arbitrariamente como uno de los puntos en la matriz 2D. La elección de este origen determina las coordenadas de A y B, pero cualquiera que sea el origen que elija, la línea AB y el no. de puntos de celosía entre ellos siguen siendo los mismos.

2) Luego, usando un argumento similar al anterior, si voltea la línea horizontal o verticalmente, la respuesta sigue siendo la misma.

Entonces, si la línea original era AB con [matemáticas] A \ equiv (ax, ay) [/ matemáticas] y [matemáticas] B \ equiv (bx, by) [/ matemáticas], entonces, sin pérdida de generalidad, consideramos un línea PQ con Q en el origen y P en el primer cuadrante, de modo que las coordenadas de P sean [matemáticas] (px, py) \ equiv (| ax – bx |, | ay – por |) [/ matemáticas].

Ahora [math] px [/ math] y [math] py [/ math] son ​​enteros, y también lo son sus factores. Si divide PQ en partes [matemática] k [/ matemática], cada uno de los puntos límite tendrá coordenadas enteras si [matemática] px [/ matemática] y [matemática] py [/ matemática] son ​​divisibles por [matemática] k [/matemáticas]. Entonces, ¿cuál es el máximo no. ¿De qué partes puede dividir la línea de manera que todos los puntos de límite intermedios sean puntos de red? Claramente, el MCD de [math] px [/ math] y [math] py [/ math].

El + 1 aparece si incluye A y B en el recuento. Este bit es fácil de ver con un simple ejemplo.

Answer 2

Primero, veamos con qué frecuencia aparecen los puntos de la red. Como resultado, la respuesta implica la pendiente. Encuentra la pendiente y simplifica la fracción. Si es un número entero como 1 o 2, déjelo como 1/1 o 2/1. Suponiendo que comience en un punto de red, cada vez que aumente el valor de y con el numerador y modifique el valor de x en consecuencia, estará en el siguiente. Lo mismo es cierto para el denominador y el valor x. ¿Por qué? Es por la definición de pendiente.

Si aumenta el valor y por el numerador, el valor x aumentará por el numerador y viceversa. Cuando simplificó la pendiente, encontró los valores más pequeños en los que esto es cierto y ambos números son enteros. Y, como sabemos, un número entero más un número entero es un número entero. Esto es lo que quieres. Más pequeño y tendríamos valores no enteros, más grande y podríamos perder algunos puntos.

Para simplificar la fracción, todo lo que debe hacer es dividir arriba y abajo por su MCD. El numerador es (ay-by) y el denominador es (ax-bx), por lo tanto, la frecuencia con la que aparecen los puntos de red es cada unidad abs (ax-bx) / GCD ((ay-by), (ax, bx)) a lo largo de las eje x o cada abs (ay-by) / GCD ((ay-by), (ax, bx)) a lo largo del eje y. Cabe señalar que no es necesario agregar los abdominales porque MCD (a, b) = MCD (-a, -b) = MCD (-a, b) = MCD (ab).

Ahora que sabemos con qué frecuencia aparecen los puntos de la red, podemos encontrar el número de puntos de la red en el segmento de línea. Hágalo, tome el número de unidades a lo largo del eje y que se encuentran entre los dos puntos, abs (ay-by), y divida por la frecuencia para el eje y o el número de unidades a lo largo del eje x-abs ( ax-bx) – y divídalo por la frecuencia en el eje x. Luego agrega uno para tener en cuenta el hecho de que esto dejará de lado uno de sus dos puntos originales. De cualquier manera, encontrarás que se simplifican a la ecuación que tienes (sin los abdominales innecesarios).

Espero haber explicado esto correctamente. Señale cualquier error que pueda haber cometido y pregunte si necesita alguna aclaración.