趣题:用两枚硬币随机生成 1 到 n 之间的整数

为了随机地并且概率均等地生成一个 1 到 6 之间的整数,通常的做法就是抛掷一个正方体的骰子。不过,这并不是唯一的办法。如果你有一枚公正的、正反概率相同的硬币,以及一枚不公正的、正反概率之比为 1 : 2 的硬币,那么你也能概率均等地生成一个 1 到 6 之间的整数。首先抛掷那枚不公正的硬币,那么结果有 1/3 的概率是正面朝上,有 2/3 的概率是反面朝上。如果出现了正面朝上的情况,那么令 i = 1 ;如果出现了反面朝上的情况,那么就再抛掷那枚公正的硬币,掷出正面则令 i = 2 ,掷出反面则令 i = 3 。最后,再抛掷一次公正的硬币,如果正面朝上则令 j = 0 ,如果反面朝上则令 j = 3 。容易看出, i + j 的值有 1, 2, 3, 4, 5, 6 这六种可能,它们出现的概率是均等的,都是 1/6 。

有人或许会说,用硬币模拟骰子哪有那么复杂,只用一枚公正的硬币就能办到:连续抛掷三次硬币,并且规定掷出“正正正”代表数字 1 ,掷出“正正反”代表数字 2 ,“正反正”为 3 ,“正反反”为 4 ,“反正正”为 5 ,“反正反”为 6 ,掷出“反反正”和“反反反”则重来,这不就行了吗?不过,这种方法有一个局限性:它不能保证整个过程在有限步之内完成。而我们刚才的方法中,总的步骤数有一个上限:三步之内必然完成。

我们的问题是:是否对于所有的正整数 n ,都能找到两枚合适的硬币,使得借助它们便能在有限步之内概率均等地产生一个 1 到 n 之间的整数?

 

 

 

 

 

 

 

 

 

答案是肯定的。接下来,我们将会构造性地证明,不管 n 是多少,我们总能使用正反出现概率分别为 1:1 和 1:(n-1) 的两枚硬币,在有限的步数内达成目的。不妨先以 n = 11 时的做法为例,来说明我们的大致思路。

当 n = 11 时,首先把 1:1 的那枚硬币连续抛掷五次,这会出现 32 种等概率的正反组合,然后抛掷 1:10 的那枚硬币,出现正面和出现反面的概率分别为 1/11 和 10/11 。

抛完这六次硬币后,一共会产生 64 种不同的情况,其中 32 种情况出现的概率都是 (1/32) × (1/11) = 1/352 ,另外 32 种情况出现的概率则都是 (1/32) × (10/11) = 10/352 。我们可以在一个单位正方形里直观地表示出这 64 种情况:先用一系列横线把整个正方形划分成 32 个等宽横条,再在左起 1/11 的地方画一条竖线,把每个横条都分成 1:10 两份。图中的这 64 个区域就对应着可能出现的 64 种情况,每个区域的面积占整个正方形的多少,就表示与之对应的情况出现的概率是多少。我们可以把整个正方形看作是由 32 × 11 = 352 个小格子组成的,那么每个格子的面积都占整个正方形的 1/352 ,左边每个区域都只包含 1 个格子,右边每个区域则都包含 10 个格子。

如果我们能把某些区域指派给数字 1 ,把另一些区域指派给数字 2 ,等等,最后把剩下的区域指派给 11 ,使得分给每个数字的区域都包含 32 个格子,即都占正方形总面积的 1/11 的话,问题就解决了。在上面这个图中,这件事情是可以办到的。每 2 个左边的区域和 3 个右边的区域加在一起,正好组成 32 个格子。这样推算下去,划分出 1, 2, 3, …, 10 的地盘,就会用掉左边的 20 个区域和右边的 30 个区域。最后,左边还剩下 12 个区域,右边还剩下 2 个区域,正好又组成了 32 个格子,它们正好成了 11 的地盘。像刚才所说的那样完成六次抛掷后,看看出现的情况位于哪个数的地盘里,便能等概率地产生 1 到 11 之间的整数了。

