返回   cpper编程论坛 > Blog > Meta
注册账号 论坛帮助 会员列表 日历事件 搜索 今日新帖 标记版面已读

为这篇文章评分

空白骰子问题

发表于 2008-03-27 03:49 PM 作者: Meta
Meta 更新于 2008-04-14 10:46 AM
问题描述:
给出两个六面空白的骰子, 往上面填数字0-6, 使得两个骰子一起掷时1-12出现的概率都是一样的.

分析:
假设这两个骰子分别为A<a1, a2, a3, a4, a5, a6>和B<b1, b2, b3, b4, b5, b6>, 其中 0 <= ai, bi <= 6, 1 <= i <= 6, 两两组合有36种情况(包含重复). 1-12出现的概率一样, 不妨假设他们出现的次数为n, 可以得知1 <= n <= 3. 下面考虑n的三种取值情况:

1. n = 1, 有12个组合分别取值 1 - 12, 其他24个组合全为0. 由此可以得知A, B的六个面: A { 0, 0, 0, 0, 0, 0 }, B { 0, 0, 0, 0, b1, b2 }. 这种假设情况下, b1和b2各出现6次, 很明显与假设是矛盾的, 不成立.

2. n = 2, 有24个组合分别取值 1 - 12, 其他12个组合全为0. 由此可以得知A, B的六个面的两种情况1). A { 0, 0, 0, 0, 0, 0 }, B { 0, 0, b3, b4, b5, b6 }; (2). A { 0, 0, 0, 0, a5, a6 }, B { 0, 0, 0, b4, b5, b6 }. 同理分析, 这两种情况都与假设矛盾, 不成立.

3. n = 3, 有36个组合分别取值 1 - 12. 我们不妨考虑如下两个特殊的数字: 12和1. 对于12, 组成其的唯一可能是2个6, 加上要出现3次, 则有 { 6 }, { 6, 6, 6 }, 于是得到 A { 6, ... }, B { 6, 6, 6, ... }.
对于1, 组成其的唯一可能则是 0, 1, 加上出现3次, 则可能有 { 0, 0, 0 }, { 1 } 或者 { 0 }, { 1, 1, 1 }. { 0, 0, 0 }, { 1, 1, 1 }不可能属于 A, 否则的话, 数字组合6和7出现的次数将会是9次, 与假设是矛盾的. 那么, { 0, 0, 0 }, { 1, 1, 1 } 只可能属于 B.
考察 A { 6, ..., 1 }, B { 6, 6, 6, 0, 0, 0 }. 由于n = 3, 满足条件的组合只可能由A中的6个数字(各不相同)与B中3个0的组合, 将产生 1 - 6数字组合各3个, 不难得知 A { 6, 5, 4, 3, 2, 1 }; 然后将A中数字与B中的3个6组合则得到7-12的组合各3个.
考察 A { 6, ..., 0 }, B{ 6, 6, 6, 1, 1, 1 }. 11这个数字, 只可能有A中5和B中的3个6组成; 如果A中包含5, 则6这个数字组合将要出现6次, 与假设矛盾, 不成立.

因此, 唯一的解就是A { 1, 2, 3, 4, 5, 6 }, B { 0, 0, 0, 6, 6, 6} .
发表在 Algorithm
评论 2 Email文章
评论总数 2

评论

旧
polyrandom 的头像
我有一个肮脏的想法:
如果
A = { 0, 0, 0, 0, 0, 0 }
B = { 0, 0, 0, 0, 0, 0 }
那么1-12出现的概率都为0,符合题目要求,因此这也是一个解。
唉,要是是我去面试,估计就入了。
发表于 2008-04-12 10:19 PM 作者: polyrandom polyrandom 当前离线
旧
Meta 的头像
恩. 1-12的出现次数n的确可以取值为0.
发表于 2008-04-14 10:48 AM 作者: Meta Meta 当前离线
发表评论 发表评论

所有时间均为格林尼治时间 +9。现在的时间是 02:03 PM


Powered by vBulletin® 版本 3.7.0
版权所有 ©2000 - 2008,Jelsoft Enterprises Ltd.
(C) Copy Right All Right Reserved 2001 - 2007

Search Engine Friendly URLs by vBSEO 3.1.0