2016年11月12日 星期六

OEIS A276449 數列的故事 (旋轉碰碰棋)

http://4rdp.blogspot.com/2016/11/oeis-a276449.html

圖片來自 FB
今年暑假貼出一篇訓練數學感 108 ─ 碰碰棋,經過問題討論後又意外找到四組數列,本文就是把這個故事做個紀錄,有興趣的朋友可以接續我們的努力再找其它數列。

碰碰棋,這款桌遊是在 International Mathematical Olympiad 2016 FB 官網看到的,我不知道它的正式名稱,就暫時稱它為碰碰棋,遊戲規則蠻簡單,在 5x5 棋盤有五顆棋子任意散佈,每顆棋子可以橫走或直走,直到該棋子遇到邊界或是其它棋子就停下來,現在就如圖所示,看如何移動棋子讓紅棋停在棋盤正中間。官方的進階玩法還限制不能去碰邊界,如果這樣,請問你會怎樣走?

因為這遊戲棋子可以任意布局,從數學的角度來看,這是一個排列組合的問題,但是它有趣在棋盤方正,可以旋轉,讓我想到一個進階題目,就是計算旋轉的組合排列

數列尋找的老班底除了赤子西瓜與孫老師外,這回還多了網友 tora 及我的小朋友 Andy,不過研究主力在赤子西瓜與 tora 身上,我負責彙整,flyingdusts 提供意見,而 Andy 計算組合數值,就這樣分工破解了這個旋轉的組合問題。

這問題說難不難但也不是簡單的問題,因為研究初期為了釐清問題本質,大家陷入膠著狀態 (誤,應該是我陷入膠著狀態)。首先,這是組合還是排列的問題?起初提問這五個棋子有多少種排列方法?因為棋盤有四個邊,如果旋轉後,有相同布局位置要扣除,每個棋子視為不同的物件。 tora 提供一個 (25P5)/4 的解答,但是答案沒這麼簡單,因為必須扣除重複排列的狀況,因為加入了旋轉讓問題難度升高,甚至連我也轉得頭暈算錯。所以我們先把問題修正成棋子都長得一模一樣,求解棋盤旋轉組合問題。另外,研發養成所的數學訓練感系列解題的習慣就是求通解,所以我們把它轉化為 n X n 棋盤放置 n 顆棋子有多少種旋轉組合。

在大家解題昏頭轉向的時候,所幸赤子西瓜提供一個公式解 C(n^2,n) = 4a + 2b + c 而再現生機,因為 a + b + c 就是我們要求的答案,它就是 a (轉四個90度方向後位置都不同的) + b (轉四次90度方向後有兩個位置相同的) + c (轉四個90度方向後位置都相同的)。


剛開始大家逐個畫圖計算,錯誤狀況很多 ......,我提出把棋盤分四個象限,針對狀況 c (四旋 90 度後位置都一樣),就是第一象限怎樣放棋子,其它象限就跟著擺,例如 4x4 棋盤 c 共有 4 種放法。而狀況 b (轉四次90度方向後有兩個位置相同的),那就是第一、二象限如何放子,第三、四象限也對應著放,其它的狀況就歸屬狀況 a (旋轉後棋子位置都不一樣)。

有了這樣處理原則,很快就解出狀況 c (四旋皆同),它還區分三種情形:
一、n = 4*i,剛好棋子數量可以平均分配在棋盤四個象限內。例如,O 空格,X 棋子
   X O O X    O X O O     O O X O     O O O O
   O O O O    O O O X     X O O O     O X X O
   O O O O    X O O O     O O O X     O X X O
   X O O X    O O X O     O X O O     O O O O
二、n = 4*i +1,必有一顆棋子在棋盤正中央,其餘平均分配在棋盤四個象限裡。
X O O O X  O X O O O  O O X O O  O O O X O  O O O O O  O O O O O
O O O O O  O O O O X  O O O O O  X O O O O  O X O X O  O O X O O
O O X O O  O O X O O  X O X O X  O O X O O  O O X O O  O X X X O
O O O O O  X O O O O  O O O O O  O O O O X  O X O X O  O O X O O
X O O O X  O O O X O  O O X O O  O X O O O  O O O O O  O O O O O
三、n = 4*i +2 或 4*i +3,無法平均分佈,就沒有四旋皆同的情形。

狀況 c 公式如下:





但是狀況 b (二旋皆同) 就不容易分辨,起初我也經常錯辨型式,還好 tora 提供兩個簡單的方法,可以幫忙辨別。一個是位置編碼,這樣旋轉後也不會錯認位置有興趣的人可以參考 tora 的手稿
   1 2 3 4    4 8 5 1
   5 6 7 8    3 7 6 2
   8 7 6 5    2 6 7 3
   4 3 2 1    1 5 8 4

另一個是試算表編號,例如圖中紅色大字 6,這樣計數數量時才不會遺漏,細節請參考 tora 的試算表。 

二旋皆同狀況,經過研究可以區分偶數及奇數棋盤,例如

