分类存档: Math

用六面不均匀的骰子模拟一只六面均匀的骰子

最近被问到了这么一个问题,蛮有意思的. 这里可以做一个额外的限定:在有限的步骤内精确地将发生的事件分割成六个概率为 1/6 的部分,而不是随着操作次数的次数增多趋近 1/6.

经过了一段时间的探索之后,我发现想要通过重复掷固定次数的骰子来达成这一目标,在知道六面各自的概率后,是不存在一个策略可以把所有发生的事件精确地分割成六份的.

我将借助超越数,使用反证法来证明这一点.

为了证明这一点,首先可以做一些化简. 六面的骰子过于复杂,可以先尝试减少到两面,也就是把骰子简化成硬币. 假设这样的策略是存在的,也就是给定一个六面概率不一的骰子及其各面概率后,就可以得到一个正整数 n,然后掷这个骰子 n 次,根据每次掷的结果将结果分为等概率的六份. 然后假设存在一种只有两面的各面概率不一的骰子.

首先,这个两面骰子可以做到六面骰子的效果. 方法是掷三次两面骰子,可以得到八种不同的结果,将这八种结果分为六份(不能有任何一份是空的),就可以得到六个概率不一的事件集. 而根据刚才的假设,知道了六种结果的概率后,把它当作一个六面的骰子,重复 n 次掷骰子的操作,然后就可以得到均匀概率的六组结果. 最后,将这六种结果的其中三种分为一组,另三组分为一组,这样就得到了均匀概率的两组结果. 也就是说,当六面骰子的策略存在的时候,两面骰子的策略也同样存在.

继续阅读 »

Lambert W function 数值计算

由于一些很蠢的原因,我写了一份完全用不着的用于计算 Lambert W function 的 C# 代码. 具体原理是很粗暴的牛顿法求解,但有几个特别处理的地方:

首先是估算. W0比较好处理,其实随便给个初始值就好,我这里选择了偏移后的 ex. 而 W-1 则比较特殊,首先在 x < -2 的部分变成了 concave 的,而且越往左斜率越小,所以一律从 x = -2 开始尝试;而在 -2 < x < -1 的区间内其实也是随便给个初始值就好,我这里选择了偏移后的 cos 函数.

其次是精度处理. 通过 log2x 做差可以求出二进制下的有效数位,然而当 y 值较大的时候其实并不能把完整的 52 位双精度浮点数的小数部分求完整,大概只能求到 47 位左右,所以这里我保守选择了 42 位有效数字.

继续阅读 »

舒兵的教师节礼物 —— Tupper's self-referential formula 使用实测

Tupper's self-referential formula(图片来源:wikipedia

教师节那天中午vIstaswx跑过来跟我讲教师节要送给舒兵(怎么又是舒兵= =)一个图像是”SB”的函数,然后把 Tupper’s self-referential formula 丢给了我。我们首先确定了其中的k值是一段二进制数据,只是排列方式未知,所以首先开始找出这个函数的工作原理:

继续阅读 »

关于“完全无匹配”问题的通式

今天舒兵课末讲了一个“完全无匹配”问题(即有N个对象A和N个对象B分别编号 1,2,3,…,N ,A与B一一组合,要求A与B编号不相同),于是全班陷入了通式计算的苦战中..

在又报废两页草稿纸之后终于得出一个好吓人的通式:

Expression

大致意思是这样:首先求出包括任何匹配的所有情况,然后减去匹配1对的总数,减去2对的,……,减去N对的,最后的结果就是完全无匹配的总数。但是由于计算N对的时候仍然需要用到一个更小范围的完全无匹配,因此这个算法变成了递归算法,只能用计算机求解了。

代码编写上增加了一个缓存,防止重复运算,毕竟输入唯一值输出也是唯一值,而且运算量很可观。

以下是在线计算。注意:由于运算位数不够最高只能求到170,并且23及以上只能用指数方法表示浮点数。

请在上方输入要运算的完全无匹配对象的总数


2016.10.27 更新:通解记作 !n (Derangement/subfactorial) 更简单的递推公式见 http://www.matrix67.com/blog/archives/6665 第二题.