參研究設備及器材紙筆電腦 Microsoft Office Excel 軟體肆研究過程或方法一遊戲規則 ( 一 ) 一維有一排燈泡, 初始狀態為全亮, 欲使最終狀態為全暗然而, 當按下其中一個燈泡的按鈕時, 會影響本身和其左右各一個燈泡, 使原本亮的變暗, 暗的變亮舉例說明 : 初

Size: px

Start display at page:

Download "參研究設備及器材紙筆電腦 Microsoft Office Excel 軟體肆研究過程或方法一遊戲規則 ( 一 ) 一維有一排燈泡, 初始狀態為全亮, 欲使最終狀態為全暗然而, 當按下其中一個燈泡的按鈕時, 會影響本身和其左右各一個燈泡, 使原本亮的變暗, 暗的變亮舉例說明 : 初"

厉擎袭
5 years ago
Views:

1 一關二淨 -- 以線性代數解析關燈遊戲研究者 : 呂瑞婷陳宥蓁陳彥廷指導者 : 王嘉慶老師摘要關燈遊戲, 規則即關掉所有的燈按任一個方格時, 便等於按了該方格及相鄰的方格的開關機制, 依循此規則關掉所有的燈, 即算是完成遊戲我們的研究方向著力於尋找平面 ( 二維 ) 的破解策略, 即讓所有的燈由亮變暗的正解法, 並進一步推導出求解的一般式我們首先從一直線 ( 一維 ) 開始觀察研究, 並將所得規律套用至二維 m n 的情況, 利用線性代數, 配合 Excel 軟體和矩陣的應用, 更有效率地求得正解接下來以此方法延伸運用在任意形狀上, 甚至推展至初始狀態不全為亮的情形目前我們已經有系統地研究出一套方法, 能解決一維和二維的任意盤面, 我們更期許未來能深入探討一組與多組正解的出現情況, 以及影響是否有正解的原因壹研究動機還記得國中時, 同學間曾掀起一波玩密室遊戲的風潮有一次遇到一個 3 3 的保險箱鎖, 當時只是沒有任何規則的隨便亂按, 無意間竟然破解了, 當下覺得這小小的東西真是有趣後來才知道它是一個獨立的遊戲, 一般稱作關燈遊戲, 由於 3 3 算是規模較小的, 我們想探究在更大規模時, 如何能夠不只是盲目的亂按, 而是更有效率有系統地找出它的解另外, 當我們正想辦法解決關燈遊戲特殊的計算規則時, 正好看見高中課本第四冊的矩陣單元, 並發現矩陣的計算形式或許對我們的研究有幫助, 於是便利用所學的矩陣, 與我們的作品互相結合貳研究目的一找出同一形狀的所有正解二解決 1 n n n 並發展為 m n 及其他形狀三利用矩陣求解 1

2 參研究設備及器材紙筆電腦 Microsoft Office Excel 軟體肆研究過程或方法一遊戲規則 ( 一 ) 一維有一排燈泡, 初始狀態為全亮, 欲使最終狀態為全暗然而, 當按下其中一個燈泡的按鈕時, 會影響本身和其左右各一個燈泡, 使原本亮的變暗, 暗的變亮舉例說明 : 初始狀態 A B C D E 按一下 A 後 A B C D E 再按一下 D 後 A B C D E 即達成目的 ( 二 ) 二維有 m n 個燈泡排列, 規則與一維的狀況大致相同 : 初始狀態為全亮, 欲使最終狀態為全暗當按下其中一個燈泡的按鈕時, 會影響本身和其左右上下共五個燈泡, 使原本亮的變暗, 暗的變亮舉例說明 : 初始狀態 A1 B1 C1 A2 B2 C2 A3 B3 C3 按一下 A1 C3 後 A1 B1 C1 A2 B2 C2 A3 B3 C3 2

