智力数学趣题：颠倒卡片

　　（1）对于n=9，试证：5次操作可达到要求；

　　（2）对于n=52，试证：

　　Ⅰ可通过27次操作达到要求；

　　Ⅱ17次操作不能达到要求；

　　Ⅲ26次操作不能达到要求。

　　解 （1）下表所示的5次操作可实现题目的要求。表中每行括号内的数码表示下次操作将取出另安插的卡片；每行的箭头号“↑”表示取出的卡片将要安插的位置。

　　（2）Ⅰ 更一般地；设k≥2，将证明对于n=2k或n=2k+1，进行k+1次操作即可实现要求。

　　下面对n=2k+1的叙述稍作修改也适用于n=2k情形（对于n=2k情形，下面叙述中所涉及的2k+1一律忽略不计）。先将（k+2，k+3）移至1与2之间。然后将（k+1，k+4）移至k+2与k+3之间。将（k，k+5）移至k+1与k+4之间，如此这般做下去，直到将（4，2k+1）移至5与2k之间。经过这样的k一1次操作之后得到

　　1，k+2，k+1，…，4，2k+1，2k，…，k+3，2，3

　　这之后的第k次操作将（1，k+2，k+1，…，4）移至2与3之间，第k+1次操作将（2，1）移至3之后。经过这样的k+1次操作达到要求。对于n=52=2×26，k=26，可经过k+1=27次操作达到目的。

　　Ⅱ 将证明对于52张卡片，l7次操作是不够的。我们约定这样一个称呼：倘若两张相邻的卡片中前一张的数码比后一张的小，则称这两张卡片间有一个“升阶”。顺序排列的52张卡片，初始时有51个升阶。每次操作时，抽出相继的任何一组卡片至多消去两个升阶，将这组卡片插入至多再消去一个升阶。因此，每次操作至多消去三个升阶。操作次数少于17= 当然不能消去全部升阶。即使17次操作也不行，因为可以断言：第一次操作至多消去一个升阶。如果抽出的卡片在任何一端，那么上述断言显然成立。如果抽出的卡片组在中间，那么抽出时消去了两个升阶，插入某处时又会产生一个升阶。无论如何，第一次操作至多消去一个升阶。

　　Ⅲ 将证明任何一次操作至多消去两个升阶，并且第一次和最后一次中的任何一次至多只能消去一个升阶。

　　假设某次操作消去了三个升阶，则该次操作抽出一组卡片时消去了两个升阶，将该组插入时又消去了一个升阶。设a是抽出那组卡片前面紧邻那张卡片的号码，b是抽出那组卡片第一张的号码，c是抽出那组卡片最后一张的号码，d是该组后面紧邻那张卡片的号码。并设该组卡片经操作插入到号码为e和f的相邻卡片之间。于是，一方面有a<b，c<d，d<a，因而c<b.另一方面，应该有f>e，e>b，c>f，因而c>b.这两方面的结论显然互相矛盾。

　　至于第一次操作，至多消去一个升阶。至于最后一次操作，我们可以倒过来看操作手续，最后一次视为倒过来的第一次，至多将一个降阶换成升阶。因此，原来的最后一次操作，至多将一个升阶换成降阶。第一次和最后一次操作至多各消去一个升阶，其间进行的每次操作至多消去两个升阶。52张卡片的初始态有51个升阶，需要25次中间操作才能消去51一2=49个升阶，因此总共需要27次操作。