  It is shown that, for every $n \geqslant 2$, the maximum length of the
shortest string accepted by an $n$-state direction-determinate two-way finite
automaton is exactly $\binom{n}{\lfloor\frac{n}{2}\rfloor}-1$
(direction-determinate automata are those that always remember in the current
state whether the last move was to the left or to the right). For two-way
finite automata of the general form, a family of $n$-state automata with
shortest accepted strings of length $\frac{3}{4} \cdot 2^n - 1$ is constructed.
