用正常人的方式在 Go 裡面做大數運算

Go 裡面沒有 Operator Overloading 的功能，所以雖然內建 Big Integer，但長一點的計算會變得很醜，比方說你要算個 (5*2+3*6)%10 好了，樣子就會有點像是

a := big.NewInt(5)
a.Mul(a, big.NewInt(2))
b := big.NewInt(3)
b.Mul(a, big.NewInt(6))
a.Add(a, b)
a.Rem(a, big.NewInt(10))

更複雜一點的算式就更難懂了。其他像是矩陣、分數、向量、多項式或者任何自訂的計算 type，下場都一樣悲慘。
底下是利用內建的 parser，壤我們可以用正常人的語言在 Go 裡面計算。
雖然有人會說什麼失去了編譯時期靜態檢查的特性，但真要比除錯，寫個 E("(5*2+3*6)%10") 絕對比上面一串外星文出錯的機會比較小一點。
可以到 http://play.golang.org/p/Toqkc4XY2J玩玩看。

Read More

Go 1.1 達到類似 Python 的 map 及 list comprehension

Go 1.1 的 reflect 新增了 SliceOf, ChanOf，以及 MakeFunc。
SliceOf 及 ChanOf 可以達到類似於 Python 裡面的 list 及 iterator 的功能，MakeFunc 可以搭配 Call 使用，達到類似 decorator 的功能。
以下是簡單測試了一下 Python 的 map 及類似 list comprehension 的效果。

Read More

Google Jam 2013 資格賽題目的數學證明

這篇用英文打的,就不轉成中文了。原來的題目可以在這裡找到。

$\newcommand{\lyxlock}{}$

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use $0,i,1,-1$ to represent “ “, T, O, X. So if$\left\Vert \sum_{i=1}^{4}a_{i,i}\right\Vert >3$ , then some one won.

2 Problem B. Lawnmower

Theorem.$\left(a_{i,j}\right)$ is a possible pattern if $$a_{i,j}=\min\left(\max\left(\left\{ a_{i,k}\right\} \right),\max\left(\left\{ a_{k,j}\right\} \right)\right)$$ for every $i,j$ .

Proof.

Can be easily proved by induction on $N=\sum_{i,j}M-a_{i,j}$ , where $M=\max\left(\left\{ a_{i,j}\right\} \right)$ .

         

     

3 Problem C. Fair and Square

Let $$N=a_{n}10^{n}+a_{n-1}10^{n-1}+\cdots+a_{1}10+a_{0}$$ , where $a_{i}\in\left\{ 0,1,\ldots9\right\}$ and $a_{n}\neq0$ . Denote by $\delta_{k}\left(x\right)$ the $\left(n-k+1\right)$ -th digit of $x$ , then we have $\delta_{k}\left(x\right)=a_{k}$ .

Assume $N$ is a palindrome, i.e., $a_{i}=a_{n-1}$ for every $i$ .

Let $b_{k}$ be the coefficient of $x^{k}$ of $$\left(a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}+a_{0}\right)^{2},$$ that is, $$b_{k}=\sum_{i=\max\left(0,k-n\right)}^{\min\left(k,n\right)}a_{i}a_{k-i}.$$

Theorem. $N^{2}$ is also a palindrome iff $b_{k}\leq9$ for all $k$ .

Proof.

($\Leftarrow$ )

Trivial.

($\Rightarrow$ )

Observe that $b_{k}=b_{2n-k}$ for all $k$ . We prove the statement by mathematical induction on $k$ for $k\leq n$ .

Case $k=0$ :

Since $$a_{n}^{2}10^{2n}\leq N^{2}<\left(a_{n}+1\right)^{2}10^{2n}$$ and $$\delta_{0}\left(N^{2}\right)=\delta_{0}\left(a_{0}^{2}\right)=\delta_{0}\left(a_{n}^{2}\right),$$ it is easy to see that $a_{0}=a_{n}\in\left\{ 1,2,3\right\}$ . So $b_{0}=a_{0}^{2}\leq9$ .

