# Fixed points in a sequence of permutations

Let $S_3$ be the symmetric group on the three objects $x_1, x_2, x_3$.

We are given a (countably infinite) sequence of permutations in $S_3$:

$\sigma_1 \ , \ \sigma_2 \ , \ \sigma_3 \ , \ \ldots \ , \ \sigma_n \ , \ \ldots \ \, .$

Is it true that there exists a positive integer $N$ such that the sequence of products

$\sigma_{N} \ , \ \sigma_{N+1}\sigma_{N} \ , \ \sigma_{N+2}\sigma_{N+1}\sigma_{N} \ , \ldots \, ,$

has a(n infinite) subsequence whose terms fix $x_1$? Thanks!!!

-
I have removed the game theory tag. –  Aryabhata Jan 11 '11 at 17:35

For each i=1,2,3 look at the sequence $$a^{(i)}=(x_i, \sigma_1 (x_i), \sigma_2 \sigma_1 (x_i), \sigma_3 \sigma_2 \sigma_1 (x_i) ...)$$ Since $\{x_1,x_2,x_3\} = \{a^{(1)}_j, a^{(2)}_j, a^{(3)}_j\}$, then there is at least one $i$ such that $x_1$ appears in $a^{(i)}$ infinite number of time. Choose N such that $a^{(i)}_{N-1}=x_1$ then this you get $$\sigma_{N+k} \cdots \sigma_{N+1}\sigma_{N} x_1 = \sigma_{N+k} \cdots \sigma_{N+1}\sigma_{N} a^{(i)}_{N-1} = a^{(i)}_{N+k}$$ so $x_1$ appears infinite number of times in this sequence - meaning it is fixed by an infinite sub sequence.