These days I discovered a problem that is intuitively correct for me, but I don't know the proof for this and I will be grateful if you could help me:). Anyway, the problem sounds like this: Given an **even** n, find a group of n — 1 permutations of n such that always is a different pair of numbers in any pair of indexes (i, i + 1) for any odd i, for any permutation. For example, if n = 6, then the answer is the group formed by:↵
↵
~~~~~↵
1. 1 2 3 4 5 6↵
2. 1 5 6 3 4 2↵
3. 1 4 2 6 3 5↵
4. 1 3 5 2 6 4↵
5. 1 6 4 5 2 3↵
~~~~~↵
↵
↵
You can see that, magically, numbers of all pairs of indexes are different for all permutations (1 is paired with every other number exactly once, 2 same, 3 same and so on).↵
The algorithm for reaching from a permutation to another is pretty simple:↵
From 1 2 3 4 5 6 make 5 6 3 4 1 2 and then perform a circular rotation to the right with the last element fixed. Thus, from 5 6 3 4 1 2 you reach to 1 5 6 3 4 2. Repeating the same algorithm you build the group above. More then that, from the last one you can get to the first one, thus this process being cyclical.↵
So, here comes the question: WHY? Why is so good and correct?
↵
~~~~~↵
1. 1 2 3 4 5 6↵
2. 1 5 6 3 4 2↵
3. 1 4 2 6 3 5↵
4. 1 3 5 2 6 4↵
5. 1 6 4 5 2 3↵
~~~~~↵
↵
↵
You can see that, magically, numbers of all pairs of indexes are different for all permutations (1 is paired with every other number exactly once, 2 same, 3 same and so on).↵
The algorithm for reaching from a permutation to another is pretty simple:↵
From 1 2 3 4 5 6 make 5 6 3 4 1 2 and then perform a circular rotation to the right with the last element fixed. Thus, from 5 6 3 4 1 2 you reach to 1 5 6 3 4 2. Repeating the same algorithm you build the group above. More then that, from the last one you can get to the first one, thus this process being cyclical.↵
So, here comes the question: WHY? Why is so good and correct?
