松鼠博士的魔法眼鏡

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

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


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

Go 1.1 的 reflect 新增了 SliceOf, ChanOf，以及 MakeFunc。
SliceOf 及 ChanOf 可以達到類似於 Python 裡面的 list 及 iterator 的功能，MakeFunc 可以搭配 Call 使用，達到類似 decorator 的功能。

2013年4月15日 星期一 $\newcommand{\lyxlock}{}$

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use to represent “ “, T, O, X. So if, then some one won.

2 Problem B. Lawnmower

Theorem. is a possible pattern if for every .
Proof.
Can be easily proved by induction on , where .

3 Problem C. Fair and Square

Let , where and . Denote by the -th digit of , then we have .
Assume is a palindrome, i.e., for every .
Let be the coefficient of of that is,

Theorem. is also a palindrome iff for all .
Proof.
()
Trivial.
()
Observe that for all . We prove the statement by mathematical induction on for .
Case :
Since and it is easy to see that . So .
Moreover, we also know that has digits and hence for all .
Case :
Suppose for all , we want to show .
By the induction hypothesis, we know that for all . So
On the other hand, Therefore, , hence

Corollary. is also a palindrome iff .
Proof.
.
()
for every by Cauchy-Schwarz inequility.
()
Trivial.
In particular, if , then .

4 Problem D. Treasure

Let be the set of all key types. Assume .
Construct a directed graph as following:
• iff we starts with at least one key of type .
• If , then iff there is a key of type in a box of type . for every palidrone by Cauchy-Schwarz inequility.
Denote by the number of boxes of type and the total number of keys of type (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every , and there is a directed path from to in graph .
Proof.
()
If , then we don’t have enough keys of type to open all boxes of type .
If there is no path from to , then it means we are unable to get any key of type .
()
We prove this by induction on the number of boxes. Denote by the number of boxes.
Assume for every , and there is a directed path from to in graph .
Case :
Then all vertices in are leaves except and the type of the only box. So there must be an edge from 0 to the type of the box.
Case :
Suppose the theorem holds for the case with boxes.
There are at least one . Consider we open a box of type (that contains a key of type if possible). Assume we destroy the key and the box just opened, then we have a setting of boxes. In this setting, we still have for all . Let be the directed graph of this -box setting.
If , then all children of in become children of , can still reach all other types in .
Assume .
If , then we can open a box of type that contains a key of type .
Otherwise, because , we still hold at least one key of type after we open a box of type (and destroy the key).
Either way, . Therefore, for every child of in , either
1. (if a key of type is in the box we just opened), or
2. and so there is a path from to and then to .
So can still reach very vertex in .
By induction hypothesis, the remaining 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 or there is still a way to get a type key.

魔術師的小朋友問題 （圖由 seanmcgrath CC-BY 授權）

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

「如果榔頭是你唯一的工具，那你會習慣把問題當成是釘子。」這是心理學家 Abraham Maslow 的名句。

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

「所以，有多少人曾經在電視上看過用繩子魔術的？沒有關係，舉手給大家看看。」

「好的，那有多少人在現場看過呢?不只是在電視上而已喔！請舉手。」

「那有多少人不只在現場看過，而且還上台當助手幫忙？」

「現在，」你停頓了一下，「有誰想要上台來，不但能當助手幫忙，近距離看，而且還有機會施展魔法喔！想要上來幫忙的朋友，請舉起手來。」

──
2008年的舊文修改重貼