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

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.

Tags:

Recreational Mathematics

Related

In any group of 17 people, where each person knows 4 others, you can find 2 people, which don't know each other and have no common friends. Convert infinite 2D plane integer coords to 1D number What is an example of a proof by minimal counterexample? Existence of injective homomorphism Using the root test when the limit does not exist Is polynomial in general the same as polynomial function? Finite dimensional irreducible representations of a semisimple Lie Algebra separate points of the universal enveloping algebra. Why integral curves cannot be tangent to each other? Is complex residue related to the word residue? A matrix involving distances of $n$ points in $\mathbb{R}^3$ Prime number between $\sqrt{n}-n^{1/3}$ and $\sqrt{n}$ What manifold is produced if all similar triangles in the plane are identified?

Recent Posts