2016年8月3日 星期三

OEIS A273916 數列的故事 (Bingo-4)

http://4rdp.blogspot.com/2016/08/a273916-bingo-4.html

等這個 A273916 數列 (0, 4, 7, 9, 11, 12, 12, 14, 15, 16, 16, 18, 19, 20, 22, 24, ...) 通過申請真是一段漫長的時間,現在終於通過申請,那就留下它的故事,激勵有研究興趣的朋友繼續努力。

今年二月我提出一個數學考題四子三連線像五子棋一樣,在圍棋盤上只要四子就可以一連線,可以直線、橫線、45度斜線,請問最少需要幾顆子可以排列三連線?(超過四子的連線不計)

這個考題的由來是我的小朋友在小學時,與同學玩 4 x 4 賓果遊戲,當時他認為產生三條連線最少需要十個棋子才能達成,事隔多年後,他突然想通其實只要九顆棋子就可以三連線,然後就考問我這個問題,當這問題被貼文到研發養成所的訓練數學感系列文章,經過熱烈討論之後,發現四子連線問題隱藏著一個還未被發現的數列,因而這系列數列研究從此展開,個人覺得,像我們業餘愛好者找數列,採一起合作方式比較有趣,每個人可以利用自己的專長來幫忙,比單打獨鬥好多了,因此邀請參與討論的香港孫老師及台灣國中生赤子西瓜一起進行後續的研究,可惜的小朋友沒興趣

OEIS 的數列申請基本流程如下:
1. 求解數學問題,發現數列
2. 於 OEIS 查詢這數列是否被登記
3. 如果還未被登記,你必須以真實姓名註冊一個帳號
4. 有帳號後就可以登記新數列
5. 填寫新數列相關資料欄位,如 Name, Data, Offset, Comments, Links, Example, Prog 等
6. 填好資料後要儲存,確認沒問題後再提交公告
7. 提交公告後,就有許多數學專家幫忙看內容有無錯誤,並提出改善意見
8. 更正及補充內容後,儲存好後再次提交
9. 如果內容無人提出異議,就等 N. J. A. Sloane (OEIS 創始人) 最後核可公告
10. 任何會員皆可對自己及他人已經核可的數列內容補充或修改,流程同上述 5 ~ 9

首先,我在 Google 雲端硬碟開一個試算表,大家有空就上線加內容,其實老師及西瓜兩人的貢獻較多,因此作者就決定以他們排名前面。由於剛好那陣子遇到 A274119 等數列陸續申請 (2003 倍數問題),於是就先將 A273916 登記上去,想等研究比較完備後再提交公開,不過 OEIS 伺服器發現登記者沒有提交公告時,超過一個禮拜就會自動發出通知一再提醒你去處理,我就是這樣受不了 OEIS 系統一再催促,而提交一個未完備的數列。

Sloane 也對這個數列額外提出兩個 Keyword 當作評語:more 及 nice,more 就是前面講過的未完備數列,需要再補充後續數值,會出現這樣情形,是因為找這數列有其難度,還找不到規則性,無法依序推導後面的數值,看上圖就會明瞭,這個最少棋子的 Bingo 遊戲,可以二維拓展,更增加它的困難性,找不出規則程式當然就很難寫,因此 PROG 欄也是空白的。 nice 評語表示這個數列讓 Sloane 驚訝,因為沒有人想過最少賓果棋子的問題隱藏一個未知的數列,而且多變難解,這可能是一個新的數學領域,它也符合 https://oeis.org/wiki/RiordanPrize 有獎金的待解難題類型,不知道今年還會不會有這樣的好康


從這題目可以了解,數列會以各類型式存在,只要有心尋找一定會發現它的蹤跡,通常以排列組合型態最常見,對於這個未完備的數列,我想留給大家把它完成,各位可以參考試算表研究內容,如果想編輯內容,請留下姓名及 Gmail 才會開放。孫老師已經研究出這賓果棋子的最終型式,是每加四子可以增加三條線,關於這點 IBM 的研究員 Chai Wah Wu 以 Fekete's subadditive lemma 證明,而且他還補充了這數列重要特性,a(n) >= n and a(n+m) <= a(n)+a(m), i.e., a(16) <= a(10)+a(6) = 28。但是中間空缺的部分還需要大家找找看另外有專業論文討論這個問題,儲存在康乃爾大學資料庫中關於程式,我想有兩種方法解,一個是採排列組合佈局,另一個是具有某種層度的人工智慧下棋程式來求解這最少賓果棋子問題,留給程式高手來表現,另外數學公式也缺乏,不論解出哪一部分的人不要忘記在 OEIS 留名,數學史將記錄這一切。

沒有留言:

張貼留言