Grinstead-Snell-Probability · Problem 3.3.5

Conditional Probability

Mathematics · card-shuffling-unshuffles

Problem

Consider the process described in the text in which an nn-card deck is repeatedly labelled and 2-unshuffled, in the manner described in the proof of Theorem 3.9. (See Figures 3.10 and 3.13.) The process continues until the labels are all different. Show that the process never terminates until at least ⌈log⁡2(n)⌉\lceil \log_2(n) \rceil unshuffles have been done.

Browse the problem library