Vrftjkry

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$?

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

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
.