從 2010 年開始，東京大学情報理工学系研究科在招生海報都會放上一段藏了訊息的 binary。去年看到這個新聞之後就多留了一份心。前幾個月研究所都在招生，就想到今年的小遊戲也差不多該出了。果然今年他們又延續了海報用和服櫻花妹附上 binary 謎題的這個優良傳統。
拿到海報圖檔之後就開工啦！
首先用 OCR 和人眼把圖檔裡的 01 抽出來，得到
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
0010101100101101001011010010110100101101001010110000101001111100010010010111000001110111011001110111110000 0010100111110001101111001011100010111001110101011111000100010101000110010010000100100100100000010010110100 1110010011110101001000001010011111000110000101100011011101000110111101111100011111000111110001111100011111 0000100000011111000111110001111100011111000000101001111100011101010111001101110111001000010111110001010110 0101011001010110010101100010000001010110010101100101011001010110000010100010101100101101001011010010110100 1011010010101100101101001011010010110100101101001010110010110100101101001011010010110100101011001011010010 1101001011010010110100101011000010100111110000100000011101010110100101101100011111000110111100100000001000 0001110100011111000110100001110111001110100010000001111100011000010110101100101110011110010111110000101101 0011111001010011000010100111110000100000011001100111010000100000011111000101001100101101011101000110111101 1111000110111001110111001011110111001001111100010111110010111101100001011011110111110000101101001111100101 0100000010100111110001110011011000110111100101110011011111000110100101100001011010010010000001111100011011 1100101110011011110010000001111100010111110111010001110100011011000111110000101101001111100101010100001010 0111110001110100011101010111010101100101011111000110111001101110011011100010111001111100011011110110101001 1010110110100101111100011011000110101100101110001000000111110000101101001111100101011000101100010110010000 1010001010110010110100101101001011010010110100101011001011010010110100101101001011010010101100101101001011 0100101101001011010010101100101101001011010010110100101101001010110000101001111100010001110101010001100001 0110010001111100000010100111110001101000001011110111001101100101011111000000101001111100011011000110100000 1000000111001001111100000010100111110001000011010100110111000001000110011111000000101000101011001011010010 1101001011010010110100101011000010100000101001010010011011110111010001100001011101000110010100100000011101 0001101000011010010111001100100000011000110111010101100010011001010010000001100010011110010010000001110010 0110010101110000011001010110000101110100011010010110111001100111000010100101010000101100010010000010110001 0001010010110001010101001011000100111000101100010010010010110001010110001011000100010100101100010100100010 1100010100110010110001001001001011000101010000101100010110010010110001001111001011000100011000101100010101 0000101100010011110010110001001011001011000101100100101100010011110000101000110010001100000011000101011110 0101111000110011001000000111010001101001011011010110010101110011001011100000101000001010011000010101111001 0111100110001000100000011010010111001100100000011101010111000000101101011000010111001001110010011011110111 01110010000001101110011011110111010001100001011101000110100101101111011011100010111000001010 |
一共是 2848 個 0 或 1。
2848 可以被 8 整除，直接把這東西轉換成 binary data 試試，果然得到一份題目的文字檔。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
+----+ |Ipwg| |o..u|EFHI KNOR |acto||||| |||| |usw!|VVVV VVVV +----+----+----+----+ | uil|o t|hw: |ak.y|->S | ft |S-to|nw/r|_/ao|->T |scys|iai |o.o |_ttl|->U |tuue|nnn.|ojki|lk. |->V,Y +----+----+----+----+ |GTad| |h/se| |lh r| |CSpF| +----+ Rotate this cube by repeating T,H,E,U,N,I,V,E,R,S,I,T,Y,O,F,T,O,K,Y,O 201^^3 times. a^^b is up-arrow notation. |
看來是個 4x4x4 的魔術方塊（展開圖），而 E, F, H, I 等等則各是代表轉動魔術方塊的其中一層。接下來我們要做的就是依照他的指示，重複 THEUNIVERSITYOFTOKYO 這個動作 201^^3 次。問題來了，所謂的 201^^3 到底是多少呢？查了一下 Wiki，原來 up-arrow notation 是這個意思。
也就是說，201^^3 代表
\[201 \uparrow\uparrow 3 = 201^{201^{201}}\]
是個超級大的數字！
看到這麼大的數字，第一個想法就是：絕對不會需要轉這麼多次！
首先，就算 4x4x4 的魔術方塊能夠轉出所有的組合（事實上沒辦法），頂多也就
\[(4 \times 4 \times 6)! = 96!\]
這麼多的組合方式。而且，
\[96! < 201^{201} = 201 \uparrow\uparrow 2 < 201 \uparrow\uparrow 3\]
根據鴿籠原理，在不斷重複 THEUNIVERSITYOFTOKYO 這個動作的情況下，因為 \(96! < 201 \uparrow\uparrow 3\)，過程中必然會有轉到之前轉出過組合的狀況（做了多餘的事情）。所以關鍵在於，如何找出方法，轉個少少次，就有轉 \(201 \uparrow\uparrow 3\) 次的效果。
在做更進一步的事情之前，還有一個問題，那就是如何用程式來計算所謂的“旋轉魔術方塊”這件事。
假如我們把魔術方塊上的每個小面都標上編號，所謂的“旋轉魔術方塊”這件事情，就轉變成了“位置與編號的重新對應”。對程式來說，就是決定“新狀態的某個位置根據舊狀態來看，新的編號應該是多少”。舉個例子來說，如果把一個位置代碼和編號一樣的狀態叫做 identity：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
+-----------+ | 0 1 2 3| | 4 5 6 7| | 8 9 10 11| |12 13 14 15| +-----------+-----------+-----------+-----------+ |16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31| |32 33 34 35|36 37 38 39|40 41 42 43|44 45 46 47| |48 49 50 51|52 53 54 55|56 57 58 59|60 61 62 63| |64 65 66 67|68 69 70 71|72 73 74 75|76 77 78 79| +-----------+-----------+-----------+-----------+ |80 81 82 83| |84 85 86 87| |88 89 90 91| |92 93 94 95| +-----------+ |
那 identity 經過 E 這個動作之後，會變成這樣：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
+-----------+ | 0 1 2 3| | 4 5 6 7| | 8 9 10 11| |79 63 47 31| +-----------+-----------+-----------+-----------+ |64 48 32 16|12 21 22 23|24 25 26 27|28 29 30 80| |65 49 33 17|13 37 38 39|40 41 42 43|44 45 46 81| |66 50 34 18|14 53 54 55|56 57 58 59|60 61 62 82| |67 51 35 19|15 69 70 71|72 73 74 75|76 77 78 83| +-----------+-----------+-----------+-----------+ |68 52 36 20| |84 85 86 87| |88 89 90 91| |92 93 94 95| +-----------+ |
只要建立個對照表，讓程式知道如何根據舊狀態建立新狀態就好了。 轉換了問題之後，程式的撰寫就變得簡單了。為了方便起見，我是把它寫成 Python 的一個小 module。其中包含了一個 rotate 的函數，還有一個代表 THEUNIVERSITYOFTOKYO 這個動作的 M。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
# identity element identity = range(4*4*6) rotate_maps = dict() rotate_maps['E'] = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 79, 63, 47, 31, 64, 48, 32, 16, 12, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 80, 65, 49, 33, 17, 13, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 81, 66, 50, 34, 18, 14, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 82, 67, 51, 35, 19, 15, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 83, 68, 52, 36, 20, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, ] rotate_maps['F'] = [ 0, 1, 2, 3, 4, 5, 6, 7, 78, 62, 46, 30, 12, 13, 14, 15, 16, 17, 18, 19, 20, 8, 22, 23, 24, 25, 26, 27, 28, 29, 84, 31, 32, 33, 34, 35, 36, 9, 38, 39, 40, 41, 42, 43, 44, 45, 85, 47, 48, 49, 50, 51, 52, 10, 54, 55, 56, 57, 58, 59, 60, 61, 86, 63, 64, 65, 66, 67, 68, 11, 70, 71, 72, 73, 74, 75, 76, 77, 87, 79, 80, 81, 82, 83, 69, 53, 37, 21, 88, 89, 90, 91, 92, 93, 94, 95, ] rotate_maps['H'] = [ 0, 1, 2, 3, 77, 61, 45, 29, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 4, 23, 24, 25, 26, 27, 28, 88, 30, 31, 32, 33, 34, 35, 36, 37, 5, 39, 40, 41, 42, 43, 44, 89, 46, 47, 48, 49, 50, 51, 52, 53, 6, 55, 56, 57, 58, 59, 60, 90, 62, 63, 64, 65, 66, 67, 68, 69, 7, 71, 72, 73, 74, 75, 76, 91, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 70, 54, 38, 22, 92, 93, 94, 95, ] rotate_maps['I'] = [ 76, 60, 44, 28, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 0, 27, 43, 59, 75, 92, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 1, 26, 42, 58, 74, 93, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 2, 25, 41, 57, 73, 94, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 3, 24, 40, 56, 72, 95, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 71, 55, 39, 23, ] rotate_maps['K'] = [ 0, 1, 2, 19, 4, 5, 6, 35, 8, 9, 10, 51, 12, 13, 14, 67, 16, 17, 18, 83, 68, 52, 36, 20, 15, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 87, 69, 53, 37, 21, 11, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 91, 70, 54, 38, 22, 7, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 95, 71, 55, 39, 23, 3, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 72, 84, 85, 86, 56, 88, 89, 90, 40, 92, 93, 94, 24, ] rotate_maps['N'] = [ 0, 1, 18, 3, 4, 5, 34, 7, 8, 9, 50, 11, 12, 13, 66, 15, 16, 17, 82, 19, 20, 21, 22, 23, 24, 14, 26, 27, 28, 29, 30, 31, 32, 33, 86, 35, 36, 37, 38, 39, 40, 10, 42, 43, 44, 45, 46, 47, 48, 49, 90, 51, 52, 53, 54, 55, 56, 6, 58, 59, 60, 61, 62, 63, 64, 65, 94, 67, 68, 69, 70, 71, 72, 2, 74, 75, 76, 77, 78, 79, 80, 81, 73, 83, 84, 85, 57, 87, 88, 89, 41, 91, 92, 93, 25, 95, ] rotate_maps['O'] = [ 0, 17, 2, 3, 4, 33, 6, 7, 8, 49, 10, 11, 12, 65, 14, 15, 16, 81, 18, 19, 20, 21, 22, 23, 24, 25, 13, 27, 28, 29, 30, 31, 32, 85, 34, 35, 36, 37, 38, 39, 40, 41, 9, 43, 44, 45, 46, 47, 48, 89, 50, 51, 52, 53, 54, 55, 56, 57, 5, 59, 60, 61, 62, 63, 64, 93, 66, 67, 68, 69, 70, 71, 72, 73, 1, 75, 76, 77, 78, 79, 80, 74, 82, 83, 84, 58, 86, 87, 88, 42, 90, 91, 92, 26, 94, 95, ] rotate_maps['R'] = [ 16, 1, 2, 3, 32, 5, 6, 7, 48, 9, 10, 11, 64, 13, 14, 15, 80, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 12, 31, 47, 63, 79, 84, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 8, 30, 46, 62, 78, 88, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 4, 29, 45, 61, 77, 92, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 0, 28, 44, 60, 76, 75, 81, 82, 83, 59, 85, 86, 87, 43, 89, 90, 91, 27, 93, 94, 95, ] rotate_maps['S'] = [ 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, ] rotate_maps['T'] = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 44, 45, 46, 47, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, ] rotate_maps['U'] = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 60, 61, 62, 63, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, ] rotate_maps['V'] = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 76, 77, 78, 79, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 92, 88, 84, 80, 93, 89, 85, 81, 94, 90, 86, 82, 95, 91, 87, 83, ] rotate_maps['Y'] = rotate_maps['V'] def rotate(vector, map): return [vector[map[i]] for i in identity] M = identity for c in 'THEUNIVERSITYOFTOKYO': M = rotate(M, rotate_maps[c]) |
回到一開始的問題，那我麼要怎麼樣簡化那 \(201 \uparrow\uparrow 3\) 次的轉動呢？這裡就必須考慮魔術方塊的兩個特性：
- 狀態數為有限
- 每個動作都是可逆的（就反轉而已）
根據 finite state machine 的理論，我們可以找得到一個最小的正整數 \(n < 96!\) 使得 \[(\text{operation THEUNIVERSITYOFTOKYO})^n \equiv M^n \equiv \text{identity}\] 二話不說，讓我們寫支程式來找看看
|
1 2 3 4 5 6 7 8 9 10 11 |
import rubiks v = rubiks.identity counter = 0 done = False while not done: v = rubiks.rotate(v, rubiks.M) counter += 1 if v == rubiks.identity: done = True print 'n =', counter |
跑完得到 \(n = 1008\)。
也就是說，
\[M^{201 \uparrow\uparrow 3} \equiv M^{(201 \uparrow\uparrow 3)\mod{1008}}\]
計算 \((201 \uparrow\uparrow 3)\mod{1008}\) 的部分我是用 Mathematica 的 PowerMod （拿來做 RSA 也很方便 XD），如果你電腦上沒有 Mathematica，也可以用 Wolfram Alpha 來算。所以我們現在知道
\[M^{201 \uparrow\uparrow 3} \equiv M^{153}\]
只差最後臨門一腳啦！櫻花妹我來了！！！抽出原題目被轉亂的字串，重新轉正。
|
1 2 3 4 5 6 7 8 9 10 |
import rubiks ciphertext = 'Ipwgo..uactousw! uilo thw: ak.y ft S-tonw/r_/aoscysiai o.o _ttltuuennn.ojkilk. GTadh/selh rCSpF' # PowerMod[201, 201^201, 1008] = 153 v = [c for c in ciphertext] for i in range(153): v = rubiks.rotate(v, rubiks.M) print ''.join(v) |
BINGO!
|
1 |
Congratulations!Follow the link.http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka GradSch of IST |
跟著這個連結進去可以聽到一首歌。
最後引用一句 up-arrow notation 發明人的話
Beware of bugs in the above code; I have only proved it correct, not tried it.
— Donald Knuth
我也要說，上面的程式碼雖然在我這裡可以跑，但不保證到其他地方能用。 XD
後記
其實這是一篇測試文。 XD
當初就在想說到底要用什麼樣的主題，才能夠用一篇文章把所有的東西都測過一遍。看來這個主題是挑得不錯，幾乎所有的排版元素和功能都測到了。哈！
喔對了！還有一件事情我一定要補充一下，就是海報和連結裡面的那個女生根本是高中生，請不要以為東大裡面會有這種年輕可愛的美眉。（東大你騙得我好苦啊 QQ）
5 Comments for “東京大学 2013 年小遊戲解析”
kenqq
says:你好,我是做完題目之後,用答案去搜索到貴站的^^
那個153我沒算出來直接跑答案的,我想請教一下計算那個1008的過程,感謝啦~
kenqq
says:沒事打擾啦,我突然想到怎麼算了,打擾了
Kuan-Yi Li
says:No worries! 有些地方我的確是跳得比較快，有任何問題都可以提出來討論。而且我也蠻好奇你所謂直接跑答案的方法是什麼，是一直做 THEUNIVERSITYOFTOKYO 然後用人眼看的意思嗎？
kenqq
says:是的,我把輸出的格式弄成每一個側面的字母鏈接成一行字符串,然後用逗號隔開,把結果複製到csv文件裡面看哪條包含有意思單詞的OTL
之後參考了您的方法之後,就把第一行生成的字符串和之後的每一行做判斷,的確會得出n=1008會重複的現象,現在想起來真是太笨了(黑線
Kuan-Yi Li
says:了解，直接看也不失為一個方法。話說壓根沒想到會有人研究這篇文章，看到讀者有收穫真的很開心。 ^_^