答案的信息量

cctv2的购物街有个刺激的猜价格 参赛者报出价格 主持人反馈是高是低 选手则要根据这个信息调整自己的猜测直至完全命中。

阿拉丁神灯猜人游戏 http://en.akinator.com/ 你在心中想好一个人，根据这个人的真实资料回答一系列问题，最终给出你心中的那个正确人选。事实上这个游戏的离线版本更是源远流长，其乐无穷。

记得小学兴趣班有个题目，一个人指定一个1024以内的数字，另一个人做猜测，可以问一个是否问题，限十次，答出这个数字。

这一类问题其实统统一样，一个是否问题能够给你的平均信息量在两个答案等概率出现时达到最大值1bit，丢给参与者的问题就变成了如何精心设计你的问题使得它的两个答案出现的几率对半。就购物街问题而言就是迅速估计可能的上下确界，然后二分发问。对于猜人的问题，尽量设计"男/女?"这样的等概率问题。对于猜数字的问题，可以问“这个数字的二进制第N位是1么？”

引起我兴趣的是这样一道题目

有一个黑匣子，黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项，但已知所有的系数都是正整数。每一次，你可以给黑匣子输入一个整数，黑匣子将返回把这个整数代入多项式后的值。有一个不可思议的结论：你可以在两步之内还原出整个多项式！这是如何做到的呢？

首先，输入 1 ，于是便得到整个多项式的所有系数之和。不妨把这个系数和记作 S 。下一步，输入 S + 1 ，于是黑匣子返回

    a_n * (S + 1)ⁿ + a_n-1 * (S + 1)^n-1 + … + a₁ * (S + 1) + a₀

把这个值转换成 S + 1 进制，依次读出每一位上的数，它们就是多项式的各项系数了。

归纳一下这段描述，简单地说，我们通过两个正整数的输入，唯一确定地输出了n+1个正整数。

乍一看来，这是一个无比恐怖的结论，颠覆了信息量守恒的观念：一个随机正整数带来的信息量是多少？假设是Nbit，那么输入2Nbit，得到了(n+1)Nbit，并且n还是不确定的，可以非常大。事实上，我们的两个输入不是完全随机的，第二个正整数必然大于等于第一个正整数，否则与“所有的系数都是正整数矛盾”，因此输入信息量还不到2Nbit。Jesus！问题出在哪里？

问题出在对正整数的信息量度量上。对计算机原理有点了解的同学应该知道，“整数”，随其存储位宽的不同，所能表示的整数范围也是有限的，并不存在一个确定的N，where Nbit能够表示一个随机正整数带来的信息量。事实上，随着正整数的增加，N会越来越大，趋于无穷大。对数字的信息量描述，只有在确定的进制下才有意义，并且度量的对象是一“位”，而不是一个整数。例如在二进制中，一位的信息量是1bit，十进制中是log10 bit，16进制中是4bit。

了解了这个，回到题目中，我们定义p(1)=S, p(S+1)=T。S+1进制中，每一位的信息量是log(S+1)，T是个S+1进制的n+1位数，因此其信息量为(n+1).log(S+1);a0-an每一位数字信息量均为log(S+1)，在我们这个问题里，它们完全独立，因此总信息量即为直接相加，也为(n+1).log(S+1)。

Done

初看到这个问题的时候，我真的被这个信息量不守恒的低级问题深深困扰了。必须承认，毕业之后，思考能力退化了。写下思考过程，自勉。