3 再按一下 A3 C1 後 A1 B1 C1 A2 B2 C2 A3 B3 C3 最後按一下 B2 A1 B1 C1 A2 B2 C2 A3 B3 C3 即達成目的二名詞解釋 ( 一 ) 一維的時候, 燈泡由左而右編為 :A,B,C,D,E ( 二 ) 二維的時候, 燈泡由左而右編為 :A,B,C,D,E, 由上而下編 ( 下標 ) 為 :1,2,3,4,5 ( 參見遊戲規則的範例 ) ( 三 ) 任何一組按下按鈕的方式均稱為解, 其中, 達成遊戲目的的解, 又定義為正解 ( 四 ) 定義 : 關鍵格若 A2,B1,B2,C2 被按下的次數已知, 則我們可以定義尚未被確定的 B3 為 B2 的關鍵格, 例如, 當 A2,B1,B2,C2 皆被按下一次且不再更動,B2 的狀態為開, 此時只剩下 B3 可改變 B2 的狀態, 故 B3 為改變 B2 狀態的關鍵格 A1 B1 C1 A2 B2 C2 A3 B3 C3 ( 五 ) 紀錄解的方式 : 1 為按一下, 0 為完全不按一維的解用數列表示 ; 二維的解用表格表示, 或用數列記下該解的第一排表示其中, 為方便記錄, 我們將可以透過翻轉成同一個解的兩個解, 仍視為兩個不同的解舉例,(1,0,1,1,0) 與 (0,1,1,0,1) 是不同的解註 : 由於按下按鈕的先後次序並不影響結果, 而且我們可以知道每個燈泡最多被按一下即可,( 因為按兩下相當於完全不按的結果 ), 因此, 每個燈泡只有兩種狀況 : 1. 完全不按 ( 記為 0 ) 2. 按一下 ( 記為 1 ) 3

4 三一維 (1 n) ( 一 ) 設定第一格的狀態, 再向後觀察其規律 : 令一維表格的第一格為 A, 第二格為 B, 依此類推 1. 當 A 是 0 時, 觀察 A 的狀態為開, 則 B 是 A 的關鍵格, 故 B 需要按, 記為 1 ; 又觀察 B 的狀態為關, 則 C 是 B 的關鍵格, 故 C 不需要按, 記為 0 ; 依此類推如下方所示 : 當 A 是 1 時, 按照同樣的方法計算, 便會如下方所示 : 綜合上述兩點 : 當 A 決定是 0 或 1 時, 將直接決定 B 是 0 或 1, 間接地決定接下來所有的個子要按或著不按, 最後只要檢查最後一格的狀態即可判斷是否為正解 ( 最後一格的狀態若為關即是正解 ) ( 二 ) 我們依上述方式將 1 1 到 1 9 的正解列出來後, 歸納出在 1xn 的情況下, 符合以下規律 :(k 為任意正整數 ) 1.n=3k 時三個為一組, 按中間的方格, 恰得一組正解 2.n=3k-2 時從 n=3k 推導, 將 n=3k 型的頭尾去掉, 恰得一組正解 3.n=3k-1 時從 n=3k-2 推導, 將 n=3k-2 型的末兩格去掉, 恰得兩組正解 ( 含翻轉 ) 四二維 (n n) ( 一 ) 先將遊戲數據化我們首先定義遊戲一開始時, 燈皆開著 ( 遊戲初始狀態 ), 表格中的初始值皆為 0 每按一下方格, 會影響其本身及上下左右五個方格的狀態, 為方便表示, 我們在此方格上加 1( 按 ) 4