Moreover, we also know that $N^{2}$ has $2n+1$ digits and hence $\delta_{2n-k}\left(N^{2}\right)=\delta_{k}\left(N^{2}\right)$ for all $k\leq2n$ .

Case $k>0$ :

Suppose $b_{i}\leq9$ for all $i<k$ , we want to show $b_{k}\leq9$ .

By the induction hypothesis, we know that $\delta_{2n-i}\left(N^{2}\right)=\delta_{i}\left(N^{2}\right)=b_{i}=b_{2n-i}$ for all $i<k$ . So

$$\begin{eqnarray*} 10^{2n-k-1}\cdot\left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \sum_{i=2n-k-1}^{2n}\delta_{i}\left(N^{2}\right)10^{i}\\ & = & \sum_{i=2n-k-1}^{2n}b_{i}10^{i} \end{eqnarray*}$$

On the other hand, $$\begin{eqnarray*} \left\lfloor \frac{N^{2}}{10^{2n-k-1}}\right\rfloor & = & \left\lfloor \frac{\sum_{i=0}^{2n}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor \\ & = & \frac{\sum_{i=2n-k-1}^{2n}b_{i}10^{i}}{10^{2n-k-1}}+\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor . \end{eqnarray*}$$ Therefore, $\left\lfloor \frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k-1}}\right\rfloor =0$ , hence $$b_{k}=b_{2n-k}\leq\frac{\sum_{i=0}^{2n-k}b_{i}10^{i}}{10^{2n-k}}<10.$$

  

  

Corollary. $N^{2}$ is also a palindrome iff $\sum_{i=0}^{n}a_{i}^{2}\leq9$ .

Proof.

$b_{n}=\sum_{i=0}^{n}a_{i}a_{n-i}=\sum_{i=0}^{n}a_{i}^{2}$ .

($\Leftarrow$ )

$b_{n}\geq b_{k}$ for every $k$ by Cauchy-Schwarz inequility.

($\Rightarrow$ )

Trivial.

In particular, if $N\neq3$ , then $a_{i}\in\left\{ 0,1,2\right\}$ .

4 Problem D. Treasure

Let $T\subseteq\mathbb{N}$ be the set of all key types. Assume $0\notin T$ .

Construct a directed graph $G=\left(V,E\right)$ as following:

• $V=T\cup\left\{ 0\right\}$
• $\left(0,j\right)\in E$ iff we starts with at least one key of type $j$ .
• If $i\neq0$ , then $\left(i,j\right)\in E$ iff there is a key of type $j$ in a box of type $i$ .$b_{n}\geq b_{k}$ for every palidrone $N$ by Cauchy-Schwarz inequility.

