**Note.** This question had a bounty, so at the end I accepted the best (and only) answer. However, a solution is implied by the answer to [this question](https://mathoverflow.net/questions/15204/space-bounded-communication-complexity-of-identity).


**Question.**
Fix n. We are interested in the biggest t for which there exist two families of functions, $P\_i,Q\_i$, of size t from [n] to [n] such that for any $i,j$ whenever we consider the infinite sequence $P\_i(Q\_j(P\_i(Q\_j\ldots P\_i(3))\ldots)$ (where the number of iterations tends to infinity), it contains no 2's and infinitely many 1's if $i=j$ and it contains no 1's and infinitely many 2's if $i\ne j$.


**A lower bound.**
I know a construction that shows that $t\ge 2^{\frac n2-O(1)}.$ For every subset $S$ of [n] that contains exactly one of $2k$ and $2k+1$ for $2\le k\le \frac n2-2$ we construct a pair of functions, $P\_S,Q\_S$ as follows. For any number m denote by $m^+$ the smallest element of $S$ that is bigger than m or if all elements of $S$ are at most m then define it to be 1.
$P\_S(1)=1, P\_S(2)=2$ and for bigger $m$'s $P\_S(m)=m^+$, while $Q\_S(1)=1, Q\_S(2)=2$ and for bigger $m$'s $Q\_S(m)=m$ if $m\in S$ and $Q\_S(m)=2$ if $m\notin S$. This way we go through all the elements of S and end in 1 if the functions have the same index, but we are pushed to 2 if they differ.


**Upper bound.**
It is of course true that $t\le n^n$. So can you do better than $2^n$?



Two [n] to [n] function families
Okay, so I tried to see how this could possibly work. After some thinking I decided that one may as well take $P\_i=Q\_i$, so that the orbit of 3 (under the action of $P\_i$) is a cycle containing 1. If you take the length of this cycle to be roughly $n/2$, send $2\to 3$ and everything else to 2, that's not a bad idea except that it doesn't work for *all* possible $n/2$-subsets; otherwise we would have roughly $\binom{n}{n/2}$ possible $i$, as you wanted to begin with. If you now look at the orbit of 3 under $(P\_iP\_j)$ in this setting you pretty quickly conclude that there is an inherent "even-town theorem" (see Babai-Frankl's [book](http://www.cs.uchicago.edu/research/publications/combinatorics)) and thus $2^{n/2}$ is really the best possible. Of course, in the full generality weird things might be possible - I have no intuition for this, but this doesn't look good and unless the difference is really really important for some applications I wouldn't recommend working on this problem. 


