Why we can find a permutation with $2$ fix points in this way?

136 Views Asked by At

I have a permutation of order $20$ and I can make cyclic permutation on it. For example $(3 2 1)$ should be $(2 1 3)$ or $(1 3 2)$. Why we can find a permutation with $2$ fix points in this way?

This is not available for a permutation of order $3$. I have the next context: I have $20$ people on a round table and $20$ papers with their names. I can rotate the table s.t. two of them have the right names?

1

There are 1 best solutions below

1
On

Partial answer, but too long for a comment.

To have a permutation that you cannot rotate to get two elements right, each element must be displaced by a different amount from its correct location. That is easy to do if the number of elements is odd. Let $1$ be the element that is in its correct location. Then offset each element by one more than the previous one, rolling around the circle at the end. For $9$ elements, the permutation is $(135792468)$. It should be clear how this matches your example for $3$ and any other odd number.

This construction fails for even numbers because when you get done with the odds you get back to $1$. That does not prove there is not some other permutation that satisfies your requirement. We can see it does not work for $4$ by exhausting the cases. Again, let $1$ stay fixed. If $2$ goes to $3$, we cannot have $3$ go to $1$ because $4$ would have to stay fixed. We cannot have $3$ go to $4$ because rotating one step counterclockwise would make both $2$ and $3$ right, so $3$ goes to $2$. But then $4$ must stay fixed and we already have two fixed points. There was nothing special about $2$ going to $3$ so any other choice will run into the same problem.

I suspect the general proof goes through the sum of the displacements. If there are $n$ elements, the sum of the displacements is $\frac 12n(n-1)$. If $n$ is odd, this is divisible by $n$, while if $n$ is even it is not. I can't find the argument to say the sum must be divisible by $n$, but I think it is standard.