如何優雅地證明這道卡片排序問題？

01-06

分別寫有1~n的n張卡片摞在一起。操作如下：若最上面的卡片是k，就把前k張卡片的順序反轉。試證明有限次操作內1號卡片一定會出現在最上面。
比如有四張卡片，從上到下依次是(3,2,4,1)，操作則依次是(4,2,3,1), (1,3,2,4)，此時1號卡片出現在了最上面。
用歸納法可以證明這道題，但我覺得這樣證明不夠優雅，不具有啟發性。不知道能否構造一個混亂度與操作次數的函數，證明其單調遞減，最小值即是1號卡片出現在最上面的情況。

我最開始的想法是，定義n次操作後，f(n)= $sum_{}^{}{2^{n-2}}$ |n號卡片在1號卡片的上方。但這個函數不能處理(3,1,4,2)變為(4,1,3,2)的情況。
不知道構造出一個這樣的函數是否可能，請教大家。也想知道這題有沒有其他優雅的證明。
另外，我和智商碾壓我的大神趙亦修討論這個問題，他給出了一個不錯的非構造性證明。如果擔心限制思路，可以先不看以下證明：

總共n個數，n個位置。規定越靠下的位置越大，越靠上的位置越小。
定義：不動數是在有限次操作之後不會再被移動的數；移動數是不動數之外的數。

命題：移動數不存在。
證明：
1.如果最大的位置是移動數，那麼移動數移動了之後，最大的位置就會變成不動數；
2.尋找位置最大的移動數，即比它位置更大的數都是不動數；當這個數移動之後，這個位置就變成了不動數；
3.位置數是有限的，所以每一個位置上的數都會在有限次操作之內變為不動數，命題得證。

因為操作終止當且僅當1號卡片出現在最小的位置，所以該命題與原命題等價。

以前準備集訓隊考試刷過這題，容我拋磚引玉下~

先說結論，我認為此題考慮混亂度其實是不自然的。理由如下：

根據觀察，本題的核心乃是第一張牌若為k，那麼其將與第k張牌交換。

至於中間的牌的順序變換其實是本題的冗餘條件，而且相對不易刻畫，解題可以不藉助這個，所以從宏觀考慮混亂度其實相當於要強行刻畫一個不必要的冗餘條件

下面記憶寫下一個本人當時的做法，個人以為比題主給的敘述精巧些：

反證：設最終排列不止於首位為1的排列，則排列必然一直變化，由於n個數的排列只有有限種，所以經過多次交換後，第一張牌必然只有某些數字重複出現無限次，且在有限次交換後，數列首位僅為那些會出現無限次的數字，設重複出現無限次首位最大的為M，則當首位為M時，數列一次交換後首位必小於M，由M的最大性，第一張牌小於M時始終無法將M置換於首位，這與M還將重複出現矛盾~

結論得證

我構造了這樣一個函數，看起來跟已有的答案都不同。

設一個排列為 $A = (a_1, ldots, a_n)$ ，則令 $f(A) = sum_{i=2}^n 2^{i-2} I_{a_i = i}$ 。

用人話來說，就是從第2項開始依次賦權1,2,4,……，把編號等於值的所有項的權加起來，就是 $f(A)$ 。

在翻轉過程中，如果 $a_1$ 某一步變成1了，則目的達成。

否則，設 $a_1 = k$ ，則它下一步會被換到 $k$ 號位置，這會導致 $f(A)$ 中 $2^{k-2}$ 這一項從無到有。

而在這一步翻轉中， $f(A)$ 里比 $2^{k-2}$ 大的項都不變，比 $2^{k-2}$ 小的項無論怎麼變，加起來都比 $2^{k-2}$ 小，所以 $f(A)$ 整體是變大的。

然而 $f(A)$ 是有上界的，不能無限增大，所以必然會在某一步， $a_1$ 變成1。

你說的混亂度應該是指一個勢能函數吧

