Is it always possible to fit these pieces in a square?

Question

Consider all possible pairs of squares that can fit in a row of length $n$ where every square has a width of 1. If I have a large square of width $n$, can all such pairs of squares fit in the large square simultaneously? It's hard to explain without an example so here is the case when $n=4$:

To the left are all the pairs of squares and to the right is a way for them to fit in the $n$ by $n$ square. Note that the pairs are not allowed to be moved horizontally but can be moved vertically.

It becomes a little harder but still possible when $n=5$:

What I'm interested in is the general case. Is it possible to fit all pairs in the square for any $n$?

Answer 1

It is always possible, we can place the $\binom{n}{2}$ pairs in a $n \times n$ square when $n$ is odd and in a $(n-1) \times n$ rectangle when $n$ is even.

This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.

---

Let $[n]$ be a short hand for $\{ 0, \ldots, n-1 \}$.

Index the set of possible pairs by $(i,j) \in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.

When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j \equiv k \pmod n$.

If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then one of the following happens $$i_1 = i_2 \lor i_1 = j_2\lor j_1 = i_2 \lor j_1 = j_2$$ Since $i_1 + j_1 \equiv i_2 + j_2 \pmod n$, we find $$(i_1,j_1) = (i_2,j_2) \pmod n \lor (i_1,j_1) = (j_2,i_2) \pmod n$$

Since $i_1,i_2,j_1,j_2 \in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate a desired packing of the $\binom{n}{2}$ pairs into a $n \times n$ square.

When $n$ is even, $n - 1$ is odd.

Place those pair $(i,j) \in [n-1]^2$ into row $k$ where $i + j \equiv k \pmod {n-1}$. Notice

• For each row $i \in [n-1]$, the slot at column $2i \pmod {n - 1}$ and $n-1$ is unused.
• For any column $j \in [n-1]$, one and only slot at row $i \in [n-1]$ is unused.

For those pair $(i,j) \in [n]^2 \setminus [n-1]^2$ with $i < j$, we have $j = n$. We can place the pair on row $k$ where $2k = i \pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $\binom{n}{2}$ pairs into a $(n-1) \times n$ rectangle.

Answer 2

For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.

A 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 .