珍珠湾ART

标题: 清MM赌钱 [打印本页]

作者: constant 时间: 2006-2-17 21:38
标题: 清MM赌钱

难度：+++

清MM去赌场赌钱，规则如下：赌场有2N个盒子，每个盒子里有一个一块钱的硬币。先交N块钱，然后猜每个盒子里硬币是正面还是反面向上，猜对一个得一块钱。www.ddhw.com

清MM有个头发和她一样多的朋友花儿MM在赌场上班，花儿MM事先知道所有2N个硬币的状态，她可以把这个信息传递给清MM，由于技术条件限制，她只能传递N个bits的信息。（例如她能传出一个0到2^N-1之间的整数。）

在花儿MM的帮助下，清MM最少能赢多少钱？平均能赢多少钱？显然，如果花儿MM把前N个结果传递给清MM，后N个让她自己猜，则清MM 最少赢零块（也就是说可以确保不输），平均可以赢Ｎ/2块钱。我们的问题是两个MM是不是找到更有效的办法，使得清MM能确保赢钱。（假设清MM很不会猜，每次都猜错。）

本贴由[constant]最后编辑于：2006-2-18 19:35:46

作者: 野菜花 时间: 2006-2-17 22:53
标题: "她只能传递N个bits的信息"意思是可以传一个由N个数(在0和2N-1之间的数)组成的序列吗？

"她只能传递N个bits的信息"意思是可以传一个由N个数(在0和2N-1之间的数)组成的序列吗？

作者: constant 时间: 2006-2-17 23:16
标题: 是一个在0和2^N-1之间的数，刚才打错了

是一个在0和2^N-1之间的数，刚才打错了

作者: QL 时间: 2006-2-18 06:25
标题: 回复：清MM赌钱

The first N-1 bits indicates the real state of the coins in the first N-1 boxes. For the last bit, 0 means there are at least 50% heads for the remaining N+1 boxes, 1 otherwise. An income of ceil ((N+1)/2) -1 is guaranteed.

By the way, 每次都猜错 is quite some talent, you can simply bet the opposite to win each single time.

作者: QL 时间: 2006-2-18 06:32
标题: 回复：清MM赌钱

A more difficult question might be: what is the maximum expected income?

作者: 寒潭清 时间: 2006-2-18 06:46
标题: [:O]咋半天没来,大家都大讨论清MM赌钱了?赌钱可不好[:E]不过,俺赢的钱拿来奖励答对者,加油

咋半天没来,大家都大讨论清MM赌钱了?赌钱可不好

不过,俺赢的钱拿来奖励答对者,加油

作者: 99-99 时间: 2006-2-18 07:25
标题: 这个题编得很有意思，很有亲切感[@};-]，形象感[@};-]

这个题编得很有意思，很有亲切感

，形象感

作者: 寒潭清 时间: 2006-2-18 07:41
标题: 同意,constant的题都是精品,很好的 [:B] [@};-][@};-][>:D<]

同意,constant的题都是精品,很好的

作者: constant 时间: 2006-2-18 22:32
标题: good

还能更好吗？

作者: 野菜花 时间: 2006-2-19 05:51
标题: 另一个方法

花儿给清儿传一个两进位制的

N位数。

前

N/2 位数字指明前 N/2 个盒子的情况。

后面

3N/2 个盒子，按次序3个一组，后 N/2 个数字，每个对应3个盒子，1表示这3个盒子中正面多，0表示反面多。

此法与QL的方法，赢钱的下界好像相同，不知平均期望值哪个高

作者: constant 时间: 2006-2-19 17:19
标题: Very nice

这个方法和原题的解答一样。和QL的解比较，下界是一样的，都是0.5N，但期望值好一些，是0.625N。QL的解期望值比较难算，可能要用中心极限定理。我觉得是0.5*（N+sqr(N))左右。

题贴出来以后，我又想到一个更好的方法，所以把难度也提高到+++。

作者: 野菜花 时间: 2006-2-19 19:06
标题: Thanks!

起先看到条件

(假设清MM很不会猜，每次都猜错), 以为必须给出至少N+1个盒子的确定信息，后来看来QL的解才知道: 每次都猜错是在完全随机的情况。

我想了这个方法后，一算和

QL的解的下界完全相同(不论N是奇数还是偶数)，就不想贴了。昨晚想想贴出来至少说明我 try (踹 ) 过了

作者: constant 时间: 2006-2-20 20:20
标题: Thanks! 还是你的题踹的人多 [:)][:B][:D)][:E][:))]

Thanks! 还是你的题踹的人多

作者: 野菜花 时间: 2006-2-20 22:00
标题: 可能因为我的题目比较容易踹[:))]long weekend有这么多人来看你的题也不容易了[:B]

可能因为我的题目比较容易踹

long weekend有这么多人来看你的题也不容易了

欢迎光临珍珠湾ART (http://zzwav.com/)