5 而以下表格為例, 會影響 B2 狀態的方格為 B1 B2 B3 A2 C2 若此標色的五個方格中數字和為奇數, 則 B2 的狀態被改變了奇數次, 即 B2 的最終狀態為關, 故當每格方格, 其上下左右的數字和皆為奇數, 則遊戲完成為了簡化方格內的數據, 我們將數據做 mod 2 的處理 A1 B1 C1 A2 B2 C2 A3 B3 C3 由以上可以歸納出下列規律 : 以 3 3 為例, 將 B1 B2 B3 A2 C2 之和 mod2, 若為 0, 則 B2 為開燈狀態 ; 若為 1, 則為關燈狀態故欲以系統性方法解決此遊戲時, 可先任意以按和不按排序第一列 A1 B1 C1 A2 B2 C2 A3 B3 C3 如 A1, B1, C1 為按不按按 (1,0,1), 則 A2 B2 C2 A3 B3 C3 A4 B4 C4 1. 填入 A2 時, 因 A1 只受 A1, A2, B1 的影響, 所以 A2 為 A1 的關鍵格, 其中已知 A1 =1 和 B1=0, 故 A2 必須等於 0 使 A1+A2+ B1+1 0(mod2) 同理可得,B2=1, 使 A1+ B1+C1+ B2+1 0(mod2),C2=0, 使 B1+C1+C2+1 0(mod2) 2. 以此類推,A3,B3,C3 也可依同樣規律算出按不按按 3. 若 A 4 =0 代表 A 2 +A 3 +B 3 為奇數, 即 A 3 的狀態為關, 同理, 若 B 4,C 4 =0, 表示 B 3,C 3 的狀態為關故檢驗第四列,A4, B4,C4 為 (0,0,0), 代表不需要經過第四排的操作達成遊戲目的, 換言之, 第四列的確不存在 ; 則 A3, B3,C3 按不按按 (1,0,1) 為正解 4. 為了方便記錄, 我們只記錄被按過的按鈕, 記為 1, 反之, 沒被按過的, 記為 0 如以上這個範例, 我們會用表格記錄為 5

6 用數列表示其解, 則記為 (1,0,1) 反之, 當 A1,B1, C1 為 (0,0,1) 時,A4, B4,C4 為 (0,1,1), 則 A1,B1, C1 (0,0,1) 不是正解 ( 二 ) 起初, 我們用人工的方式在紙上進行前面所述的運算, 但非常耗時, 於是我們開始使用 Excel 軟體, 然後逐一改變第一列的解, 以窮舉的方式找出正解舉例來說, 當 n=5 時, 第一列為 (1,1,0,0,0) A1=1 B1=1 C1=0 D1=0 E1=0 A2 B2 C2 D2 E2 A3 B3 C3 D3 E3 A4 B4 C4 D4 E4 A5 B5 C5 D5 E5 我們用 Excel 輸入函數 : A2=MOD(A1+ B1+1,2) B2=MOD(A1+ B1+C1+1,2) C2=MOD(B1+ C1+D1+1,2) D2=MOD(C1+ D1+E1+1,2) E2=MOD(D1+ E1+1,2) 這樣的 A2~E2 才能使 A1~E1 格中的燈變成全暗的以同樣的方法可求得 A3~E3 A4~E4 A5~E5 再進而求出 A6~E6: 6

7 A1=1 A2=1 A3=0 A4=0 A5=0 B1=1 B2=1 B3=0 B4=1 B5=1 C1=0 C2=0 C3=1 C4=1 C5=1 D1=0 D2=1 D3=1 D4=1 D5=0 E1=0 E2=1 E3=1 E4=0 E5=1 F1=0 F2=0 F3=0 F4=0 F5=0 若 A6~E6 全為 0, 則初始條件 A1~E1 是正解 ; 反之, 若 A6~E6 不全為 0, 則初始條件 A1~E1 不是正解 ( 三 ) 我們依照上述 ( 二 ) 方法, 將二進位數列從 (0,0,,0,0) (0,0,,0,1) 開始代入第一列, 一直代到 (1,1,,1) 觀察第 n+1 列是否皆為 0, 求得 2 2 到 9 9 的方格之正解 : : 唯一解 ( 含翻轉 ) : 唯一解 ( 含翻轉 ) : 共 16 組正解 ( 含翻轉 )

8 : 共 4 組正解 ( 含翻轉 ) : 唯一解 ( 含翻轉 )

9 6. 7 7: 唯一解 ( 含翻轉 ) : 唯一解 ( 含翻轉 ) : 共有 256 組正解, 故不一一詳列 ( 四 ) 當我們求 9 9 的正解時, 因為已經做了個狀況, 發現竟然不像前面比較小的 n, 都是唯一正解 ( 除了 n=4 全為正解, 也許只是特例 ), 因此, 我們不得不尋求更方便的方法 1. 以 4 4 為例, 首先在第一列設上未知數 a,b,c,d, 將第二列以第一列的元素表示 (A2=A1+B1+1), 以此向下類推, 即至所求須全為零的第五列, 將第五列以第一列元素表示, 並令第五列每一格內的值為 0, 聯立可求得 a,b,c,d 之解其中, 表格內的計算均已 mod2: a b c d a+b+1 a+b+c+1 b+c+d+1 c+d+1 a+c+1 d a b+d+1 b+c+d+1 a+b+d+1 a+c+d+1 a+b+c