同样的思路可以适用于任意正整数 n 。取一枚公平的硬币并连续抛掷 k 次,再抛掷一枚正反概率为 1:(n-1) 的硬币,整个概率空间就被分成了 2k × 2 个区域,左边每个区域都占 1 小格,右边每个区域都占 n-1 小格,所有区域加在一起一共有 2k · n 个小格。我们的目标便是把这些区域重新组合成 n 份,使得每份正好都是 2k 个小格。令 q 等于 2k 除以 n-1 的商,令 r 等于 2k 除以 n-1 的余数,那么每次选择 q 个右边的区域和 r 个左边的区域相搭配,正好就是 2k 小格,可供 1 到 n 中的其中一个数使用。如果 q = r ,那么右边的区域和左边的区域会同时用完,于是大功告成。如果 q > r ,那么右边的区域会率先出现不够用的局面,不过这没有关系:右边的每一个区域都可以等效地用左边的 n-1 个区域来代替,因而不够的话总是能从左边找补回来的。如果 q < r 的话,这就真的不好办了,不过幸运的是,我们还留有一手:我们可以精心选择 k 的值,来避免 q < r 。

比方说,刚才 n = 11 时,我们选择的 k 值为 5 ,此时 2k 除以 n-1 的商 q = 3 ,余数 r = 2 。对于其他的正整数 n ,我们总能选择一个合适的 k ,使得 2k 除以 n-1 的商和余数满足 q ≥ r 吗?是的。我们至少可以这么做:注意到余数 r 始终小于除数 n-1 ,因此我们只需要让商数 q 至少是 n-1 即可;因而,选取足够大的 k ,使得 2k ≥ (n-1)2 ,便能保证 q ≥ r 了。

题目来源:http://www.brand.site.co.il/riddles/201410q.html

