2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you sure it's doable for $n=2$? It seems to me that it isn't (or I misunderstood something in your explanation of the problem) $\endgroup$ – Andrei Rykhalski Mar 1 '19 at 9:04
  • $\begingroup$ So basically you have a complete graph $K_n$ augmented with self-loops and you want to partition the edges into $n$ cycles of length $n$. Probably that comes down to partitioning $K_n$ into $n$ cycles of length $n-1$ and then adding a self-loop to each one. $\endgroup$ – Peter Taylor Mar 1 '19 at 11:46
  • $\begingroup$ @tannnyp Sorry, I missed "not" in your message $\endgroup$ – Andrei Rykhalski Mar 1 '19 at 14:30
  • $\begingroup$ @PeterTaylor Keep in mind that each edge must be traversed in both directions, i.e. between each pair of nodes you have two oppositely directed edges which both take part in the problem. For $n$ a prime, it is easy, but for composites such as $n=10$ it does not seem so straightforward. $\endgroup$ – Jaap Scherphuis Mar 1 '19 at 14:58
  • $\begingroup$ @JaapScherphuis, it's a good point that the edges are directed and present in both directions, but it's overly restrictive to say that it's easy for primes: it's easy for any odd number. $\endgroup$ – Peter Taylor Mar 1 '19 at 16:27
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Unfortunately, if you alternate step size 4 and 5, you get one long loop of 20 pairs, not two loops of 10. Maybe they can be combined in a different way, but as it stands you haven't demonstrated a solution yet. $\endgroup$ – Jaap Scherphuis Mar 1 '19 at 10:00
  • $\begingroup$ @Jaap. Oops! Back to the drawing board. $\endgroup$ – FredH Mar 1 '19 at 10:01
  • $\begingroup$ It's fixed (I hope). Sadly, it's a lot more complicated than my original approach. Any ideas for a simpler solution? $\endgroup$ – FredH Mar 1 '19 at 11:06
2
$\begingroup$

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
| cite | improve this answer | |
$\endgroup$

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.