關(guān)于十五子的游戲

陳景潤(rùn)

我們先來(lái)介紹一點(diǎn)組合數(shù)學(xué)的知識(shí).有一堆東西，需要把它們排列出來(lái)，我們可以給每一個(gè)東西編一個(gè)號(hào)，例如按某種規(guī)定依次編為1，2，…，n.我們稱(chēng)這個(gè)從小到大的序列（1，2，…，n）為順序列，但若出現(xiàn)一個(gè)大的數(shù)排在小的數(shù)的前面，例如（1，3，2，4，…，n），這是一個(gè)在順序上發(fā)生雜亂的序列，我們不妨稱(chēng)之為非順序列.人們規(guī)定：若在一個(gè)序列中，有一個(gè)數(shù)排在另一個(gè)比它還小的數(shù)之前，我們稱(chēng)之為一個(gè)倒置.例如非順序列（1，3，2，4，5）有一個(gè)倒置，又如（3，1，2，4，5）有兩個(gè)倒置，因?yàn)?不僅在2之前，而且還排在1之前，再如（3，2，1，4，5）有三個(gè)倒置，因?yàn)?排在1，2的前面，這有兩個(gè)倒置，2排在1的前面，又有一個(gè)倒置.我們稱(chēng)順序列的倒置數(shù)為0 ，這是因?yàn)轫樞蛄袥](méi)有發(fā)生倒置.根據(jù)倒置數(shù)的不同，我們可以把所有的序列分成兩類(lèi)，一類(lèi)是倒置數(shù)為偶數(shù)的序列，我們稱(chēng)之為偶置序列（順序列也應(yīng)歸為偶置序列）；另一類(lèi)是倒置數(shù)為奇數(shù)的序列，我們稱(chēng)之為奇置序列.

設(shè)圖18是一個(gè)十五子游戲的初始位置，我們先把這15個(gè)數(shù)排成一個(gè)序列：5，1，4，3，10，8，2，13，6，9，14，

12，7，15，11. 5排在最前面，因而有1，2，3，4這四個(gè)比它小的數(shù)排在它后面，所以僅僅對(duì)5來(lái)講，有4個(gè)倒置，我們把4寫(xiě)在橫線下和5對(duì)應(yīng)；1排在第2，雖然5排在它前面，但這個(gè)倒置在計(jì)算5的倒置數(shù)時(shí)已經(jīng)算過(guò)了，所以不再計(jì)算，而1的后面再也沒(méi)有比1小的數(shù)了，因而1的倒置數(shù)是0，把0記在1的下面；同理，4的后面比 4小的數(shù)有3和2兩個(gè)，因而在4的下面記下2；依此類(lèi)推，得圖19.由于4+0+2+1+5+3+0+5+0+1+ 3+2+0+1+0= 27是一個(gè)奇數(shù)，因而這是一個(gè)奇置序列（請(qǐng)注意，這時(shí)我們是把空格拋開(kāi)來(lái)計(jì)算的）.事實(shí)上，要判斷其是奇置序列還是偶置序列，用不著把這些倒置數(shù)加起來(lái).因?yàn)榕紨?shù)加偶數(shù)還是偶數(shù)，奇數(shù)加偶數(shù)還是奇數(shù)，就是說(shuō)，一個(gè)整數(shù)加上一個(gè)偶數(shù)并不改變?cè)瓉?lái)這個(gè)整數(shù)的奇偶性，因此我們只需數(shù)一下倒置數(shù)中有多少個(gè)奇數(shù)，若是偶數(shù)個(gè)奇數(shù)，則這個(gè)序列是一個(gè)偶置序列；若有奇數(shù)個(gè)奇數(shù)，則這個(gè)序列一定是個(gè)奇置序列，圖19的下面一行數(shù)中共有1，5，3，5，1，3，1七個(gè)奇數(shù)，故馬上斷定圖上的序列是一個(gè)奇置序列.

下面我們來(lái)研究一下，一個(gè)序列中相鄰的兩個(gè)數(shù)調(diào)換一下位置，倒置數(shù)會(huì)發(fā)生什么變化.例如一個(gè)序列中某一對(duì)相鄰的兩數(shù)為xy，當(dāng)兩數(shù)調(diào)換位置后，變?yōu)閥x.若x大于y，則xy的順序是不正常的，即有一個(gè)倒置，現(xiàn)在變?yōu)閥x，即小的在前，大的在后，因而原來(lái)的一個(gè)倒置消失了；若x小于y ，則xy這兩個(gè)數(shù)之間沒(méi)有倒置，變?yōu)閥x后，小的在后，大的在前，因而產(chǎn)生了一個(gè)倒置.因此，我們可以斷言，兩個(gè)相鄰的數(shù)若調(diào)換位置后，序列倒置數(shù)的奇偶性一定發(fā)生改變.若有三個(gè)相鄰的數(shù)xyz，把x調(diào)到z的后面，變?yōu)閥zx，這時(shí)候我們可以把這樣的調(diào)換，先看為是x與y變換位置，變?yōu)閥xz，再把x與z變換位置，變?yōu)閥zx，即經(jīng)過(guò)了兩次相鄰的調(diào)換，因而原序列倒置數(shù)的奇偶性要發(fā)生兩次變化，即奇—偶—奇，或者是偶—奇—偶，這樣，一個(gè)數(shù)在序列里向前跳過(guò)兩個(gè)數(shù)或向后跳過(guò)兩個(gè)數(shù)后，序列的奇偶性不變.若是有四個(gè)相鄰的數(shù)排成xyzw，當(dāng)x調(diào)到w后面，變?yōu)閥zwx時(shí)，顯然還可以把這個(gè)變換分成三個(gè)相鄰的變換，即x先與y交換，再與z交換，最后與w交換，因而原序列倒置數(shù)的奇偶性也經(jīng)過(guò)三次變換，即奇—偶—奇—偶或偶—奇—偶—奇，故序列的奇偶性要變.

