第二版杀拉的五题串烧

22568

第五题..
我以前应该有码过死算的方法..不过不记得在哪..就不再说了..反正估计也没啥人想看..
就说一个当时见到的算是巧解的方法吧..
考虑如下游戏模型Y:

1. 有两个球,之间系着一根绳子.绳子上有一个记号,于是记号将两个球分成一左一右.
   
2. 一次操作是指:随机选择一个球,将它替换成用绳子系着的两个球.(所有球的次序保持不变.新增的绳子没有记号.)

复制代码

那么这和原先的模型X可以有什么关系呢?
X和Y都是一开始有两个球,并且每次操作增加一个球.
Y的记号永远有且仅有一个.假如我们将记号左右的球数和X的两盆中的球数对应,那么都是一开始各一个,并且每次都是有一边增加一个.
那么,概率呢?很明显,Y中每次操作两边增加球的概率是和原先两边球数的比例相同的,也就是说X和Y中每次操作对于两边球数的改变的概率分布是相同的.
所以,所求的结果在X和Y中是一样的.

接下来,我们来研究下Y..
在若干步操作后,Y中的模型变成什么样子?一串依次用绳子连结的有序的球,其中某两个球之间的绳子有记号.
确切地说,N步操作后会有(N+2)个球,(N+1)段绳子.
假如我们在第i步操作的时候顺手把新增的绳子标上一个i(原先那段有记号的就标个0吧),那么这(N+1)段绳子就会是{0,1,...,N}的一个排列.

接下来,很明显,我们要证明这个操作过程和这个排列(的(N+1)!种取值)一一对应.
很明显每一串合法的操作都对应了唯一的排列.
反之,对任意一个排列,显然也有对应的操作:考虑将球串按绳子标号N,N-1,...,2,1的顺序再依次"揉"回只剩两个球.将这个过程反过来,就是所求的操作.

到此,这题模型的化归就算完成了.这么个排列已经足够简单了,不管想求什么,都可以直接开始处理了.
特别地,这题想求的是"在已知'最终两边球数不同'的前提下,少的一边球数的期望".
只须排列中0的位置,而无须考虑另外N个数.很明显0在每个位置都是等概率的.
于是结果为[(N+3)/2]/2.
特别地,对于此题的N=2014,所求期望为504.

21457

本来还指望第五题顶得久一点的，结果半天时间答案就又出来了
正确答案是504
这回5题全给同一个人@天马行空 解决了，，看来下次是不是要换种出题方式了

21457

第五题解：
构造另外一个模型来解决这个问题

有2016张扑克牌。
洗牌过程是这样的：在k张牌顺序确定了之后，向k+1个空中随机放入第k+1张牌。
一开始也是有两张牌。之后规定，剩下加入的牌不能放到这两张牌中间，并且在这里做上标记。
标记之上的记为A，牌数为a，标记之下的记为B，牌数为b。
那么，进入A和B的概率正好是a/(a+b)和b/(a+b)。
这个模型和原题的模型等效。

洗完牌之后，较少的那部分的牌数目的可能为：1，2，3……1006，1007。由于洗牌的任意性，这些可能出现的结果的概率是相同的！
则数学期望为：(1007+1)/2=504。
则原题的数学期望为504。

@天马行空

32332

我觉得这些题我都在哪里见到过一样………

53631

你这题   有点像脑筋急转弯

87687

6次？