Suelo de baldosas de Un Rectángulo Con Un toque de Magia

Question

He aquí un famoso problema:

Si un rectángulo $R$ es de baldosas por rectángulos $T_i$ cada uno de los cuales tiene al menos un entero sidelength, entonces el rectangle $R$ tiene al menos un número entero de longitud lateral.

$\mbox{}$

Hay un número de pruebas de este resultado (14 pruebas en este papel). Uno podría pensar que este problema es un tedioso ejercicio de combinatoria, pero la amplia gama de soluciones que no dependen de los métodos combinatorios me pregunto qué más profundos principios están en el trabajo aquí. En particular, mi pregunta es acerca de la prueba usando integrales dobles que me esbozar a continuación:

Supongamos que el rectángulo determinado $R$ tiene dimensiones de $a\times b$ y sin pérdida de generalidad supongamos que $R$ tiene una esquina en coordenadas $(0,0)$. Note que $\int_m^n\sin(2\pi x)dx=0$ ffi $m\pm$ n es un número entero. Por lo tanto, para cualquier pieza rectángulo $T_i$, tenemos que:

$\int\int_{T_i}\sin(2\pi x)\sin(2\pi y)dA=0$

Si nos suma sobre todas las baldosas rectángulos $T_i$, obtenemos que el área integral de más de $R$ es también cero:

$\int\int_{R}\sin(2\pi x)\sin(2\pi y)dA=\sum_i\int\int_{T_i}\sin(2\pi x)\sin(2\pi y)dA=0$

Desde el cornor del rectángulo está en $(0,0)$, se sigue que $un$ o $b$ debe ser un entero.

Mi pregunta es la siguiente: donde exactamente hace una prueba de y, ¿cómo se generalizan a otras preguntas sobre suelo de baldosas? Es evidente que hay un principio más profundo en el trabajo aquí. ¿Qué es exactamente el principio?

Uno puede escoger otras funciones para integrar sobre como $x-[x]-1/2$ y el resultado se sigue. Parece que la magia negra que esto funciona. Es como si las funciones que se están integrando más de desentrañar las propiedades geométricas de la forma en una forma sencilla.

EDIT: lo más probable Es que uno no necesita integrales a pensar en el mismo sabor como esta solución. Básicamente estás mirando a ambos lados de los tramos en paralelo con el lineal de funciones de prueba en fichas individuales. Sin embargo, esto no explicar realmente el más profundo de los principios aquí, en particular, de cómo se podría generalizar este método a preguntas más difíciles por la elección adecuada "funciones de prueba."

Answer 1

No es un ejercicio de "la Moderna Teoría de grafos" por Bollobas sección II.4 pg 63 que es esencialmente el mismo argumento, pero elimina las funciones trigonométricas. Para cada rectángulo $U = [x_1, x_2] \times [y_1, y_2]$ vamos $\psi(U) = (x_2 - x_1) \otimes (y_2 - y_1)$ en $\mathbb{Z}(\mathbb{R}/\mathbb{Z}) \otimes \mathbb{Z}(\mathbb{R}/\mathbb{Z})$ (considerado como $\mathbb{Z}$ módulo). Entonces $\sum_{U} \psi(U) = 0$, de modo que el rectángulo original debe tener un número entero de lado.

[Editado después de Reid comentario. Aquí $\mathbb{Z}(\mathbb{R}/\mathbb{Z})$ es el $\mathbb{Z}$ módulo con base de $\mathbb{R}/\mathbb{Z}$]

Answer 2

Hay una inédita nota sobre este teorema a partir de 1987 por Edgser W. Dijkstra, En un Problema de transmisión de Doug McIlroy, ver también este resumen. Él explica cómo la prueba de que los usos complejos integrales dobles (número 1 en el Vagón del papel), naturalmente, de la siguiente manera a partir de una elección inicial de la formalización de la segmentación de la propiedad, y, en particular, cómo el complejo números sube. En la final se especula acerca de la aplicabilidad general de este enfoque.

Como un aparte, también hay una prueba con las integrales de contorno en una nota posterior de Dijkstra: Ulrich Berger, el argumento de expresarse de otra manera. ("Ulrich Berger, el argumento de" es, esencialmente, el barrido de la línea de la prueba, el número 12 en el Vagón del papel, consulte EWD1023, Ulrich Berger la solución para el rectángulo problema.)

Answer 3

No es en absoluto obvio para mí que hay profundas principio en el trabajo en la doble integral de la prueba. En mi mente, la doble integral de la prueba es realmente el mismo que el de tablero de ajedrez de la prueba. Sólo estás tratando de llegar a una traducción invariante en función de los rectángulos que es (un) aditivo y (b) cero si y sólo si el rectángulo tiene la propiedad de interés. Todo lo que importa es que usted escoja una función que se cancela a sí mismo de la misma manera que el patrón de tablero de ajedrez. La elección de la función seno para este propósito es divertido, pero no profunda.

Si usted está buscando para profundizar en los principios, a continuación, me gustaría recomendar Rick Kenyon papel "Una nota sobre el suelo de baldosas con el entero cara rectángulos," J. Combinat. La Teoría De La Ser. Un 74 (1996), no. 2, 321-332. Utilizando este problema como un ejemplo, Kenyon se muestra el concepto de la Conway-Lagarias mosaico de grupo, una poderosa herramienta para el estudio de mosaico de problemas.

Answer 4

En mi humilde opinión el "principio más profundo en el trabajo aquí" es la asignación de un conveniente medir a los objetos combinatoria combinado. El ejemplo más cercano que viene a la mente es este problema:

Es posible cubrir una 2-D de disco de diámetro de 10 con 9 rectángulos de longitud 10 y ancho de 1?

Uno resuelve la anterior mediante la proyección de la cubierta del disco en 1/2 esfera por encima de él, notando que cada rectángulo de la intersección con el disco de proyectos para el área de la 1/2 de la esfera es igual a 1/10 de la 1/2 de la esfera de la zona, esta demostrando que 9 rectángulos no será suficiente.

Ambos problemas - el de la pregunta y la anterior con un eligió una medida de la densidad (firmado uno en el caso del rectángulo R) que tendría una conveniente integración de la propiedad.