10 2. 再以 9 9 為例 : 因為第一列的元素較多, 為了方便觀察, 故將每一個燈泡的影響情形分開討論 (1) a (2) b a a a a a a a a a a a a a a a a a a a a a a a a a a a a a b b b b b b b b b b b b b b b b b b b b b b b b b b b b 10

11 (3) c (4) d c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c c d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d (5) e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e 11

12 (6) f,g,h,i 與 a,b,c,d 對稱, 在此省略不列 (7) 變數 (8) 將以上所列之表格綜合後如下 : a b c d e f g h i a+b+1 a+b+c+ 1 b+c+d+ 1 c+d+e+ 1 d+e+f+1 e+f+g+1 f+g+h+1 g+h+i+1 h+i+1 a+c+1 d a+e b+f c+g d+h e+i f g+i+1 b+c+d +1 a+b+d +e+1 a+c+e+ f a+b+d +f+g b+c+e +g+h c+d+f+ h+i d+e+g +i e+f+h+i +1 f+g+ h+1 e d+f+1 c+e+g b+d+f+ h+1 a+c+e+ g+1+i b+d+f+ h+1 c+e+g d+f+1 e b+c+e +f+1 a+e+g +1 a+c+d +f+g+h e+i a+c+e +g+i a+b+c+ e+f+g+1 b+d+h +1 c+d+f+ h+i d+f+h+ 1 a+b+f+ g+h+i+ a+b+h a+b+c b+c+d g+h+1 1 +i +d+1 +h+i+1 c+d+e+g d+e+ +h+i+1 g+h+1 i b+d a+e+i f+h a b+f+h+1 c+e+i +1 a+b+f+ a+b+d d+e+f+ a+b+c a+c+d a+b+d+f b+c+ g+i+1 +e+g+h 1 +e+f+h+ +h+i+1 +g d+f+g +i i +i c+e b+d+h a+c+g b+f+h+ e+g b+d+f a+e +1 +i 1 0 a+c+e+ 0 a+c+e+ 0 a+c+e+ 0 a+c+ g+i g+i g+i e+g+i 12

13 接下來我們討論第 10 列之狀況 : S S S S S 其中,S=a+c+e+g+i 為了讓第十列的狀況不影響 9 9 之解 ( 即讓第十列不存在 ), 於是令 a+c+e+g+i=0 (8-1) b,d,f,h 是 1 或 0 並不影響解 16 個組合 (8-2) a,c,e,g,i 之中, 有 3 種情況 : 0 個 1 1 個 2 個 1 =10 個 4 個 1 5 個 (8-3) 配合 b,d,f,h 可以計算出有 (1+10+5) 16=256= 個正解 9 9 全部的解有個所以我們證明了 9 9 的正解確實佔了所有解的一半 ( 五 ) 利用此方法, 證明為什麼 4 4 的解都是正解 1. a a a a a a a a a 2. b b b b b b b b b 13

14 3. c c c c c c c c c 4. d d d d d d d d d 5. 變數由以上結果得知 a,b,c,d, 變數 1 的初始值皆不影響解, 故 4 4 的解全為正解 ( 六 ) 利用此方法, 求的正解綜合每第 11 列的每一格 : a+c+g+i d+f+j+1 a+1 b+d+f+j+1 g+i b+d a+e+g+i+1 j+1 a+e+g+1 b+d+h+j 整理後得 : ( 以下均以 mod2 處理 ) a+c+g+i=0 d+f+j+1=0 a+1=0 b+d+f+j+1=0 g+i=0 b+d=0 14

15 a+e+g+i+1=0 j+1=0 a+e+g+1=0 b+d+h+j=0 解此線性方程組, 進而推導出有唯一正解 =(1,0,1,0,0,0,0,1,0,1) 如下 : ( 七 ) 為了能更快速的求得第 n+1 列的數列, 我們構造矩陣表達上述的計算方法 1. 以 3 3 為例 A1 B1 C1 A2 B2 C2 A3 B3 C3 A4 B4 C4 a b c a+b+1 a+b+c+1 b+c+1 a+c+1 a+c+1 b+c+1 a+b+c a+b+1 15

