Puzzle 1 Let $M = (Q, \Sigma , \delta, F)$ be a deterministic finite-state automaton (DFA), with $n$ states. Assume that $\delta$ is total. Every $w \in \Sigma^*$ induces a function $\delta _w : Q \rightarrow Q$. Show that for each $w \in \Sigma^*$, there is a $u \in \Sigma^*$, $|u| \le n!$, such that $\delta_w = \delta_u$.
A partial solution is presented below. This solution was arrived at by Anil Seth in discussion with Meena Mahajan. The presentation of the solution was finalised by Meena Mahajan following further discussions with K. Narayan Kumar . Shashank Mehta had independently arrived at essentially the same solution; some of his notation has been used as well in this presentation.
Assume that $Q = \{1,2, ... ,n\}$. We say that $w$ is optimal if $\forall v \in \Sigma^*$ such that $\delta_v = \delta_w$, $|v| \ge |w|$.
Let $w = a_1 a_2 ... a_N$ be a string of length $N$ in $\Sigma^*$. Let $\delta _i$ denote the function induced by the prefix $w_i$ of $w$ of length $i$. We represent each $\delta_i$ by an $n$-tuple of states. Clearly, $\delta _0$ is the tuple $\langle 1,2, ... ,n\rangle$. Consider the sequence $\delta_0, \delta_1, ... , \delta_N$. If $w$ is optimal, then each $\delta_i$, $i \in \{1,2, ... , N \}$ is distinct.
We know that the tuple $\delta_0$ has $n$ distinct elements. Let $\delta_N$ have $k$ distinct elements. If $k = n$, then each $\delta_i$ is a tuple that permutes the $n$ states. Since there are at most $n!$ such permutations, it follows from the optimality of $w$ that $|w| \le n!$.
If $k < n$, let us partition the sequence $\delta_0, \delta_1, ... , \delta_N$ into segments. For $j \in \{1,2, ... ,N\}$, the $j$-segment has that portion of the sequence where each tuple has exactly $j$ distinct elements. The sequence begins with the $n$-segment and ends with the $k$-segment. Some segments may even be empty (e.g., if from $n$ states we directly go to $n-4$ states, segments $n-1$, $n-2$, $n-3$ are empty).
Fix an index $j$ such that the $j$-segment is non-empty. Pick out the first tuple $t$ in this segment. Pick out a set $T$ of $j$ positions in $[1,2, ... , n]$ such that in $t_j$, these positions have distinct states. From this segment onwards, it is sufficient to consider the behaviour of $w$ on these positions alone. These positions have distinct states until this segment ends.
The number of arrangements of distinct states in these positions is bounded by $P(n,j)$, the number of permutations of $j$ objects drawn from a set of $n$ distinct objects. Thus,
N = \sum_{j=k}^{n} \mbox{(length of j-segment)}
\le \sum_{j=1}^{n} \mbox{(max length of j-segment)}
= \sum_{j=1}^{n} P(n,j)
= (n!) \sum_{j=1}^{n} \frac{1}{(n-j)!}
= (n!) \sum_{l=0}^{n-1} \frac{1}{l!}
\le (n!) \sum_{l=0}^{\infty} \frac{1}{l!}
= (n!) e
We now improve this crude bound. The improvement bounds $N = |w|$ by $n!$ if $k \le n-3$, by $5(n!)/4$ if $k = n-2$, and by $3(n!)/2$ if $k = n-1$.
Partition the set of states into $k$ parts, $Q = Q_1 \cup Q_2 \cup ... \cup Q_{k}$, based on what they are mapped to by $\delta_N$.
Now, in the $j$-segment where we have identified a set $T$, $|T| = j$, of relevant positions, consider the partition $T = T_1 \cup T_2 \cup ... \cup T_{k}$, where $T_i = T \cap Q_i$. Clearly, all positions in $T_i$ eventually get mapped to the same state by some prefix of $w$. Therefore,
Claim 1: If tuples $t', t''$ occur in the $j$-segment of $w$ and they differ on $T$ only by permutations within each of the parts $T_i$, then $w$ is not optimal.
Proof Assume otherwise; an optimal $w$ has both $t'$ and $t''$ in its $j$-segment. Say $t'$ precedes $t''$. Delete the substring of $w$ occurring between $t'$ and $t''$. A modified version of the sequence of tuples after $t''$ will now occur immediately after $t'$. The modification involves permuting positions within parts of each $Q_i$. Since the last segment treats all positions within a part identically, these permutations have no effect on the last segment. So the final tuple is the same, and it has been realised by a string shorter than $w$, contradicting the optimality of $w$. \hfill $\Box$
From the above claim, it follows that the maximum possible length of the $j$-segment is actually much less than $P(n,j)$. It is in fact bounded by $$\frac{P(n,j)}{|T_1|! |T_2|! ... |T_{k}|!}$$.
Claim 2 Given natural numbers $a_1, a_2, ... a_{m}$ adding up to $p$, $$ a_1 ! a_2 ! ... a_m ! \ge 2^{p-m}$$
Proof The expression $ a_1 ! a_2 ! ... a_m !$ has $p$ factors, since $(a_i)!$ contributes $a_i$ factors and $a_1 + a_2 + ... + a_m = p$. Of these, $m$ factors are 1, one from each $(a_i)!$. This leaves $p-m$ factors, each an integer greater than or equal to two. The inequality follows. \hfill $\Box$
Claim 3: The length of the $j$-segment is at most $\frac{1}{2^{j-k}}\frac{n!}{(n-j)!}$.
Proof Follows from the above two Claims. $\Box$
So now,
N = \sum_{j=k}^{n} \mbox{(length of $j$-segment)}
\le \sum_{j=k}^{n} \frac{1}{2^{j-k}}\frac{n!}{(n-j)!}
= (n!) \sum_{l=0}^{n-k} \frac{1}{l!}\frac{1}{2^{(n-k)-l}}
Now it can be easily verified that for $k \le n-3$, $N \le n!$.