数学研发论坛

 找回密码
 欢迎注册
查看: 6746|回复: 55

[原创] 猜排列问题

[复制链接]
发表于 2012-4-1 21:40:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
KeyTo9_Fans将一副扑克洗牌后得到一个$52$张牌的排列,让mathe猜之。

mathe给出一个$52$张牌的排列后,KeyTo9_Fans进行检验和比对。

精华
然后告诉mathe猜对的数量:“猜对$0$张”,“猜对$1$张”,……,或者“猜对$52$张”。

如果没有全部猜对,则mathe继续猜,KeyTo9_Fans继续告诉mathe猜对的数量,直到mathe全部猜对为止。

问:mathe全部猜对所需次数的期望值是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 09:49:32 | 显示全部楼层
1# KeyTo9_Fans

KeyTo9_Fans和mathe 玩猜猜看游戏啊,KeyTo9_Fans 可以试试这样告诉mathe,
“mathe,你真有才,虽然猜错了50棵牌, 但猜对了第12,第34棵牌,值得鼓励,再接再厉啊”
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-4-2 11:27:56 | 显示全部楼层
“mathe,你真有才,虽然猜错了50棵牌, 但猜对了第12,第34棵牌,值得鼓励,再接再厉啊”

这样的回复可以使mathe在$O(N)$的次数内全部猜对。

其中$N$是扑克牌的数量。

像$1$楼那样的回复,mathe好歹也得猜$\Omega(N\log N)$次吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 12:24:26 | 显示全部楼层
或者这样算:
设p=1/52!,则期望值为:
$\sum_{n=1}^{+infty} n*(1-p)^{n-1}*p =1/p=52!$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-4-2 12:39:52 | 显示全部楼层
mathe猜对之前Fans不洗牌。

也即是说,mathe猜的一直是同一个排列。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 13:09:42 | 显示全部楼层
1张牌,不用猜
2张牌,猜1次就足够。
3张牌,1/6一次猜对,5/6两次确定序列,所以期望值为11/6
即E(1)=0
E(2)=1
E(3)=11/6

E(n)<< n!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 13:13:34 | 显示全部楼层
关键是n这么大,如何确定最佳方案。
这么多方案,确定哪种是最佳,还是很不容易的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 15:00:02 | 显示全部楼层

回7#,一次说中也算猜了一次

1张牌,一说即中,P(1)=1,E(1)=1
2张牌,P(1)=1/2,P(2)=1/2 ,所以E(2)=3/2
3张牌,首次,P(1)=1/6,P( 猜对0张)=1/3, P(猜对1张)=1/2,
        当首次猜对0张时,P(2)= P(3)=1/6
        当首次猜对1张时,P(2)= P(3)= P(4)=1/6
所以 P(2)=P(3)=1/3, P(1)=P(4)=1/6
所以 E(3)=P(1)+2P(2)+3P(3)+4p(4)=1/6+2/3+3/3+4/6=5/2
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 20:06:53 | 显示全部楼层
9# hujunhua
正确,7楼看错了,两次不能确保知道
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-2 20:43:44 | 显示全部楼层

n=3张牌的猜牌进程表

把mathe第1猜所选的排列记为123
A0
123, 132, 321, 213, 231, 312
G1
3
1
0
A1
123
132,  321, 213
231, 312
G2
3
1
0
3
1
0
A2
132
/
321,  213
231
/
312



G3
3
1
0

3
1
0


A3
321
/
213


312
/
/





G4
3
1
0










A4
213
/
/




解释一下:

1、G1,G2,G3表示mathe第1猜,第2猜,第3猜猜对的数量。Gk=2不可能,故所在行只分为3,1,0三列。
2、A1,A2,A3表示mathe根据Fans提示的猜对数量作出的排列判断,显然Gk=3下面所对的就是mathe所选猜的排列。
3 、从表中可知,第2猜不需要策略,从判断的A1中任选1个排列作猜,后续分解都是同构的。
根据表进行统计得P(1)=1/6, P(2)=2/6,P(3)=2/6,P(4)=1/6.
n=3时,运气最不济只需要4次可以猜中。E(3,k)=∑kP(k)=5/2
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-16 02:43 , Processed in 0.060974 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表