Número de celdas que se cruzan con el segmento de línea que une$(0,0)$ y$(m,n)$

Question

Si $m,n \in \mathbb{N}$ . Deje $g(m, n)$ el número de células que la línea que une la $(m, n)$ $(0, 0)$recortes en la región de $0 \le x \le m$ and $0 \le y ≤ $ n.

Por ejemplo, $g(1, 1)$ $1$ debido a que la línea que une la $(1, 1)$ y $(0, 0)$ recortes de una sola célula. Del mismo modo $g(2, 1)$ $2$ e $g(3, 2) = 4$.

Encontrar $g(343, 56)$.

Estoy tratando de derivar una fórmula para cualquier $g(m,n)$. Me di cuenta de que para $m=n$ la respuesta es $m$ pero para $m \neq n$ la respuesta parece ser $(m+n-1)$ en general, pero esto no vale para todos. Alguna idea de cómo generalizar $m \neq n$ restricción?

Answer 1

Si${\rm gcd}(m,n) = d \neq 1$, puede decir que$g(m,n) = d \cdot g(\frac{m}{d},\frac{n}{d})$ como la línea se puede dividir en$d$ partes, cada una comenzando en$(0,0)$ y terminando en$(\frac{m}{d},\frac{n}{d})$. Sin embargo, si${\rm gcd}(m,n) = 1$ está caminando en un rectángulo de$m \times n$, empezando por la esquina inferior izquierda, terminando en la esquina superior derecha, y solo moviéndose hacia arriba o hacia la derecha. Esto requiere exactamente$m + n - 1$% de cuadrados. Entonces, si$d = {\rm gcd}(m,n)$, entonces

ps

En particular,$$g(m,n) = d \cdot \left(\frac{m}{d} + \frac{n}{d} - 1\right) = m + n - d$, entonces${\rm gcd}(343,56) = 7$.

Answer 2

Dejar $r = {\rm gcd}(m,n)$. El segmento de línea de$(0,0)$ a$(m,n)$ cuts$m-1$ líneas de celosía vertical y$n-1$ horizontales (sin incluir las de los puntos finales), pero tiene$r-1$ intersecciones de líneas horizontales y verticales, entonces$g(m,n) = (m-1) + (n-1) - (r-1) + 1 = m + n - r$.

Answer 3

Es sólo $m+n-1$ si $m$ $n$ son relativamente primos. Si $m$ $n$ son primos relativos, entonces la única entramado de puntos que el segmento de línea entre el $(0,0)$ $(m,n)$ touch son los dos puntos de sí mismos. Ya que nunca toca otra red punto, se debe cruzar $m$ plazas en la dirección horizontal y $n$ plazas en la dirección vertical, pero esta doble cuenta uno de los cuadrados (la parte superior derecha más uno) por lo que se debe de tirar de él hacia fuera.

Si $m$ $n$ no son primos relativos, entonces asumir que $(m,n)=d$. Nuestro segmento de línea ahora de la cruz a través de $(0,0)$ $d$ adicional de celosía puntos. Por lo tanto, tenemos $d$ bloques de tamaño $(m/d,n/d)$. Desde $m/d$ $n/d$ son relativamente primos, dentro de cada bloque cortamos $m/d+n/d-1$ plazas, así que nuestra solución final es $d(m/d+n/d-1) = m+n-d$.