清MM赌钱

constant · 发表于 2006-2-17 21:38:15

难度：+++

清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:54

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

constant · 发表于 2006-2-17 23:16:37

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

QL · 发表于 2006-2-18 06:25:53

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:05

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

寒潭清 · 发表于 2006-2-18 06:46:02

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

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

99-99 · 发表于 2006-2-18 07:25:20

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

，形象感

寒潭清 · 发表于 2006-2-18 07:41:27

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

constant · 发表于 2006-2-18 22:32:29

还能更好吗？

野菜花 · 发表于 2006-2-19 05:51:15

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

N位数。

前

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

后面

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

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

constant · 发表于 2006-2-19 17:19:47

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

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

野菜花 · 发表于 2006-2-19 19:06:29

起先看到条件

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

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

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

constant · 发表于 2006-2-20 20:20:48

Thanks! 还是你的题踹的人多

野菜花 · 发表于 2006-2-20 22:00:53

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

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

		自动登录	找回密码
密码			立即注册

动态微博

清MM赌钱

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

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

回复：清MM赌钱

回复：清MM赌钱

[:O]咋半天没来,大家都大讨论清MM赌钱了?赌钱可不好[:E]不过,俺赢的钱拿来奖励答对者,加油

这个题编得很有意思，很有亲切感[@};-]，形象感[@};-]

同意,constant的题都是精品,很好的 [:B] [@};-][@};-][>:D<]

good

另一个方法

Very nice

Thanks!

Thanks! 还是你的题踹的人多 [:)][:B][:D)][:E][:))]

可能因为我的题目比较容易踹[:))]long weekend有这么多人来看你的题也不容易了[:B]