如何證明奇數個手勢的石頭剪子布是公平的？

定義「石頭剪刀布」如下，

兩個人遊戲，可以出n種手勢，若兩人出的手勢相同則平，不同則按照一定規則判定誰贏。

公平指的是，無論出何種手勢，勝率都是50%。

這個問題在wiki里叫做「RPS」問題，其實就是證明RPS(2k+1)是公平的。這個我就沒在wiki里找到答案了。

顯然易證偶數個手勢的是不公平的，因為有n-1個手勢跟你不一樣，n-1是個奇數，必定勝和負的概率不等。

那麼奇數呢？是否可以求出對任意n均成立的分配方案？

---

前提條件是除了相同手勢以外都要立即決出勝負，否則類似於A &> B &> C &> D &> A的順序也一樣是公平的，只是A和C、B和D也算平局。偶數的情況題主已經說得比較清楚了，那麼奇數顯然構造一個任意一種出法，贏和輸概率都相等的規則就可以了，這個一點都不難

我們把奇數種出法用來表示，然後規定對於雙方出的手勢a和b：

令，如果

則平局

則b勝a

則a勝b

這裡取模保持結果為中的整數，顯然對於任意的a，若b的取值對所有值等概率，則勝負概率相等，因此是公平的。

這個方法也可以形象理解成，圓周上有2k+1個點，按等距離分布在圓周上，從任意一個點開始，往前順時針半周的能贏自己，往後逆時針半周的自己能贏，由於有奇數個點，兩個半周除了自己以外沒有其他交點。圓周是對稱的，因此對於任意一個點來說，贏和輸的概率都是相等的。

---

圖論問題

有奇數個結點。 很容易就可以構造有向圖，使每條邊的入度和出度相等。這時候每條邊構造偏序集，讓源戰勝坑，就是一種公平的狀態。證明和構造方法可以使用數學歸納，結點數每次加2，很方便。

如果我沒記錯，這是今年ccpc還是icpc的某個網路賽的題目。知道了這一點就是水題了。

證明具體說一下吧:

用歸納法證明。

2k＋1個結點成為公平狀態後，增加2個結點a b 。

k個結點勝a輸b ; k＋1個結點勝b輸a。

這樣2k＋1個結點出度入度相等。b勝a，使得a b 出度入度也相等

---

推薦閱讀：