16 (1) 首先, 令矩陣 X= 其中 (A1,B1,C1) 即為 3 3 表格中的第一列, 而 (0,0,0) 為第一列的上一列 ( 由於不存在, 所以數值皆記為 0, 在此我們簡稱為第零列 ) (2) 為了使計算符合先前的規則, 構造一矩陣 A= 此時,AX= 其中 A2=A1+B1,B2=A1+B1+C1,C2=B1+C1 即, 原先第一列 (A1,B1,C1) 會轉換成第二列 (A2,B2,C2), 而第零列 (0,0,0) 會轉換成第一列 (A1,B1,C1) (3) 同理, = 其中 (A3,B3,C3) 為表格中第三列於是我們所求的第四列數列即為的前三個元素接下來分別將 (A1,B1,C1) 的值 (a,b,c) 代入矩陣中進行計算即可 (4) 又變數 1 的計算矩陣則如下 : 首先取矩陣 X = ( 由於變數 1 在表格第一列的數值皆為 0, 故可直接代入 ) 16

17 構造一矩陣 A = 則同樣的, 的前三個元素即為變數 1 第四列之數列 (5) 最後再將第四列同一格的元素相加, 令為 0, 並解三元聯立方程式, 便可得滿足第四列皆為 0 之正解 2. 推導至 n n 的情況, 令第一列為,, 所以 X= 並令 Q= 此時矩陣 A= 而 X 的前 n 個元素便是所求第 n+1 列的數列另外變數 1 的方面 : 令 X = 再取 A = 則 X 的前 n 個元素就是組成變數 1 第 n+1 列的數列, 最後再將第 n+1 列同一格的元素相加, 令為 0, 並解 n 元聯立方程式, 便可得滿足第 n+1 列皆為 0 之正解 17

18 五二維 m n ( 一 ) 設 m 為列 n 為行利用同樣的方法, 觀察,, ) 在第 (m+1) 列的分布狀況, 利用,, ) 都等於 0, 列出,,, ) 的關係式, 進而求出,,, ) 的值 (a,b,c, ) ( 二 ) 舉例如下 : ( 三 ) 仿照 n n 之方法, 構造出矩陣以方便計算 : 令 m n 第一列為,, ), 由於 m n 與 n n 只差在列數不同, 故所有矩陣皆可延用, 只是在 n n 時所求為第 n+1 列, 而在 m n 所求為第 m+1 列 18

19 於是令 X=,Q= 則矩陣 A= 又變數 1 的矩陣如下 : 令 X =, 則 A = X 的前 n 個元素與 X 的前 n 個元素就是組成第 m+1 列的元素故最後再以 n 元聯立, 便可求得方格 m n 的正解六不規則的形狀我們設法將以上方法推展至不規則的形狀, 又分成凸多邊形及凹多邊形例 : ( 一 ) 凸多邊形例 : a b c a+b+1 a+b+c+1 b+c+1 a+c+1 a+c+1 b+c+1 a 仿照前述方法, 任取此凸四邊形之一邊作起始列 ( 每行的第一格 ), 設 a,b,c 未知數, 再求出每一行後一格的組成元素,n 元聯立式必可求出解在此情況下, 無論取凸邊形的任何一邊皆可求出相同解 : 19

20 ( 二 ) 凹多邊形例 : 1. 將之規則化以方便處理 : 20

21 2. 取左邊作為起始列 ( 以設較少的未知數 ) d d+e+1 d+1 d d+e+1 f e+f+k+1 d+f+k+j+1 f e d+e+1 e+1 e d+e+1 d+k e+k d+e+f+j+1 d+e+j+1 d+k+j e+k k g+k+d+e j g+d+i+j+1 g k+g+1 i j+i+h+1 h b+c+1 c b+c b+1 b a+b+1 b+1 c a+1 a a+b+1 a+1 a+c a+c+1 3. 聯立求解伍研究結果一 1 n 之解 : 當 n=3k, 正解為 (0,1,0,0,1,0,,0,1,0) n=3k-1, 正解為 (1,0,0,1,0,0,,1,0,0,1) n=3k-2, 正解為 (1,0,0,1,0,0,,1,0,0,1,0) 二 n n 之解 : 我們為了快速求得正解, 利用設未知數的方式, 解聯立方程式, 並證明了為何 4 4 的解全為正解, 而 9 9 中有一半的解為正解 ( 一 )n=1,2,3,5,6,7,8,10 只有唯一正解 ( 二 )n=4 全部的解均為正解 21

