※ 引述《arist (這實在是太複雜了)》之銘言：
: 有一雙人遊戲，在一排格子中每個人可填入S或O，兩人輪流填，先達到SOS的人為勝
: ，試問在格子數為幾格時，先手必勝，幾格時後手必勝，還有何時，雙方皆無必勝
: 下法。
剛才花了一點時間想，還沒想完整，不過要看電視了
這題還有點趣味
下面是幾個規則
符號 W先手贏 E平手 L先手必敗
s o 空格用_
首先，先手的人使用 在開頭劃上o會把case reduce到n-1
所以n-1 L 則 nW
n-1 E 則 nW or E
再來，確定無法填入任何東西的空格，只有 s__s 的形式
其它情形，要不然能填s，要不然能填o
基本上，要贏，（雙方不犯錯），一定要出現這種形式的空格才行
第三點，由第二點可以看出，不能填的空格不會消失，（除非在一方勝利前
敗方被迫填入）而且始終維持偶數個
第四點，由第三點得知，由奇偶性，n為奇數時，先手不會輸，n為偶數時，後手不會輸
第五點，n為奇數，n>=7時，先手必勝，先手先在夠中間的地方填入s，則有兩個方向
可以製造不能填的空格，下一手至少有一個地方可以製造，由第四點，知道
先手總是可以避開這些不能填的空格，所以，既然這些空格最後總是要填完
，所以，必定是後手填的，所以奇數時先手必勝。
再加上 n<=3 必定 E
n=4時也只能 E
n=5,6直接試，可以知道 只能E，或者說，沒辦法製造s__s
偶數時 當n<=12時 ，先手第一手可以放在中間，分成兩段小於七的，所以是E
偶數當 n>=7+8+1=16 先手第一手不管如何下，後手可製造不可填空格（這裡
我不詳細寫了）所以是L
剩下n=14，先手可以分成兩邊，6,7，詳細討論我也不寫了，這個情況是E
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: adsl-64-164-171-179.dsl.lsan03.