¿Siempre es posible encajar estas piezas en un cuadrado?

Question

Considerar todos los posibles pares de plazas que pueden caber en una fila de la longitud de la $n$ donde cada cuadrado tiene un ancho de 1. Si tengo una gran plaza de anchura $n$, pueden todos los pares de cuadrados en la gran plaza de forma simultánea? Es difícil de explicar sin un ejemplo así que este es el caso cuando se $n=4$:

A la izquierda están todos los pares de plazas y a la derecha es una manera para ellos para que quepa en la $n$ por $n$ plaza. Tenga en cuenta que los pares no están autorizados para ser trasladado de manera horizontal, pero se puede mover verticalmente.

Se vuelve un poco más difícil, pero todavía es posible cuando se $n=5$:

Lo que me interesa es el caso general. Es posible el ajuste de todos los pares en la plaza para cualquier $n$?

Answer 1

Siempre es posible, podemos colocar la $\binom{n}{2}$ pares en un $n \times n$ cuadrado cuando se $n$ es impar y en un $(n-1) \times n$ rectángulo al $n$ es incluso.

Este problema es equivalente al borde de colorear problema para completar la gráfica de $K_n$. Buscar en la wiki de la intuición geométrica subyacente después de la construcción.

---

Deje $[n]$ ser una forma abreviada de $\{ 0, \ldots, n-1 \}$.

Índice el conjunto de posibles pares por $(i,j) \in [n]^2$ con $i < j$.
Etiqueta de filas y columnas de la gran plaza, en el uso de los números de $[n]$.

Cuando $n$ es impar, coloque el par $(i,j)$ de la fila $k$ de la gran plaza, en donde $i + j \equiv k \pmod n$.

Si dos pares de $(i_1,j_1)$, $(i_2,j_2)$ en la misma fila se intersectan, entonces uno de los siguientes casos $$i_1 = i_2 \lor i_1 = j_2\lor j_1 = i_2 \lor j_1 = j_2$$ Desde $i_1 + j_1 \equiv i_2 + j_2 \pmod n$, nos encontramos con $$(i_1,j_1) = (i_2,j_2) \pmod n \lor (i_1,j_1) = (j_2,i_2) \pmod n$$

Desde $i_1,i_2,j_1,j_2 \in [n]$ e $i_1 < j_1$, $i_2 < j_2$, podemos descartar que el segundo caso. A partir de esto, podemos deducir distintos pares de algunos de fila son disjuntas. Esto generan un deseada de embalaje de la $\binom{n}{2}$ pares en una $n \times n$ plaza.

Cuando $n$ es incluso, $n - 1$ es impar.

Los par $(i,j) \in [n-1]^2$ en fila $k$ donde $i + j \equiv k \pmod {n-1}$. Aviso

• Para cada fila $i \in [n-1]$, la ranura en la columna $2i \pmod {n - 1}$ e $n-1$ no está en uso.
• Para cualquier columna $j \in [n-1]$, y sólo el de la ranura en la fila $i \in [n-1]$ no está en uso.

Para los par $(i,j) \in [n]^2 \setminus [n-1]^2$ con $i < j$, tenemos $j = n$. Podemos colocar el par en la fila $k$ donde $2k = i \pmod {n-1}$. Este va a llenar todos los espacios inutilizados en la primera $n-1$ filas y generar un deseada de embalaje de la $\binom{n}{2}$ pares en una $(n-1) \times n$ rectángulo.

Answer 2

7 × 7, tenemos lo siguiente. X es un espacio vacío, hasta son los 21 pares de cuadrados. Por ejemplo, D D en la segunda fila indica que el par {1,3} es utilizado en esa fila, mientras que la X en la séptima posición significa que ese punto quedo vacíelo.

A B B C X C

D E D E F F X

G H X I H I G

J K K J X L L

X M N O O M N

P X Q R Q P R

S T U X S U T.