猜排列问题

KeyTo9_Fans

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

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

然后告诉mathe猜对的数量：“猜对$0$张”，“猜对$1$张”，……，或者“猜对$52$张”。

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

问：mathe全部猜对所需次数的期望值是多少？

wayne

1# KeyTo9_Fans

KeyTo9_Fans和mathe 玩猜猜看游戏啊，KeyTo9_Fans 可以试试这样告诉mathe，
“mathe，你真有才，虽然猜错了50棵牌， 但猜对了第12，第34棵牌，值得鼓励，再接再厉啊”

KeyTo9_Fans

“mathe，你真有才，虽然猜错了50棵牌， 但猜对了第12，第34棵牌，值得鼓励，再接再厉啊”

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

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

像$1$楼那样的回复，mathe好歹也得猜$\Omega(N\log N)$次吧？

wayne

或者这样算：
设p=1/52!,则期望值为：
$\sum_{n=1}^{+infty} n*(1-p)^{n-1}*p =1/p=52!$

KeyTo9_Fans

mathe猜对之前Fans不洗牌。

也即是说，mathe猜的一直是同一个排列。

056254628

1张牌，不用猜
2张牌，猜1次就足够。
3张牌，1/6一次猜对，5/6两次确定序列，所以期望值为11/6
即E(1)=0
E(2)=1
E(3)=11/6

E(n)<< n！

056254628

关键是n这么大，如何确定最佳方案。
这么多方案，确定哪种是最佳，还是很不容易的

hujunhua

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

056254628

9# hujunhua
正确，7楼看错了，两次不能确保知道

hujunhua

把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