¿Hay alguna solución elemental para este problema en el intervalo de color?

Question

El problema es el siguiente.

Suponga $m,n$ son dos coprime de los números impares, considere el intervalo de $[0,mn]$. Cortamos el intervalo de $m,2m,\ldots,(n-1)m$ e $n, 2n,\ldots, (m-1)n$ a $m+n-1$ piezas de pequeños intervalos. Y hemos de color de izquierda a derecha en blanco y negro periódicamente y negro primero. La pregunta es para mostrar $$(\textrm{the length of black})-(\textrm{the length of white})=1$$ For example, if $m=3,n=5$, $$\begin{array}{c*{31}}0 &&&&&& 3 &&&&&& 6 &&&&&& 9 &&&&&& 12 &&&&&& 15 \\ \mid & \blacksquare && \blacksquare &&\blacksquare &\mid & \square && \square & \mid & \blacksquare & \mid & \square&& \square&& \square &\mid & \blacksquare &\mid & \square&& \square&\mid & \blacksquare&& \blacksquare&& \blacksquare & \mid \\ 0 &&&&&&&&&& 5 &&&&&&&&&& 10 &&&&&&&&&& 15\end{matriz} $$The length of black is $8$ and the length of white is $7$.

En mi blog, he presentado dos "analítica" de las soluciones, que son tanto debido a Liu Ben, utilizando el truco de sumas exponenciales. Ellos son tan agradables en el sentido de "analítica".

Al final del post, se me ocurrió una "primaria" solución quiero explicar más precisamente aquí.

Considere la posibilidad de una mesa de billar de tamaño $m\times n$, e hirió al billar desde una de las esquinas en $45^{\circ}$. Cada vez que la pelota knockes el límite, cambia su color. Entonces $$(\textrm{the length of black interval})=\sqrt{2}\times (\textrm{the length of orbit of black ball})\qquad {(*)}$$ and $$(\textrm{the length of white interval})=\sqrt{2}\times (\textrm{the length of orbit of white ball})\qquad {(**)}$$ So it suffices to count the length of the grid at the direction of $\diagup$ and $\diagdown$, que no es difícil de calcular.

Pero en esta solución, no es fácil explicar por qué $(*)$ e $(**)$ se mantiene, a pesar de que sabemos lo de "experiencia de vida". Y creo que puede haber algo más elementales método para resolver este problema. Así que mis preguntas son

• ¿Hay algún primaria soluciones a este problema?
• Hay alguna "estricto proceso" para el billar problema ?
• Por otra parte, aunque he aprendido a no más de 1 boca hace, creo que es tan genio que debe ser clásico y descubierto por los antiguos. Entonces, ¿hay alguna referencia para este problema ?

Answer 1

Dibujar el cuadrado grande $Q:=[0,nm]\times[0,mn]$ en el número entero de celosía. Dibujar $n-1$ divisores verticales horizontalmente $m$ aparte y $m-1$ divisores horizontales verticalmente $n$ aparte. El cuadrado de $Q$ se divide luego en $nm$ rectángulos $R_{jk}$, cada uno compuesto de $mn$ celosía plazas. Deje $\ell$ ser la diagonal de $Q$ conectar $(0,0)$ con $(nm,mn)$. Esta $\ell$ se divide en $n$ a partes iguales por los divisores verticales y en $m$ a partes iguales por los divisores horizontales. Por lo tanto, podemos considerar a $\ell$ como una copia de la larga línea horizontal en la primera figura de la pregunta. Siempre que $\ell$ cruza una línea divisoria que entra en una nueva rectángulo $R_{jk}$. Estos $m+n-1$ rectángulos son de color rojo en la figura. Tenga en cuenta que además de la $\ell$ es una diagonal de exactamente $nm$ unidad de plazas de la red.

Ahora podemos copiar estos rectángulos rojo junto con las piezas de $\ell$ en ellos en un nuevo $(m\times n)$-rectángulo $R$. Podemos entonces ver a una familia de $45^\circ$-segmentos de $\sigma_i$ en $R$. Mirando en esta segunda figura es todavía posible seguir el original $\ell$: cada vez que un $\sigma_i$ golpea una línea límite $e\subset R$ el siguiente segmento en el original $\ell\subset Q$ comienza en el punto correspondiente en el paralelo borde de $e'\subset R$, hasta que por fin llegamos a $(m,n)$. De ${\rm gcd}(m,n)=1$ se deduce que los segmentos de $\sigma_i$ son distintos, y como ellos hacen exactamente $mn$ unidad de cuadrados de las diagonales se obtiene la imagen de la derecha abajo.

