數學中的排序原理

歐陽維誠

軍事上“擒賊先擒王”的思想，對于解數學題非常有用。在研究數學問題時，常常要從考慮的對象中找到一個為首的元素，找出第一個為首的元素以后，再找第二個為頭的，繼續下去，第三個、第四個……用數學術語來說，就是把一個集合的所有元素，按某種原則依次排隊，排隊之后，常常有助于發現解決問題的途徑。在數學中稱這一思想為排序原理。

在許多數學問題中涉及一些可用數量來刻畫的元素，如數的大小、線段的長短、角的大小等等。對于集合而言，不考慮元素之間的順序。如果它們之間沒有順序，雜亂無章，往往會使許多有利于解題的條件被隱蔽起來，給解題帶來困難。因此，有經驗的解題者在解題之前，總是先考慮一下有沒有必要給所涉及的集合的所有元素排一個順序，無論是自然的順序還是人為的順序，常常都有助于解題。

請看下面一個簡單的例子：

有１０人同時到一個服務窗口辦事，假定這１０人需要服務的時間都是互不相同的，應該如何安排這１０人服務的次序，才能使他們１０人總的花費時間（包括每人被服務的時間和等待服務的時間）最少？

我們不妨把這１０人依次編號為

１，２，３，４，５，６，７，８，９，１０。

他們需要服務的時間依次是

ａ₁，ａ₂，ａ₃，ａ₄，ａ₅，ａ₆，ａ₇，ａ₈，ａ₉，ａ₁₀。

因為他們需要服務的時間互不相同，把需要服務時間最多的那個當作“王”，不妨假定ａ₁₀先“擒”出來。ａ₁₀取出之后，剩下的９個人又有一個需要服務時間最長的“王”，設它是ａ₉，把ａ₉“擒”出來。繼續下去，每次“擒”住一個服務時間最長的“王”，設依次為₈ａ₇，…，ａ₁。

這樣，我們用逐步“擒王”的辦法，把１０個人依次需要的服務時間排成一個從大到小的次序：ａ₁₀＞ａ₉＞ａ₈＞ａ₇＞ａ₆＞ａ₅＞ａ₄＞ａ₃＞ａ₂＞ａ₁。直覺告訴我們，應該讓服務時間最短的人先去接受服務。這樣開始一齊等的人多，但服務的時間短，總的等待時間就少一些。到了后面，服務的時間越來越長，但同時等待的人也越來越少，總時間會短一些。

事實上也的確如此，用數學方法可以嚴格證明。

再看下面的例子：

某社區有若干幢建筑物，任何兩幢的高度都不一樣，任何兩幢的距離都不超過它們的高度之差，如果最高的一幢建筑物的高度不超過１００米，那么我們一定可以用一道不超過２００米的圍墻（不包括建筑物本身的長度）把這些建筑物圍起來。

這個問題乍看起來似乎難以想像，這些建筑物的數量不明，布局未定，遠近高低不同，圍墻如何修法？我們可以請排序原理來幫忙。

假設共有ｎ幢建筑物，把它們從高到矮排一個順序，設它們的高度依次是

１００≥ａ₁＞ａ₂＞ａ₃＞…＞ａ_n。

如圖１所示，圍墻從ａ₁筑到ａ₂，再從ａ₂到ａ₃，ａ₃到ａ₄，…，最后從ａ_n再回到ａ₁。由于任何兩座建筑物之間的距離都不超過它們的高度之差，所以圍墻從ａ₁到ａ_n的長度不會超過（ａ₁－ａ₂）＋（ａ₂－ａ₃）＋（ａ₃－ａ₄）＋…＋（ａ_n-1－ａ_n）。

（ａ₁－ａ₂）＋（ａ₂－ａ₃）＋（ａ₃－ａ₄）＋…＋（ａ_n-1－ａ_n）＝ａ₁－ａ_n＜ａ₁≤１００。整個圍墻是從ａ₁到ａ_n的兩倍，所以圍墻的長度不會超過２００米，把所有建筑物都圍住了。

最后，我們再利用排序原理，做一個簡單的數學游戲。在９張小卡片上寫下９個不同的整數ａ₁，ａ₂，…，ａ₉。甲、乙兩人輪流取一張小卡片放在一個３×３的方格棋盤中的某一格，每一小格放一張卡片，不準多放，也不準不放。放完后，對甲計算最上一行和最下一行中的６張卡片上的６數之和，對乙則計算最左及最右兩列的６數之和，和數大者為勝，問誰有獲勝的策略？

由圖２可知，在計算勝負時，打“○”的中間一格里的數根本不用，因而不起作用。打“×”的四個小方格里的數，是甲、乙的公共數，所以不影響勝負。真正對甲、乙的勝負起作用的只有Ａ、Ｂ、Ｃ、Ｄ四格中的數。最簡單的取勝思想自然是挑最大的數給自己，挑最小的數給對方。所以，首先要把９個數的大小排成一個順序。

不妨假定９個數的大小順序是

ａ₁，ａ₂，ａ₃，ａ₄，ａ₅，ａ₆，ａ₇，ａ₈，ａ₉。

我們只要考慮兩個最大的ａ₈、ａ₉和兩個最小的ａ₁、ａ₂就可以了，這要分三種情況討論：

（１）若ａ₉－ａ₈＞ａ₂－ａ₁，這時先放者甲只要將最大的ａ₉放在Ａ格內，那么Ｂ格放的即使是最小的ａ₁，也會有Ａ＋Ｂ＝ａ₉＋ａ₁＞ａ₂＋ａ₈，甲必勝。

（２）若ａ₉－ａ₈＞ａ₂－ａ₁，這時先放者甲可將最小的ａ₁送給乙，放在Ｃ格處，下一步乙即使把最大的ａ₉放在Ｄ內，也會有Ｃ＋Ｄ＝ａ₁＋ａ₉＜ａ₂＋ａ₈，甲必勝。

（３）若ａ₉－ａ₈＞ａ₂－ａ₁，甲未必能勝，乙最多能和。因為若甲第一步取最大的ａ₉置于Ａ，第二步乙即可取最小的ａ₁放在Ｂ處。第三步、第四步，甲、乙都只能在Ｃ、Ｄ兩格內分別放下ａ₂和ａ₈，總有Ａ＋Ｂ＝ａ₉＋ａ₁＝ａ₂＋ａ₈＝Ｃ＋Ｄ，甲、乙不分勝負。同樣的，若第一步甲將最小的ａ₁送進對方的Ｃ處，第二步乙即可將最大的ａ₉放在自己的Ｄ格內，這時仍會有Ｃ＋Ｄ＝ａ₁＋ａ₉＝ａ₂＋ａ₈＝Ａ＋Ｂ，也不分勝負。所以，在這種情況下，如果雙方不發生錯誤的話，總是和局。不發生錯誤的關鍵，就是要牢牢抓住最大的或最小的“王”。