簡易檢索 / 詳目顯示

回結果列表
研究生： 林哲侃
Lin, Tse-Kan
論文名稱： 數學計算可交換性益智玩具的最少步數
Calculating the Upper Bounds of the Commutative Puzzles in Mathematics
指導教授： 郭君逸
Guo, Jun-Yi
學位類別： 碩士
Master
系所名稱： 數學系
Department of Mathematics
論文出版年： 2016
畢業學年度： 104
語文別： 英文
論文頁數： 43
中文關鍵詞： 點燈遊戲
英文關鍵詞： commutative puzzles
DOI URL： https://doi.org/10.6345/NTNU202204008
論文種類： 學術論文
相關次數： 點閱：123  下載：38 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 這篇論文的主旨是要描述點燈遊戲，及其他類可交換性益智玩具的最佳解。在1998年，Anderson與Feil用線性代數找出了點燈遊戲的解法。2009年，Goldwasser等人證明了點燈遊戲在只能按亮燈的限制下與一般遊戲的可解性並無不同。2014年，Schicho和Top進一步討論更多點燈遊戲的變形。這些結果都相當程度地仰賴電腦運算。在這篇論文中，我們試著用純數學方法去找出最佳解的上界，並給出上界的估計公式。

    The main purpose of this paper is to describe the optimal solution of Lights Out games and other similar commutative puzzles. In 1998, Anderson and Feil used Linear Algebra to find a solution method for Lights Out games. In 2009, Goldwasser et al. proved the lit-only restriction is not different for the sigma game. In 2014, Schicho and Top discussed many variation of Lights Out. Those results heavily rely on computer. In this paper, we use mathematical methods to find an upper bound of minimal solutions, and furthermore, give an estimation algorithm to the upper bound.

    Content 1 Abstract 3 1. Introduction 5 Lights Out 5 Linear Solution 5 Lie Algebra, Dynkin Diagram and Lit-Only Games 6 2. The standard Lights Out 9 Standard Lights Out of n×n grids 9 Lights Out cube 20 3. N-ary models and Variations 25 N-ary Lights Out 25 4. Some other commutative puzzles 37 Rubik's Clock 37 Gear Shift 39 5. Conclusion 41 References 43

    [1] Huang, Hau-wen, Lit-only sigma-game on nondegenerate graphs, Journal of Algebraic Combinatorics, (2015) 41: 385-395.
    [2] Hsin-Jung Wu and Gerard J. Chang, A study on equivalence classes of painted graphs, Master Thesis, NTU, Taiwan, 2006.
    [3] Josef Schicho and Jaap Top, Algebraic Approaches to FlipIt, The Resolution of Singular Algebraic Varieties, Clay mathematics Proceedings, Vol. 20, 2014, pp. 319-325.
    [4] Jakob Kogler, God's Number for Clock found, from https://goo.gl/SeqC6r
    [5] John Goldwasser, Xinmao Wang and Yaokun Wu, Does the lit-only restriction make any difference for the σ-game and σ+-game? European Journal of Combinatorics, Volume 30, Issue 4, May 2009, Pages 774–787
    [6] Marlow Anderson and Todd Feil, Turning Lights Out with Linear Algebra, Mathematics Magazine, Vol. 71, No. 4. Oct., 1998, pp. 300-303

    下載圖示
    QR CODE