2009年10月17日星期六

时钟纸牌

《随机算法》一书中,时钟纸牌是这样一个程序:考虑13*4张标准扑克牌,随机排成13堆。先从第13堆中取一张,然后迭代地,每次从第x堆中取一张牌,其中x是上一次取的牌的面值,直到某次第x堆中没有牌为止。
命题:最后一次取的那张牌是13。
证明:假设最后一次取的牌不是13,是X,那么此时第X堆中没有牌,而程序开始时第X堆中有4张牌,所以在此之前已经从第X堆中取4张牌了,而每次从X堆中取牌,都必须要求上一次翻开的是X,所以在此之前已经翻开4张X了。一共就4张X,这次又翻出一张X,矛盾。