Denote by $B\left(i\right)$ the number of boxes of type $i$ and $K\left(i\right)$ the total number of keys of type $i$ (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Proof.

($\Rightarrow$ )

If $B\left(j\right)>K\left(j\right)$ , then we don’t have enough keys of type $j$ to open all boxes of type $j$ .

If there is no path from $0$ to $j$ , then it means we are unable to get any key of type $j$ .

($\Leftarrow$ )

We prove this by induction on the number of boxes. Denote by $N$ the number of boxes.

Assume for every $j\in T$ , $B\left(j\right)\leq K\left(j\right)$ and there is a directed path from $0$ to $j$ in graph $G$ .

Case $N=1$ :

Then all vertices in $G$ are leaves except $0$ and the type of the only box. So there must be an edge from 0 to the type of the box.

Case $N>1$ :

Suppose the theorem holds for the case with $N-1$ boxes.

There are at least one $\left(0,i\right)\in E$ . Consider we open a box of type $i$ (that contains a key of type $i$ if possible). Assume we destroy the key and the box just opened, then we have a setting of $N-1$ boxes. In this setting, we still have $B\left(j\right)\leq K\left(j\right)$ for all $j$ . Let $G'=\left(V',E'\right)$ be the directed graph of this $\left(N-1\right)$ -box setting.

If $B\left(i\right)=1$ , then all children of $j$ in $G$ become children of $0$ , $0$ can still reach all other types in $G'$ .

Assume $B\left(i\right)>1$ .

If $\left(i,i\right)\in E$ , then we can open a box of type $i$ that contains a key of type $i$ .

Otherwise, because $K\left(i\right)\geq B\left(i\right)>1$ , we still hold at least one key of type $i$ after we open a box of type $i$ (and destroy the key).

Either way, $\left(0,i\right)\in E'$ . Therefore, for every child $j$ of $i$ in $G$ , either

1. $\left(0,j\right)\in E'$ (if a key of type $j$ is in the box we just opened), or

2. $\left(i,j\right)\in E'$ and so there is a path from $0$ to $i$ and then to $j$ .

So $0$ can still reach very vertex in $G'$ .

By induction hypothesis, the remaining $N-1$ can also be opened.

  

  

By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.

However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.

The solve the problem, you should open the box with smallest number such that either this box is the last one of type $i$ or there is still a way to get a type $i$ key.

---

Document generated by eLyXer 1.2.5 (2013-03-10) on 2013-04-16T11:23:46.409386

Read More

悖論的演講投影片

這是今天在 IMO 第二階段選訓營的投影片內容，簡報內容改自以前通識課的演講。但聽眾不同，所以內容還是差異不少。一些東西有講，沒有在簡報裡。許多圖取自 wikipedia 的 CC 圖片，投影片裡沒有註明，但是演講時都會口頭提到。

Read More

魔術師的小朋友問題

（圖由 seanmcgrath CC-BY 授權）

緊接著 Party 魔術的互動表演後，你拿出繩子準備表演「剪繩還原」。

預想著熟悉到不能再熟悉的程序，你的嘴角不禁微微上揚。
如果說有什麼讓你得意的表演，那這套「剪繩還原」就是。
在幾個精心設計的橋段和對白之後，繩子將被觀眾剪成幾段。
然後，你會對繩子吹口氣，將早已由觀眾剪斷的繩子回復原狀。現場的氣氛將達到最高潮。
這不是連一般業餘魔術師也會一點的剪繩還原效果。
你手中的這條繩子，在配合獨門技法和心理鋪陳後，將會充滿不可思議的魔法。
這不是普通的剪繩還原，這是你的剪繩還原。
繩子是貨真價實的被剪斷了，而最後，繩子也紮紮實實的還原了。過程絕對透明，完全沒有任何作弊的可能。

你還記得上次表演後，觀眾驚奇的表情，不可置信的反覆檢查繩子，企圖找到一點蛛絲馬跡。

當然，他們沒有找到。

在確定沒有任何作弊的可能後，像數學證明一樣的必然，觀眾們只能承認事實只有一種可能性，那就是繩子真的還原了。

這樣，他們心滿意足的做出結論（或更貼切的說，再度確認）：這個世界上確實存在著超越人類理解的神秘事物。

晚上，他們將伴著好夢入睡，以愉快的心情面對未來生活中的挑戰，懷抱希望！
你並沒有花太多力氣，就能記住了這些細節。因為每次表演後都是一樣的情形！沒有例外。
即使是最疑心頑固的觀眾，也一樣。就算是剛才那幾個小搗蛋鬼也一樣。
因為這是你的責任，你身為魔術師的責任。所以你希望能讓觀眾感受到驚奇帶來的愉悅感。

而「剪繩還原」從來沒有讓你失望過!

就在你拿出繩子後，突然聽見一位小朋友在台下大聲說：「我看過了耶...你是不是要學電視上大魔競的剪繩還原？」。

「天哪！我連剪刀都還沒拿出來啊。」你心中跑出來這樣一句話。

這麼直接的把梗破掉，那還怎麼變？好好的魔術就這樣被浪費了？我的剪繩還原就這樣被糟蹋掉了？

不過，那不是你心中跑出來的第一句話。雖然很容易就被忽略掉，但你腦海浮現的第一句話是：「我想拿個榔頭把釘子鎚下去」

一般人大概只會把它當成腦中那種不經意出現的靈光。因為和現在遇到的危機毫無關聯，所以很容易就一閃而過。
但這句話並沒有在你腦中一閃而過。你不是一般人。事實上，你非常清楚它是怎麼跑出來的。

「如果榔頭是你唯一的工具，那你會習慣把問題當成是釘子。」這是心理學家 Abraham Maslow 的名句。
其實你並不清楚 Abraham Maslow 和他的需求層次理論是什麼，又或者他在什麼場合下說過這句話名言。

你也不想知道。

你是在「如何處理搗蛋者」這本書的介紹裡看到這句話的。
也許在潛意識裡，你把小朋友當成了釘子。
不過，不需要什麼人本主義理論，也知道在這裡拿榔頭打小孩，似乎不太適當。這還真是個難題啊。

相當然爾，書裡應該有提到處理這種狀況的方法。

問題是你沒看過。

這次，你要靠你自己解決這個問題。

他為什麼會講這句話？他想說些什麼？
也許他完全沒有惡意。也許只是像「蔡依林，我在電視上看過耶。你是我電視上看過的同一個蔡依林嗎？」或者「搓牌我知道耶，你要學電影上賭聖的特異功能搓牌嗎？」。
你想，大概只要回答說「半對半不對，你等下耐心看看就知道我的意思了」
當然，你不用解釋半對指的是「剪繩還原」，而半不對則是說你不是學電視的，你的程序和梗更高級，更有趣。但只要這樣利用話語的模糊性，就能繼續保持懸疑性。
但問題的不光是他想說什麼。觀眾不只一人。更重要的可能是其他人怎麼解讀他的意思。

所以，你想好要怎麼回答了。

「小朋友，你好厲害喔，你一定了看很多電視吧」明褒暗貶，說不定等下回去，他一個星期就只能看一個小時電視了。算是給搗蛋者小小的懲罰吧。
不過小朋友顯然只能看到光明的，高興的點了點頭。

「所以，有多少人曾經在電視上看過用繩子魔術的？沒有關係，舉手給大家看看。」
當然，你注意到說的是「繩子魔術」，沒有必要把「剪繩還原」的效果一直重複先講。你也可以舉例說，像是綁人、打結這類的，提醒大家繩子的魔術有很多種。
但是現在，你覺得光是這樣說應該就夠了。你很小心，你很確定你還沒有真的承認你要變「剪繩還原」。當然你也絕對沒有否認。
也許跟一般人的常識相反，但魔術師其實是不能說謊的。至少不應該在表演時說。
你也注意到你說的是「繩子魔術」而不是「魔術」。因為你也不想有太多人舉手。雖然那不會是太大的問題。

「好的，那有多少人在現場看過呢?不只是在電視上而已喔！請舉手。」
其實這本來就不是什麼大問題。你的表演本來就有價值，你根本不需要誇大。現場看到的本來就比電視上看到要好得多。
籃球轉播跟現場看哪個好？
演唱會轉播跟參與現場演唱會哪個好？
在電視上看美國跟去美國哪個好?
這些是每個人都知道的常識，你只要提醒他們而已。
還是有好幾個人舉手，現在魔術的風氣挺不錯的，比十幾年前好太多了。但是你也不排除其中有幾個是想表現自己見多識廣的那種類型。

「那有多少人不只在現場看過，而且還上台當助手幫忙？」
剛才殘餘的幾隻手也放下了。不過即使還有一兩個人舉手也無妨。
因為很快就會被一堆手淹沒。
「現在，」你停頓了一下，「有誰想要上台來，不但能當助手幫忙，近距離看，而且還有機會施展魔法喔！想要上來幫忙的朋友，請舉起手來。」
經過你的提醒，觀眾意識到你表演的價值，瞭解到這個機會有多難得，也瞭解到拿電視上的表演跟現場表演比有多蠢。
你不用花太大力氣，因為這些是大家本來就知道的事實。
在許多擺動的手之中，你挑了一個適合當助手的觀眾上台。當然，你聽得到許多落選者帶點失望的聲音，但當你要他們為上台來幫忙的觀眾鼓掌時，掌聲依然非常熱烈。
你知道他們已經把自我移情到上台來的觀眾身上，一個因為這個難得機會能現場、即時參與神秘魔術表演而變得不平凡的平凡人。

接下來，修改一下程序吧，你想。改成讓觀眾吹口氣，讓繩子還原比較好。
因為你剛才說過，不但讓他上台當助手，還有機會施展魔法。也許跟一般人的常識相反，但魔術師其實是不能說謊的。至少不應該在表演時說。
咦，還是只能在表演時說謊？
你也搞不太清楚了。

──

2008年的舊文修改重貼

Read More

沒國際觀是因為媒體很爛，那然後呢?

最近你可能看到不少人在轉這篇清大彭明輝教授部落格的文章：台灣有一種病，很深，深到…………。內容大致上是說，台灣人欠缺國際觀，並非因為英文很差，而是因為媒體太爛。

我並非不同意他觀察到的現象。如果媒體增加國際新聞以及有深度的報導，的確會提升整體民眾的國際知識。

當然很多人會開始轉台，轉去看新聞龍捲風、台灣龍捲風或者狂愛龍捲風之類的東西。

但至少，看新聞鬼扯節目可以增加星際觀，還能訓練資訊過濾的能力。

本土長壽劇裡早晚會有跨國企業鬥爭，然後牽扯到國際政治軍事角力的劇情。順帶還可以介紹一些醫療科技，比方電子義肢、電子眼、換臉、複製人之類的，對劇情鋪陳應該很有幫助。

偶像劇也可以有像是與 CIA 情報頭子的浪漫邂逅，相知相遇、進而定情的故事。當然中間會穿插許多跟國際情勢息息相關的劇情，比方男主角有一筆征討利比亞的私人軍費無法兌換的落難情節，獲得女主角援助後，主角擊敗格達費，然後駕著直升機前來求婚。

所以我完全同意如果媒體增加國際深度，就會增加整體國民的國際觀的這個因果關係。

但全世界最沒用的就是這個｢如果｣。

這樣的說法，就像說：你被曬傷，並非因為你沒擦防曬油就出門，而是因為太陽太大。如果太陽沒有那麼大，就不會被曬傷了。

有用的是，要怎麼讓如果不再是如果。

媒體太爛已經是常識了。但原因呢？要怎麼改善？

媒體中並非沒有外國新聞的資訊，如文茜世界週報、公視新聞、還有一些時段比較少的國際新聞。但為什麼這麼少？是財團控制？還是民眾口味的問題？還是市場太小？

我不知道，但有很大的機會是，暫時很難改變這個情況。

就像我們知道地球與太陽的關係並非宇宙中星球的常態，但我們就是生活在地球上啊。

就是因為台灣媒體很爛，才要加強英文或其他外文能力，特別是聽讀能力。這樣，才能突破限制，得到需要的資訊。

當然我們也許會希望很多人來翻譯資訊，但我們真的願意讓這麼多有用人力來做這些事嗎？還是讓他們做些更有創造力的事情？這是需要計算的。

要改變媒體，並非不可能，而且是持續要做的事。但對個人來說，加強英文能力是現階段就可行，可以突破媒體限制的作法。

在你還沒想到怎麼讓太陽不要發出紫外線之前，看到別人宣導擦防曬油或著撐傘，其實不用憂慮別人不知道真正的原因是太陽太熱。

畢竟，如果不知道太陽太熱，為什麼要擦防曬油或撐傘？

Read More