身为题目的作者
在此再度感谢每一个写了这题的小组们
看到许多组解答用手写得密密麻麻
有的还画了树状图
真的很认真
起初在设计题目时
直觉认为答案的PMF和geometry random variable有关
如正四面体在到达步数n>1的情形
然而 正六面体的结果会稍微复杂了些
不过 若从详解中的写的 最后答案是由两个exponential差得来的
所以在计算期望值的时候 就会有和geometry异曲同工的技巧了
(话说当初为了赶缴交的deadline所以详解不甚详细 不好意思)
(另外有几个小错 勘误于本版第75篇)
话说回来
详解中 正六面体的PMF用到线性代数来解
当初也是想帮各位和我们复习一下的意思
不过后来有答对的组别都没有人用线性代数就是了XD
详解也提到 可以用递回的方法来做
递回式P[n]=(P[n-2]+P[n-4])/4
它的characteristic polynomial为 x^2-x/4-1/4
解得两个特征根 (1+-sqrt(17))/8
剩下代初始条件P[3]=1/2,P[5]=1/8 解系数 就是routine的计算了
(PMF写成递回表示式 或是其他表示方式的function 都有给对!!)
另外
若要单算正六面体期望值的话 也有速解
我们讨论蚂蚁开始爬后 直接从起点爬了2段边到达离顶点差1段(level3)的这个时刻
此时看到的期望值为X 则
X= 3*(1/2) + (X+4)*(1/4) + (X+2)*(1/4)
共爬了3段直接爬到终点 花2段爬回起点再向上2段回来 爬1段到level2再爬1段回level3
解得X=6
同理正四面体也可以这么算 设Y为第一次没上去后看到的期望值
X=1*(1/3)+(Y+1)*(2/3) Y=1*(1/2)+(Y+1)*(1/2)
解得Y=2 X=7/3
这里用到两个变量因为第一次没爬上去后接下来会碰到重复的状况(上去:1/2;不上去1/2)
和一开始有三条路可以选不同。
算是直接用期望值去递回吧!
最后表扬一下第9组和第20组用了这种速解
(老实说本来要出正六和正八面体的但没想到这种速解所以作罢)
然后某组似乎用PMF递回式跑Matlab跑1000遍@@ 也答对了...