Guessing numbers with wrong answers (Q)

在 Math Overflow 上看到的有趣問題!
假設給定平常常見的猜數字遊戲:
在 1~1000 當中選擇一個數字, 請問最少要多少次可以猜出來?
有經驗的玩家一定知道切半法是最好的答案, 因此是 10 次.

這是, 若我們假設回答問題的人會有一次的機會回答錯誤,
請問這時猜的人最少要多少次才能猜對?

晚點再來寫答案!

Encoding unordered tree and SP-graph in optimal length

哈哈，結果跟老師一討論，好像很簡單的 separator 就可以做到 optimal 了，
不管 optimal 是多少XD (好像是在 1.58n 左右？)
SP-graph 就用他的 decomposition tree 的 separator 就可以了，
應該會一對一對應:]

果然簡單的問題早就被做光了XD
--
看到幾個有趣的 blog ，(像是 Lipton 的)
Wordpress 可以用 LaTeX 耶...
好吸引人喔，要不要搬過去呢？

SP-graph succinct encoding

這是學姊最近在做的問題：

對於一個 n-node 的 SP-graph，
有沒有一個 encoding 的方法能做到 4n+o(n)?

在想這個問題的過程，
發現 unlabeled unordered tree 好像還沒有低於 2n+o(n) 的 encoding!

說不定這是一個可以想的方向？