考慮下面這個勢能函數 $f(P) = sum_{i = 1}^n2^isigma(i)$ , $sigma(i) = 1mbox{ if Card i is in its place}$ , P 是任意一個排列。

首先f(P)有上界 2^{n + 1} -1。其次每次操作，如果第一張不是1， f(P)都增加。所以最終會停止

==========================================================

然後翻了下別人的答案，就是 @王贇 Maigo 的rephrase……就當是新的寫法吧……

謝邀。給一個初步想法，大家幫著檢查一下。

因為排列數是有限的，在足夠多次操作之後，考慮 n 張牌時的最後一張牌：

1.從來沒變過

此時將這張牌去掉， n 變為 n-1 ,重新考慮此時的牌堆。

2.變過

如果第 n 張牌變過，那麼它最多變了一次，且變成了 n ，此時將它去掉，繼續考慮新牌堆。

因此在有限次之後，牌堆將不再變化，而這種情況只可能是 1 到了最上端。

使用一個n位2進位數D表示當前的「混亂度」，其中從低向高第k位表示第k張卡片的值是否為k。每次翻轉操作都會使D的值增大：假設翻轉前第一張卡片為x，則D的第x位由0變1，而比x高的所有位不變。對於任意n張卡片的初始狀態，因為D的最大值為 $2^n-1$ ，這個值就是所需翻轉數的上限。（如果考慮最低位只會在終止狀態為1，上限可以降至 $2^{n-1}$ 。）

題主所舉之例，初始狀態(3,4,2,1)，D=0000；第一步翻轉後狀態(2,4,3,1)，D=0100；第二步翻轉後狀態(4,2,3,1)，D=0110；第三步翻轉後狀態(1,3,2,4)，D=1001，終止。

註：看了一下其它答案，這個（帶上限的）構造性證明應該和 @王贇 Maigo的證明思路一致。

如果對進一步降低上限有興趣，可以參考下表（其中A=10，B=11，C=12）:

n 最大翻轉次數對應的初始狀態 1 0 1 2 1 21 3 2 231 4 4 2413 5 7 31452 6 10 365142 7 16 3146752 8 22 61578324 9 30 615972834 10 38 591862A473 11 51 49B6A782135 12 65 261AB8C34795

如果只考慮第一位和第k位兩兩交換。任意一個數k在首位，當置換之後，它就在第k位永遠不動了，因為只有k本身在首位才能置換第k位的數。那麼每一個置換後的數都會呆在自己對應值的位置。

但是題目是倒置1～k位的數，但是要讓倒置後第k位的k發生變化，只有比k更大的數能夠做到。因此最大的數在首位被倒置之後不可能再被移動。之後把最大的數和它的位置去掉，重複。即可證明除1以外，在第一位都不穩定，並且最終會穩定在自己對應的值的位置。

大於等於二的翻轉會導致逆向讀已經排好的數的集合的字典序變大。

這樣還可以給出所需次數的非常粗糙的上界。

貌似第一遍回答說的很不清楚，沒什麼人支持QAQ。我重新整理一下思路。

我沒有系統學習過資訊理論，只是平時的課程中介紹過，我覺得我所定義的「混亂度」的本質是信息熵。

首先有一個很重要的結論：如果某一時刻（假設為s），知道了某張牌的確切位置（位於從上往下數第幾張），那麼之後任意時刻（假設為他），我們都能知道這張牌的位置。

這是因為，在t時刻，我們完全知道從s時刻到t時刻中，對卡組順序的改變過程。所以自然能分析出t時刻這張牌的位置。

換句話說：對於每一張卡，在沒有確定它的位置前，它的位置的不確定性（混亂度為1）高，但只要我們「看見」它一次，它的混亂度就立即並且永遠降低到0。

同時注意到：我們只能看卡組頂端的卡！所以一張卡的混亂度從1變為0，當且僅當它出現在頂端。

這樣就可以定義整體的混亂度了！整體混亂度是所有牌混亂度的和 F（s）=N-k

每張牌的混亂度不會增加，所以總體的混亂度不會增加。

