Permutation of three balls We have three balls in every move we can swap two of the balls.Prove that after an odd number of moves the permution of the balls are not same as they was first.
My attempt:I cant do anything special but I find out that at last one of the balls is in its first place but the two other's are swaped.
 A: A Simple Proof Based on Bipartite Graph.
Let the balls be $1$, $2$ and $3$. There are totally $6$ states, namely, $123$, $132$, $213$, $231$, $312$ and $321$. Draw a node for each state and draw a line between two nodes if we can change from one state to the other by swapping balls. You will find that the resulting graph is bipartite and thus has no cycle of odd length.


A More General Proof (Not Based on Bipartite Graph).
We assume there are totally $n$ balls, namely, $\{1, 2, 3, \cdots, n\}$. Given a permutation of the balls $P = b_1b_2\cdots b_n$, we define the # of pairs of reversions in $P$ as $$r(P) = |\{(b_i, b_j): i < j \wedge b_i > b_j\}|$$
After a swap, $P$ becomes $P'$. The following observation would be proved.

Observation. $r(P)\equiv r(P') + 1\ (\text{mod}\ 2)$

Proof. Suppose we swap $b_i$ and $b_j$ in $P$ with $i < j$ and $b_i > b_j$. 


*

*After the swap, reversion $(b_i, b_j)$ vanishes.

*For $b_k$ with $k < i$ or $k > j$, the relative position between $b_k$ and $b_i$ ($b_j$) does not change. We do not need to consider this case.

*For $b_k$ with $i < k < j$ and $b_i > b_k > b_j$, reversions $(b_i, b_k)$ and $(b_k, b_j)$ disappear.

*For $b_k$ with $i < k < j$ and $b_k < b_j$, reversion $(b_i, b_k)$ vanishes and new reversion $(b_j, b_k)$ appears.

*For $b_k$ with $i < k < j$ and $b_k > b_i$, reversion $(b_k, b_j)$ vanishes and new reversion $(b_k, b_i)$ appears.
Therefore, odd # of pairs of reversions are eliminated. When we swap $b_i$, $b_j$ with $i < j$ and $b_i < b_j$, it can be analyzed similarly and is omitted here. $\square$

By the observation above, after odd # of swaps, the # of pairs of reversions in the resulting permutation must be different from that of the original permutation by odd number. 
A: Consider the 3-cycle $(1,2,3)$ of the the symmetric group $S_3$. Note that swapping two balls, i.e. swapping the two numbers is equivalent to taking taking the inverse of the 3-cycle. In other words the action of swap can be defined as a function $f:S_3 \to S_3$ given by $f(a) = a^{-1}; \forall a \in S_3$.
Using that $(a^{-1})^{-1} = a$ we have that after an odd number of swaps the cycle would be $(1,2,3)^{-1} = (1,3,2)$. Hence we can never get the same configuration as in the beginning.
NOTE: The above proof shows that even if we're allowed to take a ball from one end and put it on the other end we would not be able to get the same configruation after odd number of swaps as the one in the beginning. Hence even a stronger result has been proven.