22 ( 三 )n=9 解的數量為 512 個, 其中有 256 個是正解三 m n 的解運用相同的方法求解, 而計算的方法也可直接套用 n n 的矩陣四不規則形狀其解決方法可分為凸多邊形及凹多邊形, 但皆可利用前述方式設未知數求解陸討論一文獻探討 : 我們利用網路搜尋相關的文獻, 發現關燈遊戲又叫點燈遊戲 Lights out 或 All lights 等等, 也有相同遊戲規則但是以黑白棋表示燈的亮暗其中, 我們所找到和關燈遊戲有關的文獻, 最早的是蔡明原林順喜 (1998) 一個有趣的益智遊戲點燈之電腦解法及分析許多文章的參考資料中均有提到此篇論文, 但主要偏重於資訊方面, 與我們想用數學探討的方向並不相同同樣著重於資訊的網頁有怎樣來點燈另一個網頁點燈步步營則提供了多種解關燈遊戲的方式, 像是拼圖法及與我們這次研究較有關的行列推估的點燈策略, 唯一的缺點是這些策略只局限於較小的特定盤面, 並沒有延伸至規模大的狀況也有人將矩陣應用在解題上, 如陳美文范姜敏容的 ( 翻動棋跡 ) 大致上是利用矩陣描述被影響的狀態, 和我們只記錄有沒有按的方法不盡相同以 3 3 為例, 要使全亮變為全暗, 列出以下方程式求所有的 X ( 代表第一列第一行位置 ) = 此方法能解任意的初始狀態和最終狀態, 而解所求的 X 必須仰賴電腦運算最後回歸到同年齡的作品, 在第 50 屆中華民國中小學科學展覽會中有兩件與關燈遊戲相關的作品 : 一謝忠益鍾育維黃瑞元的 ( 關燈遊戲 ) 二張竣翔黃柏豪的 ( 燈場亮相 ) 前者以一維的關燈遊戲為主 ; 後者則著力於立體的部分以上的作品內容, 並沒有朝利用設定未知數解線性方程組的方向研究, 因此, 為了與以上作品有不同的發展方向, 我們著重於二維盤面解正解的研究及討論 22