在最開始，我們只觀察到頂端那一張牌，所以F（1）=N-1

題主希望從「混亂度」的角度分析這個問題，但是似乎並沒有自己給出一個合適的「混亂度」的定義。我來稍作嘗試吧。因為想詳細講思路，所以可能顯得冗長，見諒。

首先注意到，很難單純從排列順序的角度定義一個單調減的「混亂度」。事實上，我的想法是，將整個卡組牌序不斷改變的過程看成一個體系；每一次換牌，都需要觀測第一張牌；每一次觀測。都會降低「體系的混亂度」。

舉個例子：假設我們已經知道整個卡組裡每張牌的位置，那麼第n次改變牌序後的排列順序也能被分析出來，換句話說，雖然整個體系可能一直變化，但我們能完美預測它的變化。整個體系非常清晰，毫不混亂。

另一方面，注意到：如果知道了某張牌的位置，那麼這張牌之後的位置都能被分析出來。這張牌在體系中非常清晰，不混亂。

還有非常重要的一點：一張牌不混亂，當且僅當它曾經出現在頂端。

所以我這麼定義整個體系的混亂度：如果某一時刻（第s次改變牌序前，但我們已經看到了第s-1次變換後牌組第一張的牌），我們確定了卡組裡k張牌的位置，就記此時體系的混亂度為N-k。記為F(s)=N-k。

F(s)有兩個性質：

1.單調不增 2.F(1)=N-1

還有一個特殊性質：

當編號為1的牌移動到頂端後，F(s)恆定。

有了這個定以後，原題的證明等價為證明一下命題：F(s)恆定當且僅當卡組頂端為1號牌。（這就是說，只要1號牌不出現在頂部，體系混亂度就會不斷降低，直到1號牌出現在頂部）

特殊性質就是必要性。現在證明充分性，用反正法：

假設存在一種情況，1號牌不在頂端而F(s)恆定。那麼，除了已知的k張牌，永遠不會有別的牌出現在頂端。那麼這k張牌中至少兩張會出現在頂端無數次（如果只有一張，那這張牌應該是1，矛盾），而這其中最大的一張，出現在頂端後，就會不再循環出現。矛盾。

這樣，整個通過混亂度的證明就完成了。

我覺得整個證明過程非常不優雅2333333，但是對混亂度的定義感覺非常滿意哈哈哈哈哈

其實只是個人一點想法，還希望大家多多指正。

可以構造這樣一個函數，f為這樣一個值，它等於值為1的卡片位置與1的差的絕對值，加上值為2的卡片與2的差的絕對值，以此類推，直至值為N的卡片與N的差的絕對值。若令卡組為p[N]，則f= $Sigma left| p[n]-n ight|$

比如{3,1,4,2}的f=2+1+1+2=6，翻轉之後{4,1,3,2}的f=3+1+0+2=6，再次翻轉{2,3,1,4}，f=1+1+2=4，再次翻轉{3,2,1,4}，f=2+2=4，最後一次翻轉f=0.

可以看到，在該函數中，翻轉後的值小於等於翻轉前的值，如果出現翻轉前後值相等的話，則必然有一個數已經翻到了應該到的地方上，出現0.

這算一個混亂度與操作次數的函數

大愛這道題！話說問題可以改成該操作只能進行有限次，感覺更美妙一點

這樣的話，就可以從，

不管進行多少次操作，卡片的排列情況不會形成環

這個角度入手

ps，感覺歸納也很美啊！

若不大於n可行

考慮n+1號元素

反證，如果n+1時不可行

那麼n+1不在頭也不在尾

設其位置為a1

那麼a1不能在1（1表示最上面）

設其位置為a2

同理a2不能在1（在1，變化一次後，a1在1了）

設位置為a3

…

an都不一樣，然而一共只有n個元素，出現矛盾，所以必有ak在1，那麼進行k次操作後n+1在位置1了，k+1次操作後，劃歸為n個元素的問題

求檢查邏輯對不對