第二版殺拉的五題串燒

22568

第五題..
我以前應(yīng)該有碼過死算的方法..不過不記得在哪..就不再說了..反正估計(jì)也沒啥人想看..
就說一個(gè)當(dāng)時(shí)見到的算是巧解的方法吧..
考慮如下游戲模型Y:

1. 有兩個(gè)球,之間系著一根繩子.繩子上有一個(gè)記號(hào),于是記號(hào)將兩個(gè)球分成一左一右.
   
2. 一次操作是指:隨機(jī)選擇一個(gè)球,將它替換成用繩子系著的兩個(gè)球.(所有球的次序保持不變.新增的繩子沒有記號(hào).)

復(fù)制代碼

那么這和原先的模型X可以有什么關(guān)系呢?
X和Y都是一開始有兩個(gè)球,并且每次操作增加一個(gè)球.
Y的記號(hào)永遠(yuǎn)有且僅有一個(gè).假如我們將記號(hào)左右的球數(shù)和X的兩盆中的球數(shù)對(duì)應(yīng),那么都是一開始各一個(gè),并且每次都是有一邊增加一個(gè).
那么,概率呢?很明顯,Y中每次操作兩邊增加球的概率是和原先兩邊球數(shù)的比例相同的,也就是說X和Y中每次操作對(duì)于兩邊球數(shù)的改變的概率分布是相同的.
所以,所求的結(jié)果在X和Y中是一樣的.

接下來,我們來研究下Y..
在若干步操作后,Y中的模型變成什么樣子?一串依次用繩子連結(jié)的有序的球,其中某兩個(gè)球之間的繩子有記號(hào).
確切地說,N步操作后會(huì)有(N+2)個(gè)球,(N+1)段繩子.
假如我們?cè)诘趇步操作的時(shí)候順手把新增的繩子標(biāo)上一個(gè)i(原先那段有記號(hào)的就標(biāo)個(gè)0吧),那么這(N+1)段繩子就會(huì)是{0,1,...,N}的一個(gè)排列.

接下來,很明顯,我們要證明這個(gè)操作過程和這個(gè)排列(的(N+1)!種取值)一一對(duì)應(yīng).
很明顯每一串合法的操作都對(duì)應(yīng)了唯一的排列.
反之,對(duì)任意一個(gè)排列,顯然也有對(duì)應(yīng)的操作:考慮將球串按繩子標(biāo)號(hào)N,N-1,...,2,1的順序再依次"揉"回只剩兩個(gè)球.將這個(gè)過程反過來,就是所求的操作.

到此,這題模型的化歸就算完成了.這么個(gè)排列已經(jīng)足夠簡(jiǎn)單了,不管想求什么,都可以直接開始處理了.
特別地,這題想求的是"在已知'最終兩邊球數(shù)不同'的前提下,少的一邊球數(shù)的期望".
只須排列中0的位置,而無須考慮另外N個(gè)數(shù).很明顯0在每個(gè)位置都是等概率的.
于是結(jié)果為[(N+3)/2]/2.
特別地,對(duì)于此題的N=2014,所求期望為504.

21457

本來還指望第五題頂?shù)镁靡稽c(diǎn)的，結(jié)果半天時(shí)間答案就又出來了
正確答案是504
這回5題全給同一個(gè)人@天馬行空 解決了，，看來下次是不是要換種出題方式了

21457

第五題解：
構(gòu)造另外一個(gè)模型來解決這個(gè)問題

有2016張撲克牌。
洗牌過程是這樣的：在k張牌順序確定了之后，向k+1個(gè)空中隨機(jī)放入第k+1張牌。
一開始也是有兩張牌。之后規(guī)定，剩下加入的牌不能放到這兩張牌中間，并且在這里做上標(biāo)記。
標(biāo)記之上的記為A，牌數(shù)為a，標(biāo)記之下的記為B，牌數(shù)為b。
那么，進(jìn)入A和B的概率正好是a/(a+b)和b/(a+b)。
這個(gè)模型和原題的模型等效。

洗完牌之后，較少的那部分的牌數(shù)目的可能為：1，2，3……1006，1007。由于洗牌的任意性，這些可能出現(xiàn)的結(jié)果的概率是相同的！
則數(shù)學(xué)期望為：(1007+1)/2=504。
則原題的數(shù)學(xué)期望為504。

@天馬行空

32332

我覺得這些題我都在哪里見到過一樣………

53631

你這題   有點(diǎn)像腦筋急轉(zhuǎn)彎

87687

6次？