回復 3# omfun 的帖子
4.
設有\(n\)個正立方體,邊長分別為\(1,2,\ldots,n\)公分,現在將他們由下而上堆疊起來,可隨機以任意大小順序堆疊,但是若連續堆疊兩個立方體,在上面的立方體邊長超過位在下面立方體邊長2公分,則此堆疊方式將會傾倒(例如:若由下而上是②①③④則可安全堆疊,但①④②③則否),問能安全堆疊的機率為何?
感謝 Pacers31 指正,下面是錯的...不小心誤會題意了,請往下找解答
解1:
若安全,1 的上方必為 2 或沒有。如果 2 在 1 上一層,那麼必是 3 在 2 上,或沒有東西在 2 上。
因此可類推至由上至下到 1 出現,必為連續正整數的型: \( k_{1},k_1-1,k_1-2,\ldots 1\);
接著不看這 k_1 個,我們又會有相同之結論,即 1 的下方將是連續正整數 \( k_{1}+k_{2},k_{1}+k_{2}-1,\ldots,k_{1}+1 \);
重覆推論得第一個大層 \( k_{1} \)個最小連續整,第一個大層 \( k_{2} \) 個剩於的最小連續整數…
第 j 層 \( k_{j} \) 個剩於最小的連續整數。其中 \( k_{1}+k_{2}+\ldots+k_{j}=n \), \( k_{j} \) 為正整數。(總共分 j 大層)
所以共有 \( \sum_{j=1}^{n}H_{n-j}^{j}=\sum_{j=1}^{n}C_{n-j}^{n-1}=2^{n-1} \) 種不會傾倒的情形。
所求機率為 \( \frac{2^{n-1}}{n!} \).
解2:
考慮以逐次插入的方式,依小到大的方式插入。
第一步,放一個 1。
第二步, 2 可選擇在 1 的上方或下方。
第三步,3 可放在 2 上方的位置,或最下。
而不能放在 1 上方的位置,因為往後愈來愈大,不可能在 3 和 1 中間放入可安全疊起的的方式。
第四步,同上, 4 僅能放在 3 上方的位置,或最下。
...
得安全的放法僅有 \( 2^{n-1} \)
因此所求機率為 \( \frac{2^{n-1}}{n!} \).
[ 本帖最後由 tsusy 於 2013-7-25 05:06 PM 編輯 ]