2016年10月5日 星期三

訓練數學感 115 ─ 梯子遊戲 (Ladder Game)

http://4rdp.blogspot.com/2016/10/115-ladder-game.html


大家在學生時代應該都有玩過紙上梯子遊戲,先從左圖上方選一個端點當起點,然後由上而下,遇到橫線連通的地方就轉彎,若遇左右橫線接通時則從中穿越,左圖例子就是從 a 到 A。

請問這八個開關有那些配置,可以得到 (a,b,c) 對 (A,B,C) 的結果?

這個測驗題的構想來自,FB 上一則東森新聞影片,南韓首爾讓捷運車廂內對座乘客有互動的機會,蠻有趣的,希望藉此題目讓大家細思如何控制梯子遊戲互換位置。

19 則留言:

  1. 有四列開關,可以分別討論。
    先假設一列開關。
    ├┘┼┘┤ 全開,設此情況為α。
    此時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種可能。

    回覆刪除
    回覆
    1. 追加
      αββα
      βααβ
      αγγα
      γααγ
      αδδα
      δααδ
      ......
      P(4,2)=12種
      22+12=34

      刪除
    2. 不錯,把橫列兩開關當成一組,每組有四種組合狀況,這樣可以把問題描述簡化很多。
      但是答案總數只有 34 種似乎太少,還有其它組合未考慮到,繼續加油。

      刪除
    3. 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

      刪除
    4. 數字為二進制轉化為十進制的代表數。
      設8個開關為一個二進制數的第1-8位,0為斷開,1為閉合。
      則有0-255共256種方法。以試算表窮舉後轉化爲10進制,如上表。
      希望可以幫西瓜找出遺漏的部分。

      刪除
    5. 這條題目與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)=γβδβ

      刪除
    6. 我有察覺到這似乎和群論有關係,以前也稍微看過相關內容,不過也不熟悉,只能用這種小學生的方式解題。
      改天要好好加強這方面的知識。

      刪除
    7. 我記得你好像還是國中生欸...已經看過群論!?(掩面)
      其實我也只是從網上東看看西看看知道一點,有空要借本書回來好好看看

      刪除
    8. 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
      把老師的解以二進制表示

      刪除
    9. 沒想到這題跟群論有關聯,等兩位研究好,可以當我的老師教一下這部分。

      刪除
    10. 試算表已發送到各位郵箱,缺少00000000這個結果,所以會顯示45

      刪除
    11. 都快要提到阿貝爾集了,看來我們真是跟望月教授在走同一條路啊,哈哈。

      刪除
    12. 還是老師厲害,我都不會聯想到望月新一的理論,能跟教授同行,真是榮幸。
      這個梯子遊戲,也有數列可以找,就以本題為例,從一橫排開關到 N 排開關,分別有多少種組合不會變更路線結果?也就是每個出發都會回到原來位置。

      刪除
    13. 觀察所得,每兩個1之間間隔奇數個0就可以滿足要求。
      或許以這個方向考慮會簡單很多。

      刪除
    14. 噢!這個研究看看。對了,老師的試算表真不易看懂,我想再嘗試Python計算。

      刪除
    15. 關於每兩個1之間間隔奇數個0就可以滿足要求,老師能舉個例子嗎? 因為我檢查 00001111 這個條件就不符。謝謝。

      刪除
    16. 00001111可以看作1010 + 0101
      這樣配對就符合要求了。

      刪除
    17. 檢證這些數是否可以表示為,101a + 10001b + 1000001c + 100000001d 即可。
      但也發現230(11100110)這個反例。

      刪除
    18. 從老師的提示,發現多數的條件,1 是偶數個,

      另外梯子次序先後調換,數值會轉變,例如 01100111 變成 01101110 或是 01101001 (第三四層更換)

      刪除