This must be known or easy for some of you, but here goes:



> 
> Suppose $f\_0,f\_1:[n]\to [n]$ are invertible functions, where $[n]=\{0,\dots,n-1\}$ is a set of $n$ elements.
> For a word $w=w\_1\dots w\_m\in\{0,1\}^m$ we define $f\_w=f\_{w\_m}\circ f\_{w\_{m-1}}\circ\dots\circ f\_{w\_1}$ (or make it the opposite order, if you prefer).
> Suppose $c, d$ and $m$ are such that there is **exactly one** word $w\in\{0,1\}^m$ with $f\_w(c)=d$.
> Does it follow that $n\ge m+1$?
> 
> 
> 


I've checked that it does follow for all $m\le 11$ (eleven).



Group action with unique word
Fix $c\in [n]$. Let $\mathcal R\_m(c)$ be $\{f\_w(c)\colon |w|=m\}$ and $r\_m(c)=|\mathcal R\_m(c)|$. We define $\mathcal R\_0(c)$ to be $\{c\}$.


*Claim*: Let $m\ge 0$. If $r\_m(c)=r\_{m+1}(c)$, then for all $M>m$ and for all $d\in\mathcal R\_M(c)$, there are two $w$'s in $\{0,1\}^M$ with $f\_w(c)=d$.


*Proof*: Let $S=\mathcal R\_m(c)$. Then $\mathcal R\_{m+1}(c)=f\_0(S)\cup f\_1(S)$. By invertibility if the $f\_i$, $f\_0(S)$ and $f\_1(S)$ each have cardinality $r\_m(c)=r\_{m+1}(c)$, and their union also has cardinality $r\_{m+1}(c)$. It follows that $f\_0(S)=f\_1(S)$. Now let $w\in \{0,1\}^M$ and let $f\_w(c)=d$. Let $w$ be the concatenation of $u$ (of length $m+1$) and $v$ of length $M-(m+1)\ge 0$. By the above, there exists a $u'$ also of length $m+1$ with the opposite $(m+1)$st symbol such that $f\_{u'}(c)=f\_{u}(c)$. Now $f\_v\circ f\_{u'}(c)=f\_v\circ f\_u(c)$. $\square$


It follows that if $c$ and $d$ are such that there is a unique $w$ of length $m$ with $f\_w(c)=d$, then $r\_{j+1}(c)>r\_j(c)$ for each $j<m$, so that $n\ge r\_m(c)\ge m+r\_0(c)=m+1$.


I should comment that this proof somewhat resembles that of the Morse-Hedlund theorem in symbolic dynamics.


