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

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

• What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square? – John Douma Nov 18 '18 at 21:39
• @JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2). – Pazzaz Nov 18 '18 at 21:46
• I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1\times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading. – Mark Bennet Nov 18 '18 at 21:56
• @MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now. – Pazzaz Nov 18 '18 at 22:14
• Well, if possible, there will always be $n^2-2\binom n2=n$ leftover spaces. – YiFan Nov 18 '18 at 23:44

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.

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 .

• It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal. – Pazzaz Nov 19 '18 at 10:03