
> 
> **Problem.** Let $n\geq 2$ and let $T$ be the set of all permutations in $S\_n$ of the form 
>  $$t\_k:=\prod\_{1\leq i\leq k/2}(i,k-i) \qquad \hbox{for $k=3,4,\ldots,n+1$}.$$ 
>  Find the least integer $f\_n$ such that every $x \in S\_n$ can be written as a product of at most $f\_n$ elements from $T$.
> 
> 
> 


This is part (ii) of Exercise 1.2.16 in Chapter 1 of *Permutation Groups* by Dixon and Mortimer (Springer 1996) and is labeled as an unsolved problem. It has been 18 years since the book was published (I guess there hasn't been any further edition yet), so I was wondering whether it is solved or not; if it is can somebody give me a hint? It looks very tough. I have solved part (i) of the exercise, showing that $T$ generates $S\_n$, and showing that $2n-3$ is always an upper bound.


I asked it on math.stackexchange but did not get any answers there. I am an active member there, but here it is my first question; I hope it meets the standards here.



Minimum word length for an unusual set of generators of the symmetric group
This problem is known as ''pancake sorting'' or ''sorting by prefix reversal''. Imagine you have a stack of pancakes numbered $1,2,3,\ldots$ starting from the top. Then $t\_k$ corresponds to taking the top $k-1$ pancakes and ``flipping them'' (as a stack).
The minimum number of flips needed to reach any given arrangement (alternatively, the diameter of the corresponding Cayley graph) is a well-known problem. The exact number is not known, but some decent bounds are.


More information can be found at :


<http://en.wikipedia.org/wiki/Pancake_sorting>


<https://oeis.org/A058986>


