### eusebiuu's blog

By eusebiuu, history, 3 years ago,

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?

• 0