Con el fin de discutir el colorante de la $\sigma_i$ color de la unidad de plazas de $R$ tablero de ajedrez como con cuadrados negros en los vértices de $R$. Desde $m$ e $n$ son impares resulta que el $\sigma_i$ negro a través de la unidad de plazas será automáticamente de color negro y el $\sigma_i$ a través de la blanco de la unidad de plazas será de color blanco. Ahora hay uno más cuadrado negro que hay en el cuadrado blanco, y hemos terminado.

Answer 2

Aquí está una manera más formal, la realización de la bola de billar argumento.

Escribir una secuencia de $mn$ pares ordenados donde:

• la primera coordenada primer lugar, sigue la secuencia de $1, 2, \dots, m$ , a continuación, la secuencia de $m, m-1, \dots, 1$ , a continuación, sigue la alternancia de estas dos secuencias.
• la segunda coordenada primer lugar, sigue la secuencia de $1, 2, \dots, n$ , a continuación, la secuencia de $n, n-1, \dots, 1$ , a continuación, sigue la alternancia de estas dos secuencias.

Intuitivamente, un par ordenado $(x,y)$ en la $i^{\text{th}}$ posición significa que en el $i^{\text{th}}$ paso, la bola de billar es atravesar la plaza en las coordenadas $(x,y)$.

Hemos color de un par ordenado $(x,y)$ negro si $x+y$ es incluso en blanco y si $x+y$ es impar. A continuación, podemos ver que los pares ordenados cambiar de color, precisamente en los puntos donde la primera secuencia $m, m$ o $1,1$, y en los puntos donde la segunda secuencia $n, n$ o $1,1$. Estos son los puntos donde la bola de billar rebotes, y también los puntos donde vamos a partir de un intervalo a otro.

Así que para obtener el resultado, tenemos que mostrar que cada par $(x,y) \in \{1,2,\dots,m\} \times \{1,2,\dots,n\}$ aparece exactamente una vez: que la bola de billar pasa por encima de cada cuadrado de la cuadrícula. Esto se puede hacer, pero es un poco molesto.

(Tendríamos que contar el número de negros pares en blanco y pares en esta red. Puedo hacer esto más adelante.)

---

El siguiente enfoque es un simple argumento a lo largo de las mismas líneas. Anotar la secuencia $(i \bmod m, i \bmod n)$ para $i=0,1,\dots,mn-1$. Una vez más, el color de un par ordenado $(x,y)$ negro si $x+y$ es incluso en blanco y si $x+y$ es impar.

(Esto corresponde a la "tele" bola de que, cuando se llega a un borde de la mesa, te teletransporta a la orilla opuesta y continúa moviéndose en la misma dirección.)

Ahora sólo tenemos que demostrar tres cosas:

En primer lugar, el color de los pares ordenados en la secuencia que se describe exactamente los colores de los intervalos. Esto es debido a que $(i \bmod m, i \bmod n)$ e $(i+1\bmod m, i+1\bmod n)$ tienen el mismo color si no hay "llevar": si añadimos $1$ a ambas coordenadas. La paridad solo cambia cuando se pasa de $m-1$ a $0$ en la primera coordenada o $n-1$ a $0$ en el segundo.

Segundo, cada posible par ordenado $(x,y)$ ocurre exactamente una vez. Este es precisamente el enunciado del Teorema del Resto Chino.

Tercero, el número de pares de $(x,y)$ donde $x+y$ es apagado por $1$ a partir del número de pares de $(x,y)$ donde $x+y$ es impar. Para ello, a la par de ellos:

• Para cualquier $x$-coordinar, par de $(2k-1,x)$ e $(2k,x)$ para $k=1,2,\dots,\frac{n-1}{2}$. Estos tienen colores opuestos.
• Par $(0,2k-1)$ e $(0,2k)$ para $k=1,2,\dots,\frac{m-1}{2}$. Estos tienen colores opuestos.
• La única impares número es $(0,0)$, que es negro, por lo que el número de negros pares es uno más que el número de blancos pares. Esto termina la prueba.