https://4rdp.blogspot.com/2016/10/115-ladder-game.html?m=0
大家在學生時代應該都有玩過紙上梯子遊戲,先從左圖上方選一個端點當起點,然後由上而下,遇到橫線連通的地方就轉彎,若遇左右橫線接通時則從中穿越,左圖例子就是從 a 到 A。
請問這八個開關有那些配置,可以得到 (a,b,c) 對 (A,B,C) 的結果?
這個測驗題的構想來自,
FB 上一則東森新聞影片,南韓首爾讓捷運車廂內對座乘客有互動的機會,蠻有趣的,希望藉此題目讓大家細思如何控制梯子遊戲互換位置。
有四列開關,可以分別討論。
回覆刪除先假設一列開關。
├┘┼┘┤ 全開,設此情況為α。
此時abc通過會得到abc。(不變)
├─┼─┤ 全關,設此情況為β。
此時abc通過會得到cba。(ac調換)
├┘┼─┤ 只開左邊,設此情況為γ。
此時abc通過會得到acb。(bc調換)
├─┼┘┤ 只開右邊,設此情況為δ。
此時abc通過會得到bac。(ab)調換。
(以下將棋盤逆時針轉90度)
經歷四次會回復原狀,所以
αααα
ββββ
γγγγ
δδδδ
共四種,皆可回到abc。
觀察後發現,其實abc經過兩次同樣機關就可以恢復成abc,所以
ααββ
ββγγ
γγδδ
δδαα
ααγγ
......
皆可回復成abc,P(4,2)=12種。
由於起始是abc,任一個機關和α交錯放置皆可回復原狀。
αβαβ
βαβα
αγαγ
γαγα
δαδα
αδαδ
3 x 2 = 6種。
將四種機關以開關編號代入,即為所求,共有4 + 12 +6 = 22種可能。
追加
刪除αββα
βααβ
αγγα
γααγ
αδδα
δααδ
......
P(4,2)=12種
22+12=34
不錯,把橫列兩開關當成一組,每組有四種組合狀況,這樣可以把問題描述簡化很多。
刪除但是答案總數只有 34 種似乎太少,還有其它組合未考慮到,繼續加油。
0
刪除5
10
15
17
20
34
40
51
60
65
68
80
85
90
95
103
105
110
118
123
125
130
136
150
155
157
160
165
170
175
183
185
190
195
204
215
217
222
230
235
237
240
245
250
255
共46
數字為二進制轉化為十進制的代表數。
刪除設8個開關為一個二進制數的第1-8位,0為斷開,1為閉合。
則有0-255共256種方法。以試算表窮舉後轉化爲10進制,如上表。
希望可以幫西瓜找出遺漏的部分。
這條題目與symmetric group (order 3) S_3有關
刪除全開是identity element,記為()(即α)
開關會交換ac,記為(ac)(即β)
只開左邊交換bc,記為(bc)(即γ)
只開右邊交換ab,記為(ab)(即δ)
然後可以考慮它們的結合
Y 之後 X 記為 XY (就像函數f(g(x))是先 g 後 f
(ac)(ab)=(abc) (即a->b, b->c, c->a)
(ac)(bc)=(cba)
(ab)(ac)=(cba)
(ab)(bc)=(abc)
(bc)(ac)=(abc)
(bc)(ab)=(cab)
注意(abc)和(cba)是對方的inverse
所以可從上面三個(abc)選一個,三個(cba)選一個,組成(abc)(cba)=()或(cba)(abc)=()
當中有十二個是西瓜未提及的
其中一個例子是(ac)(ab)(ac)(bc)=γβδβ
我有察覺到這似乎和群論有關係,以前也稍微看過相關內容,不過也不熟悉,只能用這種小學生的方式解題。
刪除改天要好好加強這方面的知識。
我記得你好像還是國中生欸...已經看過群論!?(掩面)
刪除其實我也只是從網上東看看西看看知道一點,有空要借本書回來好好看看
00000000
刪除00000101
00001010
00001111
00010001
00010100
00100010
00101000
00110011
00111100
01000001
01000100
01010000
01010101
01011010
01011111
01100111
01101001
01101110
01110110
01111011
01111101
10000010
10001000
10010110
10011011
10011101
10100000
10100101
10101010
10101111
10110111
10111001
10111110
11000011
11001100
11010111
11011001
11011110
11100110
11101011
11101101
11110000
11110101
11111010
11111111
把老師的解以二進制表示
沒想到這題跟群論有關聯,等兩位研究好,可以當我的老師教一下這部分。
刪除試算表已發送到各位郵箱,缺少00000000這個結果,所以會顯示45
刪除都快要提到阿貝爾集了,看來我們真是跟望月教授在走同一條路啊,哈哈。
刪除還是老師厲害,我都不會聯想到望月新一的理論,能跟教授同行,真是榮幸。
刪除這個梯子遊戲,也有數列可以找,就以本題為例,從一橫排開關到 N 排開關,分別有多少種組合不會變更路線結果?也就是每個出發都會回到原來位置。
觀察所得,每兩個1之間間隔奇數個0就可以滿足要求。
刪除或許以這個方向考慮會簡單很多。
噢!這個研究看看。對了,老師的試算表真不易看懂,我想再嘗試Python計算。
刪除關於每兩個1之間間隔奇數個0就可以滿足要求,老師能舉個例子嗎? 因為我檢查 00001111 這個條件就不符。謝謝。
刪除00001111可以看作1010 + 0101
刪除這樣配對就符合要求了。
檢證這些數是否可以表示為,101a + 10001b + 1000001c + 100000001d 即可。
刪除但也發現230(11100110)這個反例。
從老師的提示,發現多數的條件,1 是偶數個,
刪除另外梯子次序先後調換,數值會轉變,例如 01100111 變成 01101110 或是 01101001 (第三四層更換)