23 二起初我們在使用矩陣解決關燈遊戲的問題時, 以類似 Excel 的計算方式, 意即我們沒有設未知數, 直接利用第一列所設的數列進行計算以下皆為 n n 的情況, 令第一列的數列之值為 ( 首先令 X=,Q=, 則 A= 再取 A 的反矩陣 =, 此時若 ( 為 n n 之解, 則 =, 即所求第 n+1 列的數列為 (0,0,,0) 於是我們想利用此矩陣反推回 ( 之值故使 =X, 將與代入, 發現 ( ) 非一有規律的數列, 即無法求得 ( 之值因此將第一列的所有元素合併計算並無法求得正解, 未達到原先所設想的目的, 我們才試著改變方向, 將第一列的每個元素設未知數, 分開討論三從最一開始, 我們所設定的遊戲初始狀態皆為開燈, 有鑑於我們所參考的作品謝忠益鍾育維黃瑞元的 ( 關燈遊戲 ) 有關於初始狀態為隨機 ( 開燈位置任意, 即不一定全都為開燈 ) 的研究, 我們便也想試著研究, 沒想到居然亦能以相同方法達成遊戲目的, 惟有些許不同 ( 一 ) 以 3 3 為例, 設 A2 的初使狀態為關燈, 其餘皆為開 23

24 A1 B1 C1 A2 B2 C2 A3 B3 C3 若要讓 A2 的狀態維持關燈不變, 即,A1+A2+B2+A3 0(mod2), 又, 依照一開始定義的計算方式,A3=A1+A2+B2+1, 於是我們在 A3 的初始值上加 1, 使 A1+A2+B2+A3 0(mod2) 成立初始值記錄如下 : 接下來仿照 n n 設未知數計算的方法 : a b c a+b+1 a+b+c+1 b+c+1 a+c+1+1 a+c+1 b+c a+b+c+1 a+b+1 ( 表格中底線字的部分為初始值 ) 於是解聯立方程式,a=1,b=0,c=0, 檢驗後成立 ( 二 ) 依此規則, 若該格初始狀態為關, 則該格的下一格初始值記為 1, 舉例如下 : 開開關開開開關關開開關開關開開開則轉記成初始值如右再利用前面設未知數求解的方式即可 ( 三 ) 計算規則 : 觀察前面舉例的計算表格, 可發現,a,b,c 在第四列的出現狀況並不因初始值而改變, 即,a,b,c 的第四列數列可延用先前的矩陣進行計算故初始值所影響的為變數 1 的計算, 換言之, 以初始值表格套用變數 1 的計算方法, 求得第 n+1 列之變數 1 數列, 再與第 n+1 列同一格的未知數相加, 聯立即可求得正 24

25 解另外, 變數 1 在初始值改變的情況下, 我們尚未構造出通用的矩陣以方便計算四參考張竣翔黃柏豪的 ( 燈場亮相 ), 作者將立體切成平面來解析, 於是我們亦嘗試將自己的研究結果應用至立方體中, 看是否能解決問題 : a c b d 以為例, 在第一層設上未知數 a,b,c,d 故第二層可表達為 a+b+c+1 a+c+d+1 a+b+d+1 b+c+d+1 同樣計算至第三層得 a c b d 即 a,b,c,d 皆為 0, 實際操作後成立但同時, 我們發現立方體可旋轉, 但此計算結果只有唯一正解, 無法表達出立體的旋轉性, 因此我們定義立方體六個方向的解皆為同一解於是我們證實了此計算規則能套用至立體圖形, 但尚未構造出精簡的矩陣以進行運算柒結論在研究的過程中, 得到在 1 n 的情況下, 正解可分為三種形式尋找 n n 時, 起初由於毫無頭緒只能用窮舉法, 然而在列出解的過程中我們慢慢發現其中之規律, 即解的數量為個, 且正解情況有時候有唯一正解, 有時候全都為解, 還有剛好一半是解於是我們找到一種方法, 無論是 n n 或 m n, 甚至推展至不規則形狀都適用, 並能判斷是否有正解即便初使狀態的開燈位置任意, 我們亦研究出只要將初使狀態為關燈的所有格子, 往下平移一格並記為初始值 1, 即可解決問題雖然沒有達到我們要求一般式的目標, 但我們構造出矩陣以計算求解我們更期待未來能夠 : 25

26 一希望能利用矩陣更直接的求得關燈遊戲之解二求出解的一般式三在關燈遊戲立體化方面尋找更有效率的計算方法四 n n 的形式, 有唯一解的條件五分析有解及無解的狀況, 找出其判斷方式捌參考資料及其他一蔡明原, 林順喜 (1998) 一個有趣的益智遊戲點燈之電腦解法及分析中華民國資訊學會通訊, 第一卷第四期, 頁 7-13 取自: 二謝忠益鍾育維黃瑞元關燈遊戲第 50 屆中華民國中小學科學展覽會取自 : 三張竣翔黃柏豪燈場亮相第 50 屆中華民國中小學科學展覽會取自 : 四陳美文范姜敏容翻動棋跡第 43 屆中華民國中小學科學展覽會取自 : 五高中數學課本第四冊第三章矩陣六蔡寶桂 ( 無日期 ) 點燈步步營取自 : 七怎樣來點燈 ( ) 取自 : 26

Ps22Pdf

Ps22Pdf ( 0531) ( CIP). /. :, 2004. 7 ISBN 7-80153 - 959-1.... G726. 9 CIP ( 2004) 069172 : : : : : : : 2 : 100733 : 010-65369524 65369530 : : : 880mm 1230mm 1 /32 : 3300 : 150 : 5000 : 2006 8 1 2 : ISBN 7-80153