9
$\begingroup$

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

enter image description here

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

enter image description here

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Douma Nov 18 '18 at 21:39
  • $\begingroup$ @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). $\endgroup$ – Pazzaz Nov 18 '18 at 21:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Bennet Nov 18 '18 at 21:56
  • $\begingroup$ @MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now. $\endgroup$ – Pazzaz Nov 18 '18 at 22:14
  • $\begingroup$ Well, if possible, there will always be $n^2-2\binom n2=n$ leftover spaces. $\endgroup$ – YiFan Nov 18 '18 at 23:44
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 .

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Pazzaz Nov 19 '18 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.