Arrange the numbers in the given rectangular blocks

Question

Consider the set $\{ (1,1), (1,2), \cdots , (1,10), (2,1), (2,2), \cdots , (10,10)\}$. The set contains all possible pairs (ordered) of numbers involving integers from $1$ to $10$. There are $100$ pairs in total. You're given $10$ rectangular blocks such that each block can contain $10$ pairs of numbers. You've to put the pairs in these boxes such that the first element of the first pair of each box is same as the last element of the last pair in the same box. Also, two consecutively placed pairs should be of the form $\{ (a,b), (b,c)\}$ where $a$ is not necessarily equal to $c$. A particular pair (out of all $100$ pairs) can be put in only one box. Show that the given arrangement is possible, that is, you can put the pairs in the boxes under the given constraints.

I tried out a few examples and it seems to work for the lower numbers (not for $n=2$ though).

Answer 1

Imagine the numbers from $1$ to $10$ written in clockwise order around a circle. I will call the clockwise distance from one number to another the "step" of that pair of numbers. For example, for the pair $(2,5)$ the step is $3$, just the ordinary difference $5-2$. But for $(8,7)$, the step is $9$, because we're going the long way around.

In order for the tenth pair in a box to end with the same number as the first pair started with, the total of the steps for all ten pairs must be a multiple of $10$. There are ten pairs with each possible step size from $0$ to $9$, so one might try putting all ten pairs with a given step in the same box. For example, the ten pairs with step size $3$ could be arranged in a box like this: $$ \big[\ (1,4)\quad (4,7)\quad (7,10)\quad (10,3)\quad (3,6)\quad (6,9)\quad (9,2)\quad (2,5)\quad (5,8)\quad (8,1)\ \big] $$ This works fine for some steps (viz., $1$, $3$, $7$ or $9$), but not for others. For example, if we gather the pairs with step $5$ together and put $(1,6)$ in the box first, the second pair would be $(6,1)$, but the third would have to be $(1,6)$ again.

To fix this problem, we can combine the troublesome step sizes in pairs and fill two boxes by using the two step sizes alternately. This requires a little care; combining two step sizes that add up to a multiple of $5$ will still not work. But we can combine step sizes of $0$ with $2$, $4$ with $5$, and $6$ with $8$.

For example, one box with alternating steps of $0$ and $2$ would contain $$ \big[\ (1,1)\quad (1,3)\quad (3,3)\quad (3,5)\quad (5,5)\quad (5,7)\quad (7,7)\quad (7,9)\quad (9,9)\quad (9,1)\ \big], $$ and the other would contain $$ \big[\ (2,2)\quad (2,4)\quad (4,4)\quad (4,6)\quad (6,6)\quad (6,8)\quad (8,8)\quad (8,10)\quad (10,10)\quad (10,2)\ \big]. $$

This way all ten boxes are filled: one each with steps of $1$, $3$, $7$ and $9$ and two each with pairs of $0$ with $2$, $4$ with $5$, and $6$ with $8$.

EDIT: As Jaap Scherphuis points out, the combination of pairs with steps $4$ and $5$ does not work: after ten pairs are placed in a box, the total of steps is $45$, not a multiple of ten.

To fix this, the revised plan is to combine the pairs with steps $3$, $4$ and $5$ into three boxes, with the successive step sizes in each box as follows:

$$ \text{First Box: }3, 4, 5, 3, 4, 5, 3, 4, 5, 4\\ \text{Second Box: }3, 4, 5, 3, 4, 5, 3, 4, 4, 5\quad\\ \text{Third Box: }3, 4, 5, 3, 4, 5, 5, 3, 5, 3\ $$ It is a bit tricky to make sure that the steps within each box don't cause a pair to be repeated and that the three boxes together can be filled with non-overlapping sets of pairs; the starting points matter as well as the steps.

To make sure this works, here are the contents of the boxes: $$ \big[\ (7,10)\quad (10,4)\quad (4,9)\quad (9,2)\quad (2,6)\quad (6,1)\quad (1,4)\quad (4,8)\quad (8,3)\quad (3,7)\ \big] $$ $$ \big[\ (4,7)\quad (7,1)\quad (1,6)\quad (6,9)\quad (9,3)\quad (3,8)\quad (8,1)\quad (1,5)\quad (5,9)\quad (9,4)\ \big] $$ $$ \big[\ (3,6)\quad (6,10)\quad (10,5)\quad (5,8)\quad (8,2)\quad (2,7)\quad (7,2)\quad (2,5)\quad (5,10)\quad (10,3)\ \big] $$ I think that does it.

Answer 2

Generalised, you have a complete digraph $K_n$ augmented with the $n$ self-loops, and you want to partition the edges into $n$ closed trails (like cycles but permitting repeated vertices).

When $n$ is odd this can be done in a very symmetric way: let trail $i$ be the cycle $$i \to i \to i+1 \pmod n \to i+3 \pmod n \to \ldots \to i+\frac{(n-1)n}2 \pmod n$$

with step sizes $0,1,2,\ldots,n-1$ (or, indeed, any other permutation of those sizes).

With $n$ even each such trail finishes on $i + \frac n2$, so it's not closed. However, that hints at a possible solution strategy: remove the steps $0$ and $\frac n2$, splitting the trail into four parts:

1. Step size 0
2. Step sizes $1,2,\ldots,\frac n2 - 1$
3. Step size $\frac n2$
4. Step sizes $\frac n2 + 1, \frac n2 + 2, \ldots, n-1$

(Parts 4 are parts 2 in reverse). For $0 \le i < \frac n2$ combine parts 2 and 4 from $i$ with two step sizes $\frac n2$: $i \to i + \frac n2 \pmod n \to i$. For $\frac n2 \le i <n$ combine parts 2 and 4 from $i$ with two step sizes $0$. Then the only challenge is to find a suitable matching so that self-loop is covered. For $n=10$ this is straightforward enough:

0 5 0 1 3 6 0 6 3 1
1 6 1 2 4 7 1 7 4 2
2 7 2 3 5 8 2 8 5 3
3 8 3 4 6 9 3 9 6 4
4 9 4 5 7 0 4 0 7 5

5 6 6 8 1 1 5 1 8 6
6 7 7 9 2 2 6 2 9 7
7 8 8 0 3 3 7 3 0 8
8 9 9 1 4 4 8 4 1 9
9 0 0 2 5 5 9 5 2 0