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

Question

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.

Answer 1

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$.