Advanced Mathematics Support Programme(AMSP)例題分析

本月的每月一題，筆者將介紹一個(ge) 有趣的問題。它出現在兩(liang) 個(ge) 多月以前的AMSP（Advanced Mathematics Support Programme）一次培訓的討論課當中，由筆者的一位朋友提供，但並非AMSP官方給出的培訓題。之前我們(men) 不太關(guan) 注這項培訓，但是自從(cong) 這個(ge) 題目的出現，筆者發現此項目非常適合中等難度的競賽，如果有條件或者在英國讀書(shu) 的學生是很推薦參加的。

題目的敘述比較簡單，其中Note部分是對這個(ge) 題目的一些嚴(yan) 謹補充：

Somepeople stand in a circle with their eyes closed. On command, they allopen their eyes. Each person picks some other person at random andstares fiercely at that person. If two people find that they arestaring at each other, they screamand drop out of the circle. Sometimes several pairs might drop out atonce. If nobody drops out, it is called a “quiet round.” If there are n people in the circle, what is the probability that the next round will be aquiet round?

一群人閉眼站成一圈。他們(men) 會(hui) 根據一聲命令同時睜開眼睛，並且每個(ge) 人都會(hui) 隨機地選一個(ge) 其他人，盯著他的眼睛看。如果兩(liang) 個(ge) 人發現他們(men) 在互相盯著看對方，他們(men) 會(hui) 尖叫並退出這個(ge) 圓圈。有時候會(hui) 有很多對人同時尖叫並退出圓圈的情況，但如果沒有人退出圓圈，則這是一個(ge) “安靜回合”。如果有n個(ge) 人站在圓圈中，下一個(ge) 回合是“安靜回合”的概率是多少？

Note：Assume that the game is just starting out, and has n peopleplaying.
Around consists of

1)everyone has their eyes closed

2)everyone opens their eyes on command and stares at someone else atrandom.

3)if two people find that they are staring at each other, the screamand are out.

4)end of round.

So a quiet round is one in which no one screams. ("next" doesnot necessarily mean that there was a round before it)

據本題的提供者所說，這是今年AMSP中一位教授給出的題目，當時整個(ge) 地區（AMSP依據東(dong) 英格蘭(lan) 、倫(lun) 敦和西部等地劃分為(wei) 地區性質的培訓）沒有一位學生做出。這位教授認為(wei) 此題是根據MAA出版的老雜誌當中的一些結論改編的，其最初的結果應當屬於(yu) MAA官方。這道題目本身其實很簡單，讀者可以自己試著解它。

分析：這個(ge) 題目在雜誌上的原題應當是抽象代數中的結論，但是經過改編以後，本題又和置換群Sn不太一樣，因為(wei) 如果同時有多個(ge) 人看向同一個(ge) 人,這就不是一個(ge) 置換了。但我們(men) 仍然可以借助映射的手段，將這個(ge) 題目做一個(ge) 等價(jia) ：

其中條件(i)指的是一個(ge) 人不能看向他自己，(ii)指的是每個(ge) 人看向的人，不能看向自己。

這個(ge) 題目的前身，應當是修改其中的staring條件：每個(ge) 人恰好被一個(ge) 人看向了。這樣的話它就變成了Sn中不含對換的置換數全體(ti) 。這個(ge) 問題也可以等價(jia) 成2-regulargraph的簡單圖數。

這個(ge) 問題的推廣形式是n-vertex,k-regular simple graph的個(ge) 數，它在AIME和AMC難題當中常常以小的n和k形式出現,並有時伴隨了BurnsideLemma的考點（需要考生自己去計算它的同構群）。

McKayand Wormald是第一個(ge) 提出最一般的結果的數學家，他們(men) 得到了n-vertex,k-regular simple graph的個(ge) 數趨近於(yu) ：

其中

這裏我們(men) 討論它的漸進值是因為(wei) 這個(ge) 值不是一個(ge) 簡單的二元函數(on n,k)。但是在k=2的時候，我們(men) 可以再次（在每月一題當中，這個(ge) 技術出現了很多次）使用我們(men) 最熟悉的工具，人類最好的夥(huo) 伴：遞推（recursion）來解決(jue) 這個(ge) 1990年圖論研究的熱門問題的初級版本。

首先借用Conway提出的PartitionFunction：

Definition P(n), the partition function, gives the number of ways of writing the integer as a sum of positiveintegers, where the order of addends is not considered significant.

例如：

4=4

=3+1

=2+2

=2+1+1

=1+1+1+1.

從(cong) 而P(4)=5。

設an是n-vertex,2-regular simple graph 的個(ge) 數。

因為(wei) an的組合性質等價(jia) 於(yu) 把n分成每個(ge) 部分都不小於(yu) 3的全部方法，故根據容斥原理我們(men) 有

Homework：熟悉GeneratingFunction的讀者可以嚐試推導它的生成函數，也許會(hui) 用到q-Pochhammer。