在十五子游戲中，我們的變化不過(guò)是把空格向左右或向上下移動(dòng)，當(dāng)空格向左右移動(dòng)時(shí)，原位置的序列沒(méi)有發(fā)生變化，例如在某一行中，原來(lái)的位置是[xyz]，當(dāng)空格向右移動(dòng)時(shí)變?yōu)閇xyz]，空格向左移動(dòng)時(shí)變?yōu)閇xyz]，這兩種情況的排列都是xyz，因而我們斷言，當(dāng)空格向左右移動(dòng)時(shí)，原序列的例置數(shù)不變，所以倒置數(shù)的奇偶性沒(méi)有發(fā)生變化.當(dāng)空格向上移動(dòng)時(shí)，例如由圖20變?yōu)閳D21，因?yàn)閳D20展開(kāi)的序列為（**xyzw*），而圖21展開(kāi)的序列為（**yzwx*），即x向后跳了三個(gè)位置，因而按前面的分析，序列的奇偶性要改變.同理，當(dāng)空格往下移動(dòng)一格時(shí)，即由圖21變?yōu)閳D20時(shí)，序列的奇偶性也要改變.而當(dāng)空格向上移動(dòng)一格后，又向右或者向左移動(dòng)時(shí)，最后又向下移動(dòng)到空格原來(lái)所在的行時(shí)，則序列倒置數(shù)的奇偶性變化了兩次，因而知道倒置數(shù)的奇偶性不變.若空格向上或向下移動(dòng)兩格，則序列倒置數(shù)的奇偶性也變化了兩次，結(jié)果倒置數(shù)的奇偶性仍然不改變，但若向上或向下移動(dòng)三次則奇偶性就要改變了.在十五子游戲中，最后結(jié)果空格是在第四行，因而若空格原位置在第四行或者第二行，則到最后位置（即圖16或圖17）時(shí)，序列的奇偶性不會(huì)改變；若空格原來(lái)的位置是在第一行或第三行時(shí)，則最后位置的倒置數(shù)的奇偶性要發(fā)生變化.我們?cè)谇懊嬉呀?jīng)講過(guò)，不論十五子游戲的最初位置如何，最終總可以變?yōu)閳D16的正常排列（偶置序列）或圖17的奇異排列（奇置序列）.因此，當(dāng)原位置的序列是偶置序列，而空格在第一行或第三行時(shí)，它只能變?yōu)槠娈惻帕?；若空格在第二行或第四行，則一定可以變?yōu)檎Ｅ帕?當(dāng)原位置的序列是奇置序列，而空格在第一行或第三行時(shí)，則最終可以變?yōu)檎Ｅ帕校划?dāng)空格在第二行或第四行時(shí)，它就只能為奇異排列了.由于正常排列與奇異排列的空格都在第四行，因而正常排列（偶置序列）再經(jīng)過(guò)任何移動(dòng)也不可能變?yōu)槠娈惻帕校ㄆ嬷眯蛄校?到此，我們就完全掌握十五子游戲的奧秘了.因?yàn)槲覀儾坏馨阉懦勺罱K狀況，而且能預(yù)先就知道它能不能排成正常排列，這只要簡(jiǎn)單計(jì)算一下序列倒置數(shù)的奇偶性，且看一下空格在第幾行就行了.就這樣，我們僅僅使用了一點(diǎn)點(diǎn)數(shù)學(xué)概念就把神秘的十五子游戲變得十分簡(jiǎn)單明了.

順便指出，任何n2個(gè)縱橫數(shù)相同的小方格和（n2 - 1）個(gè)小紙板都可以玩“n2 - 1子游戲”，例如縱橫各五的二十五個(gè)小方格和二十四個(gè)小紙板的“二十四子游戲”與十五子游戲一樣，可以總結(jié)出規(guī)律，并且規(guī)律更簡(jiǎn)單一些，這里我們就不再多介紹了.（續(xù)完）