37 条评论

  • Scorpio

    赞赞赞!

  • 我草

    我草,牛逼

  • Scorpio

    赞赞赞赞赞赞赞赞赞赞赞赞赞赞赞赞赞赞!

  • reiyawea

    终于等到更新了,又长了一回见识。

  • godultimate24

    M大神这几个月的作品产出量不高,是很忙吗?

  • 老王王

    那么,怎样制造不公平硬币呢?如果造不出,整个问题就是纯蛋疼了。

  • lililioon

    ……于是等12月看M67大大讲解如何用一枚硬币生成随机数

  • 怕死的鬼

    我在想,你怎么去制作一枚正反概率比为1:n的硬币

  • Leo

    不公平的硬币只要调整重心的位置不就可以了吗,两面朝上的几率之比应该和重心到两面距离有关(具体关系交给大神计算),调整重心的位置用两种材料混合就行,为什么你们都觉的不可行。

    • qzane

      因为如果一边重量是1,另一边重量是2,如果把这个硬币竖直摆在桌上,重量1的那面朝上的概率基本是100%,你能明白我的意思吗。

    • Leo

      抛硬币的过程跟你说的操作明显不一样啊,硬币在空中会旋转啊。
      即使你说的成立,“基本是100%”说明硬币并不会因为质量分布不均而使得只有一面朝上,而两面朝上的概率比应该是重心位置的连续函数,所以理论上总能制作出满足一定条件的硬币啊。

  • donate

    。。。6666

  • elf

    正面概率x=(1+1/3^0.5)/2
    满足x^2*(1-x)+x*(1-x)^2=1/6
    投3次
    010+101=001+110=100+011=1/6概率
    一枚硬币投出1/2和1/3

  • elf

    对于1/2和1/n
    取(k+1)n>c(p,2p+1)>=kn
    满足x^p*(1-x)^(p+1)+x^(p+1)*(1-x)^p=1/(2kn)
    x^p*(1-x)^p=1/(2kn)
    x*(1-x)=1/(2kn)^(1/p)

  • Toto

    其实只要一枚公平硬币就够了 =。= ,比如生成6个随机数的时候,连续丢3次硬币,一共有8总组合,令其中6种分别对应1-6,剩下两种奖励重扔一轮!

  • 城南旧事

    春季万物复苏,也是皮肤容易出现问题的时候,对于青春期的少男少女来说,一定要知晓一些祛痘的妙招:

      

      一、祛痘 祛痘小妙招 小妙招第一古方:莹肌如玉散。

      目前中药里面祛痘的古方中最火的要算莹肌如玉散了,莹肌如玉散出自《普济方》,莹 藏宝教你祛痘小妙招,快速简单祛痘 肌如玉散是以楮实、白芨、升麻、甘松、白芷、白丁香、砂仁、糯米末、皂角原料。将这些药材一起研磨成粉,混合均匀后,每天取少量涂脸,即可祛除痘痘,令颜面光洁如玉,因而得名莹肌如玉散。莹肌如玉散配方中不含绿豆,因为绿豆只清表面毒素,而不清皮下痘毒。而是采用了升麻等物,升麻不但能像绿豆一样有清 祛痘产品 热下火的效果,还能升发痘毒,所以祛痘之后一般不复发。莹肌如玉散

  • 城南旧事

    快速,藏宝教你怎 藏宝教你怎么祛痘 么祛痘祛痘小妙招一: 保持良好的生活习惯

      1、注意脸部清洁。

      长痘痘很多时候都是因为油脂分 祛痘小妙招 泌过多堵塞毛孔造成的,因此做好清洁工作就十分必要啦!首先要选择弱酸性的肥皂或刺激性小的洗面奶,在低于体温的温水手中揉搓起泡后捧起来洗脸,轻柔的螺旋式按摩一分钟之后,即可用稍热(比体温高一点)的水冲洗干净了,妙招让你轻松祛痘。每天洗2-3次,别忘了洗脸后上点化妆水,可以保湿并收缩毛孔哦!
    妙招让你轻松祛痘

      2、保证充足的睡眠,。

      睡眠不足会导致肝功能下降,体内毒素无法及时排出,自然也就给了痘痘疯长的机会。想要消灭他们最好在十一点之前睡觉,实在不行也别熬过

  • 城南旧事

    春季万物复苏,也是皮肤容易出现问题的时候,藏宝教你祛痘小妙招,快速简单祛痘,对于青春期的少男少女来说,藏宝教你如何快速祛痘和痘印,一定要知晓一些祛 藏宝教你祛痘小妙招,快速简单祛痘 痘的妙招:

      

      一、祛痘小妙招第一古方:莹肌如玉散。

       藏宝教你如何快速祛痘和痘印 目前中药里面祛痘的古方中最火的要算莹肌如玉散了,莹肌如玉散出自《普济方》,莹肌如玉散是以楮实、白芨、升麻、甘松、白芷、白丁香、砂仁、糯米末、皂角原料。将这些药材一起研磨成粉,混合均匀后,每天取少量涂脸,即可祛除痘痘,令颜面光洁如玉,因而得名莹肌如玉散。莹肌如玉散配方中不含绿豆,因为绿豆只清表面毒素,而不清皮下痘毒。而是采用了升麻等物,升麻不但能像绿豆一样有 祛痘小妙招

  • __ty

    额,我有个问题,你的意思是如果只有一枚公平的硬币,是没有办法保证能有限次模拟一个 1/k 概率的事件吗,那就是说计算机也没有办法做到 这种 吗;
    显然:
    ((rand() % k) == 0) 这种并不是 1/k 的事件,
    只有: while ((t = rand()) >= k) return t == 0;
    这样的才可以吗?

  • elf

    p为大于2的质数,正面概率x的硬币投p次
    x^p+px^(p-1)(1-x)+[p!/(p-2!)2!]x^(p-2)(1-x)^2+…+px(1-x)^(p-1)+(1-x)^p
    其中px^(p-1)(1-x)+[p!/(p-2!)2!]x^(p-2)(1-x)^2+…+px(1-x)^(p-1)系数均为p的倍数
    注意0.5^(p-1)<=x^p+(1-x)^p2
    故存在x满足x^p+(1-x)^p=1/2
    即px^(p-1)(1-x)+[p!/(p-2!)2!]x^(p-2)(1-x)^2+…+px(1-x)^(p-1)=1/2
    x^(p-1)(1-x)+[(p-1)!/(p-2!)2!]x^(p-2)(1-x)^2+…+x(1-x)^(p-1)=1/2p
    这样硬币可投出1/2和1/p
    结合文章这枚硬币可随机出1到p之间所有整数

  • jackymond

    用1和0表示硬币的正反面,重复抛一枚硬币n次,得到n位二进制数,再转换为十进制数。每个数的概率相等,这样就可以随机生成0到2∧n的数。

  • 浣熊

    为什么q小于r就不好办了呀

  • 浣熊

    我甚至可以随机的让这些格子属于某一种情况 只要他们分得的鸽子一样多就好啊, 所以为什么一定要q小于r呢

  • 浣熊

    说反了, 所以为什么一定要q大于r呢?

  • 匿名

    为什么我觉得只需要一枚普通硬币就够了啊,是不是错觉。。。
    N个球,是奇数就补一个假球进去,两两分组,扔硬币决定哪一个进入下一轮
    这样一来每个球进入下一轮的概率都是0.5,然后再对进入下一轮的球进行同样的操作,直至最后只剩一个球,就是产生的随机数
    看上去好像很公平的样子。。

发表评论