# Synchronizing sequence and Synchronizable DFA, how come states repeat if synchronizing word length is $>|Q|^{2}$?

I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $$M=(Q,\Sigma,\delta,q_0,A)$$ be a DFA and let $$q'$$ be a state of $$M$$ called its "home". A Synchronizing sequence for $$M$$ and $$q'$$ is a string $$s\in \Sigma^*$$ where $$\delta (q,s)=q'$$ for every $$q\in Q$$. (We actually have extended $$\delta$$ to strings so that $$\delta(q,s)$$ equals the state where $$M$$ ends up when $$M$$ starts at state $$q$$ and reads input $$s$$).

Say that $$M$$ is Synchronizable if it has a synchronizing sequence for some state $$q'$$.

Prove that, if $$M$$ is a $$k$$-state synchronizable DFA, then it has a synchronizing sequence of length at most $$k^3$$.

This problem was already attempted here. I don't understand the answer though:

The proof of this a standard shrinking argument: if such a word is longer than $$k^{2}$$, then during the runs from $$q1$$,$$q2$$ a pair of states repeats, and we can shrink $$w$$.

How come a pair of states repeats?

I don't see a problem with runs from $$q1$$ and $$q2$$ reaching separate states. I don't so how I could be sure that I could shrink to word without disturbing both routes.

synchronously moving through the DFA beginning with two different states while an input of a word w can be described as choosing two states out of k on every step. So there exist $\binom{k}{2}$ possibilities to do that. As $k^2>\binom{k}{2}$, there will be one step where we choose a pair of states which we already had before. So the word $w$ can be shortened: this is the contradiction to the claim that the word is longer then $k^2$.
• Welcome to the site! Note that "$k$ over $2$" means $k/2$, not $\binom{k}{2}$. I edited your post to correct this. Apr 21, 2017 at 8:39
• This proves that given any two states, if there is a synchronizing sequence that works for them, there is such a sequence of length $q^2$. But why should the same word work for every two pair? Oct 20, 2017 at 16:11