X O O      O O X     雖然兩者看起來不同但他們是一群的
O X O      O X O     
O O X      X O O
赤子西瓜定義它們為鏡射組合,90度旋轉後,左右兩圖對稱
------------------------------------------------
O X O X    X O O O   左邊兩個也是一群的
O O O O    O O O X   
O O O O    X O O O
X O X O    O O O X

狀況 b 的公式如下:





最後是狀況 a (四旋皆異),我們看個例子比較容易了解,但它們是四個同一群組,
   X X X X   O O O X   O O O O   X O O O
   O O O O   O O O X   O O O O   X O O O
   O O O O   O O O X   O O O O   X O O O
   O O O O   O O O X   X X X X   X O O O

狀況 a 的公式如下:





因此,這四個數列分別如下,
列名是依據貢獻以及重要性來排序,感謝網友們的大幫忙
四旋皆同 c(n) = A276449 = 1, 0, 0, 4, 6, 0, 0, 120, 190, 0, 0, 7140, 11480, 0, 0, 635376, ...
登記發現者 ─ 赤子西瓜、tora、Andy、Bridan

二旋皆同 b(n) = A276451 = 0, 1, 2, 12, 30, 408, 1012, 17920, 45600, 1059380, 2730756, ...
登記發現者 ─ tora、赤子西瓜、Bridan、flyingdusts

四旋皆異 a(n) = A276452 = 0, 1, 20, 448, 13266, 486744, 21474640, 1106532352, ...

登記發現者 ─ Bridan赤子西瓜、tora

a(n)+b(n)+c(n) = A276454 = 1, 2, 22, 464, 13302, 487152, 21475652, 1106550392, ...
登記發現者 ─ 赤子西瓜、Bridan、tora

這四個數列九月初就在 OEIS 登記,A276449 很快認可發表,但是 A276451 卡關好久,剛開始有 OEIS 義工 Michael De Vlieger 初步檢查數值是否正確,然後由德國物理學家 Wolfdieter Lang 負責審核我的申請,可能跟這個旋轉組合有關係,起初他不明白為什麼 A276451 不是 0, 2, 4, 24, ... 而是 0, 1, 2, 12, ...,我解釋這四組數列有 C(n^2,n) = 4a + 2b + c 依存關係後,他才清楚整體關係,然後建議我用物理軌道術語方式來解釋說明,因此 A276449 為 1-orbit under C_4 (轉四次 90 度一圈),表示旋轉 90 度只有一種樣態,A276451 為 2-orbits under C_4,90 度旋轉兩種樣態,A276452 為 4-orbits under C_4,90 度旋轉四種樣態,從這裡學到一課。Wolfdieter Lang 還建議我研究 Polya counting,也是關於群組著色旋轉的問題。

另外,尋找數列的同時,Andy 意外發現神奇的組合算式,
C(16,2) = 15 + 14 + 13 + ... + 2 + 1 = 16! / 14! / 2! = 120
以及
C(16,3) = 2 x (1x14 + 2x13 + 3x12 + 4x11 + 5x10 + 6x9 + 7x8) = 16! / 13! / 3! = 560
我從這神奇組合算式受到啟發,提出一個 Bridan 猜想 ─ 數學的組合公式,它與高維空間的特定錐形體是有個對應關係,也就是 m 物任取二個組合像是在計算三角形面積,任取三個組合像是在計算三角錐體積,四維錐形體積就是底部 x 高度 / 4,五維錐形體積就是底部 x 高度 / 5,其餘以此類推。

從這次數列登記過程,可以知道研究旋轉的組合問題的人不多,有興趣的人接下來可以幹什麼?個人直覺如果棋盤是正三角形或是正 N 邊形,應該有奇妙數列可以找,反正我們已經開了歷史先河也留下紀錄,那留些機會給後進努力吧。這回一次囊括四項數列,是今年第三次全新數列斬獲,跟寶可夢抓寶有得拚,話說找數列不是一件容易的事,但是留意生活周遭有趣的事物一定可以發現很多。


最後附上網友 tora 參與這次尋找數列的感言,做為本文結尾:
老實說之前站長寄給我請我幫忙看赤子西瓜的公式的時候,
我實在看不太懂,然後我自己也是一直釐不出一個頭緒來解這題,
就這樣過了好幾天一兩個禮拜,一直沒有回站長信也覺得很不好意思。
直到後來看到赤子西瓜推出的C(N^2,N)=4a+2b+c這公式才有點明白想法。
然後昨天下午在那裏用excel標棋盤的時候也是突然靈光一閃,
才想到把格子標上數字,然後再用取數字去放棋子的方法。
一下子好像就迎刃而解了,反而有點不太相信這麼簡單就算出來了。
解出來以後突然有種滿足又失落的心情,哈。

失落的是覺得自己怎麼沒有早點想到這解法。


延伸閱讀
一、想知道什麼是 OEIS ,請看 OEIS A274119 數列的故事 (2003倍數)
二、想知道 OEIS 數列申請程序,請看 OEIS A273916 數列的故事 (Bingo-4)
三、Andy 的神奇算式 以及 組合公式對應高維錐體的 Bridan 猜想

沒有留言:

張貼留言