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.