[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

Consider the process described in the text in which an

[math]n[/math]-card deck is repeatedly labelled and 2-unshuffled, in the manner described in the proof of Theorem. (See Figures \ref{fig 3.12} and \ref{fig 3.13}.) The process continues until the labels are all different. Show that the process never terminates until at least [math]\lceil \log_2(n) \rceil[/math] unshuffles have been done.