東京大学 2013 年小遊戲解析

從 2010 年開始,東京大学情報理工学系研究科在招生海報都會放上一段藏了訊息的 binary。去年看到這個新聞之後就多留了一份心。前幾個月研究所都在招生,就想到今年的小遊戲也差不多該出了。果然今年他們又延續了海報用和服櫻花妹附上 binary 謎題的這個優良傳統。

Poster_2013

拿到海報圖檔之後就開工啦!

首先用 OCR 和人眼把圖檔裡的 01 抽出來,得到

一共是 2848 個 0 或 1。

2848 可以被 8 整除,直接把這東西轉換成 binary data 試試,果然得到一份題目的文字檔。

看來是個 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:

那 identity 經過 E 這個動作之後,會變成這樣:

只要建立個對照表,讓程式知道如何根據舊狀態建立新狀態就好了。 轉換了問題之後,程式的撰寫就變得簡單了。為了方便起見,我是把它寫成 Python 的一個小 module。其中包含了一個 rotate 的函數,還有一個代表 THEUNIVERSITYOFTOKYO 這個動作的 M。

回到一開始的問題,那我麼要怎麼樣簡化那 \(201 \uparrow\uparrow 3\) 次的轉動呢?這裡就必須考慮魔術方塊的兩個特性:

  1. 狀態數為有限
  2. 每個動作都是可逆的(就反轉而已)

根據 finite state machine 的理論,我們可以找得到一個最小的正整數 \(n < 96!\) 使得 \[(\text{operation THEUNIVERSITYOFTOKYO})^n \equiv M^n \equiv \text{identity}\] 二話不說,讓我們寫支程式來找看看

跑完得到 \(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}\]

只差最後臨門一腳啦!櫻花妹我來了!!!抽出原題目被轉亂的字串,重新轉正。

BINGO!

跟著這個連結進去可以聽到一首歌。

最後引用一句 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的過程,感謝啦~

Kuan-Yi Li

says:

No worries! 有些地方我的確是跳得比較快,有任何問題都可以提出來討論。而且我也蠻好奇你所謂直接跑答案的方法是什麼,是一直做 THEUNIVERSITYOFTOKYO 然後用人眼看的意思嗎?

kenqq

says:

是的,我把輸出的格式弄成每一個側面的字母鏈接成一行字符串,然後用逗號隔開,把結果複製到csv文件裡面看哪條包含有意思單詞的OTL

之後參考了您的方法之後,就把第一行生成的字符串和之後的每一行做判斷,的確會得出n=1008會重複的現象,現在想起來真是太笨了(黑線

Kuan-Yi Li

says:

了解,直接看也不失為一個方法。話說壓根沒想到會有人研究這篇文章,看到讀者有收穫真的很開心。 ^_^

Leave a Reply

Your email address will not be published. Required fields are marked *

Captcha loading...