一段繩子，任意切n刀，切成n+1段繩子。問這些繩子能組成n+1邊形的概率？

01-11

樓主算出來了n=2時，p=25%，p=3時，p=50%，n=4時，p約等於0.687。但是得不到一個關於n的函數

$P=1-frac{n+1}{2^{n} }$

思路很簡單：最長的一段不能超過繩子總長的一半。

我將給出2個證明，第一個證明是正常的思路，需要一點微積分，第二個證明不用任何高等數學，簡潔易懂，但需要一點點技巧。

~~~~~~~~~~~~~~~~~~~~

證明1（僅用到簡單的微積分）：

設繩子的長為1。

先將問題離散化，將繩子分成k段（ $k ightarrow infty$ ），每段長為Δx（ $Delta x ightarrow 0$ ）。

設 $P_{0}$ 為繩子無法組成n+1邊形的概率。在這種情況下，設最長的一段為x，顯然 $xgeq frac{1}{2}$

下面計算最長的一段恰為x的概率。有兩種情況：

假設最長的一段恰在兩端

假設最長一段在左端，那麼最左邊的一刀（可以是n刀的任意1刀）必須切在某個固定的Δx內，剩下的n-1刀必須切在右邊的 1-x 內。最長一段在右端同理。

故總概率為 $Delta P_{1}= 2nleft( 1-x ight) ^{n-1} Delta x$

假設最長的一段在中間

則最長一段的左右兩刀的距離恰為x

左邊那一刀可以選擇的位置有 $frac{1-x}{Delta x}$ 種，此時右邊一刀位置固定，剩下的 n-2 刀必須在 1-x 內。

左右兩刀在刀數的選擇有 $nleft( n-1 ight)$ 種

故總概率為 $Delta P_{2}= frac{1-x}{Delta x} nleft( n-1 ight) left( Delta x ight) ^{2} left( 1-x ight) ^{n-2}=nleft( n-1 ight) left( 1-x ight) ^{n-1}Delta x$

所以對於最長的一段恰為x的情況，繩子無法組成n+1邊形的概率：

$Delta P_{0}= Delta P_{1}+Delta P_{2}=nleft( n+1 ight) left( 1-x ight) ^{n-1}Delta x$

$P_{0}=sum_{frac{1}{2}leq xleq 1 }^{}{Delta P_{0} }$

然後再化離散為連續

$P_{0}=int_{frac{1}{2} }^{1}n left( n+1 ight) left( 1-x ight) ^{n-1}dx=n left( n+1 ight)int_{0 }^{frac{1}{2}} x^{n-1}dx=frac{n+1}{2^{n} }$

故 $P=1-P_{0}= 1-frac{n+1}{2^{n} }$

證畢！

~~~~~~~~~~~~~~~~~~~~

當天晚上我又想了一下這道題，根據答案的形式，突然又想到了一個絕妙的方法！

只需要高中的數學知識就可以證明。

~~~~~~~~~~~~~~~~~~~~

證明2（僅用高中數學）：

設繩子的長為1。

切n刀將繩子分成了n+1段，從左到右分別是： $x_{0} ,x_{1}, x_{2},...,x_{n}$

滿足： $0< x_{0} ,x_{1}, x_{2},...,x_{n} <1$ , $sum_{i=0}^{n}{x_{i} } =1$

如果這些繩子不能組成n+1邊形，那麼存在 $x_{i} left( 0leq ileq n ight)$ ， $x_{i}geq frac{1}{2}$

易見，只能恰有一段不小於 $frac{1}{2}$

假設 $x_{0}geq frac{1}{2}$ ，易見此情況等價於所有的n刀都切在了右邊 $frac{1}{2}$ ，故所求的概率為 $frac{1}{2^{n} }$

設其中的某一組解為 $left( x_{0,0}, x_{1,0}, x_{2,0},...,x_{n,0} ight)$

假設 $x_{i}geq frac{1}{2} left( 1leq ileq n ight)$ ，設某一組解為 $left( x_{0,i}, x_{1,i}, x_{2,i},...,x_{n,i} ight)$ ,容易發現，對於每一組解，都可以通過輪換的方式，和 $x_{0}geq frac{1}{2}$ 的解建立一一映射的關係：

$left( x_{0,0}, x_{1,0},...,x_{n-i,0},x_{n-i+1,0},...,x_{n,0} ight) Leftrightarrow left( x_{i,i}, x_{i+1,i},...,x_{n,i},x_{0,i},...,x_{i-1,i} ight)$

故，對於任意 $x_{i}geq frac{1}{2} left( 1leq ileq n ight)$ ，所求的概率均為 $frac{1}{2^{n} }$

（答者註：嚴格地說，一一映射並不是集合大小相同的充分條件，反例有著名的整數和偶數一一映射，但在本題下，容易判斷，集合大小相等是成立的。嚴格的證明需要證明雅各比行列式的值為1才行，這並不難但有點麻煩，從略）

綜上，對於以上n+1種情況，這些繩子不能組成n+1邊形的總概率 $P_{0}= frac{n+1}{2^{n} }$

故 $P=1-P_{0}= 1-frac{n+1}{2^{n} }$

證畢！

~~~~~~~~~~~~~~~~~~~~

已經有正確答案了，我給個證明吧.

思路來源於n=2的情形，如下圖

註：背景的虛線是空間坐標系的坐標軸，各字母的定義見下文.

對於高維的情況，原諒我只能不說人話了……

寫在前面，我對問題的理解是全概率空間是在繩子上依次取n個點，也就是概率空間是 $arOmega={(x_1,x_2,...,x_n)|0leq x_1leq x_2leqcdotsleq x_nleq 1}$ ，上面的概率測度就是n維的體積.很容易證明這個概率空間和取n+1個和為1的非負數，也就是下文中的 $Omega$ ，是等價的，因為只差一個線性映射，而體積這種東西在線性映射下是保持的.

首先代數化，記 $Omega ={(a_0,a_1,cdots,a_n)|a_iin[0,1],sum{a_i}=1 }$ .這個是全空間.

要使n+1個數能夠組成n+1邊形，只需要滿足一個條件： $forall kin{0,1,cdots,n},a_k<sum_{k e i}{a_i}$ .

代入條件，也就是只需要滿足： $forall kin{0,1,cdots,n},a_k<frac1 2$ .

因此符合條件的空間是 $Gamma ={(a_0,a_1,cdots,a_n)|a_iin(0,frac1 2),sum{a_i}=1 }$ .

因此，我們要計算的概率不是別的，就是 $frac{Vol(Gamma)}{Vol(Omega)}$ .

為了方便，我們考慮 $Gamma$ 在 $Omega$ 中的補集.

記 $A_k ={(a_0,a_1,cdots,a_n)|a_kgeq frac1 2 }cap Omega$ .

那麼 $Gamma$ 在 $Omega$ 中的補集就幾乎是 $igcup_{k=0}^{n} A_k$ .

顯然， $forall i e j,Vol(A_icap A_k)=0$ .因此. $Vol(Gamma)=Vol(Omega)-sum_{k=0}^{n}{Vol(A_k)}$ .

以下證明， $Vol(A_k)=frac{Vol(Omega)}{2^{n}}$ .

由對稱性，只需計算 $Vol(A_0)$ 即可.

將 $Omega$ 視為 $mathbb R^{n+1}$ 的子集， $mathbb R^{n+1}$ 上的加法自然誘導 $Omega$ 及其子集上的加法.

命題1. $Omega$ 和 $A_k$ 都是 $mathbb R^{n+1}$ 中的緊緻凸集.

證明留作習題.

定義（凸集的頂點）對於 $mathbb R^{n+1}$ 中緊緻凸集 $C$ 中的點 $x$ ，稱 $x$ 為 $C$ 的頂點，如果 $x=frac{y+z}{2},y,zin C$ 蘊含 $x=y=z$ .

命題2.對於 $mathbb R^{n+1}$ 中只有有限頂點的緊緻的凸集，其中的點唯一對應於頂點的凸組合.

直觀很顯然，存在性需要緊性導出，好像要用到歸納法.唯一性根據頂點的定義導出.

命題3. $Omega$ 的頂點是 $(1,0,...,0),(0,1,...,0),...,(0,0,...,1)$ ，共n+1個.

命題4. $A_0$ 的頂點是 $(1,0,0,...,0),(frac1 2,frac1 2,0,...,0),(frac1 2,0,frac1 2,...,0),...,(frac1 2,0,0,...,frac1 2)$ ，也是n+1個.

以上兩個命題都可以直接觀察得出，證明也不複雜，先猜出來，剩下的反證即可.

前方高能！！準備應對衝擊！！以下是關鍵結論！！

命題5. $A_0$ 可以通過關於點 $(1,0,0,...,0)$ ，位似比為2的位似變換變到 $Omega$ .

先證明頂點可以位似變換，再利用命題2得到整個圖形的位似變換.

既然是關鍵結論，這裡仔細說一下吧.我們考慮把頂點 $(1,0,0,...,0)$ 平移到原點，此時其他的頂點也要做相應的變化.

此時， $Omega$ 的頂點變為：

$(0,0,0,...,0),(-1,1,0,...,0),(-1,0,1,...,0),...,(-1,0,0,...,1)$ .

而 $A_0$ 的頂點變為：

$(0,0,0,...,0),(-frac1 2,frac1 2,0,...,0),(-frac1 2,0,frac1 2,...,0),(-frac1 2,0,0,...,frac1 2)$ .

這位似，這酸爽！

命題6. $Vol(A_0)=frac{Vol(Omega)}{2^{n}}$ .

這是命題5的直接結論.

綜上， $frac{Vol(Gamma)}{Vol(Omega)}=frac{Vol(Omega)-sum_{k=0}^{n}{Vol(A_k)} }{Vol(Omega)}=1-frac{n+1}{2^n}$ .

考慮「組不成 n+1 邊形」的概率.

首先把繩子視作一個有缺口的圓環：

因為組不成一個多邊形，一定有一段繩子長度大於繩長的一半.

即切口和缺口的位置必須在虛線一側，如下圖：（B 為某個切口）

劣弧 A-B 間可能有 0,1,2,...,n 個切口（0 個切口即 A,B 重合），這一共是 n+1 種情況.

對於每種情況，所有切口位置均在弧 B-A-C 上的概率為 $frac{1}{2^n}$ .

這樣「組不成 n+1 邊形」的概率就是 $frac{n+1}{2^n}$ .

所以「組成 n+1 邊形」的概率就是 $1-frac{n+1}{2^n}$ .

===

推薦看 @Vichare Wang 的回答 http://www.zhihu.com/question/25408010/answer/30818853 ，他敘述的形式比我好。

我來給一個簡潔一點的證明吧。第一名 @曾加的答案是正確的，但是我看了好幾遍才看懂。。。 @簡言的答案我認為是錯誤的。

首先要把這個題目等價成：

給一個圓環狀的繩子，切n+1刀，每個切口都是均勻分布，問每一段都小於1/2圓周的概率。

因為第一刀不管切在哪裡，都會把繩子切成一條，餘下的部分顯然等價。

然後我們求至少有一段大於1/2圓周的概率。我們用 $A_i$ 表示最長的一段繩子大於1/2圓周，並且右端點恰好是第i刀這個事件。那 $A_i$ 發生的概率是 $frac{1}{2^n}$ 。因為不管第i刀切在哪，餘下的那些刀一定要落在這一刀往右的半個圓周內，並且反過來也成立。

然後我們知道 $A_1$ , $A_2$ ,……, $A_{n+1}$ 之間是互斥的，概率都是 $frac{1}{2^n}$ ，那總的概率就是 $frac{n+1}{2^n}$ 。

再反過來，題目的答案就是 $1-frac{n+1}{2^n}$

1-(n+1)/(2^n)

idea: for n equals to 3, the constraints x,y,z,w are between zero and one and the sum is one give a tetrahedron in R3, while for making a triangle none of them should be bigger than one half. something like that:

same for arbitrary n.

idea2:in another answer (1 - (1 / 2) ^ n ), multiplication by (n+1) is forgot....

題主能不能先界定清楚，什麼叫「任意地切 n 刀」？

你是把繩子平放在桌子上，在整根繩子上任意地找 n 個下刀點？

還是先任意地切一刀，然後隨機取出其中一段，再「任意地切 (n - 1) 刀」？

將之抽象，就有兩種不同的切割策略：

方法一，隨機地產生 n 個 (0, 1) 間的隨機數（服從均勻分布）作為下刀點，然後下刀，得到若干段繩子。
方法二，從一整根繩子開始，每次隨機地（均勻分布）取出現有繩子的一根，隨機地（均勻分布）將之分成兩段，然後放回。重複 n 次。

要知道兩種切法，得到的繩子段的長度分布是不同的。

上圖是模擬切割然後統計繩子段長度（1/1000 統計精度）得到的分布圖。繩子分割為 15 段，圖中藍色線為第一種切割，紅色是第二種。可以看到，兩種切割法得出的繩長分布都不是均勻的，紅色應當是指數分布，而藍色則複雜得多。源碼參考 JS Bin。

對於n,在n維下作體積為1的正n+1邊形(面體)T,T的每一個側n維標示了0-1的刻度(即正三角形的側邊,正四面體的側面,正五面四維體的側體)僅有約束條件每個刻度小於1/2,如圖

紅色區域面積即為所求概率，除去紅色部分公有n+1個邊長為原邊長1/2的相似體(維度為n)，所以答案為

$P=1-(n+1)/2^n$

1-(3/4)^(n-1)

n=2時p=1/4

剪兩刀之後是剪三刀，顯然在能組成三角形的概率範圍內隨便怎麼剪都沒問題

剩下的就是在不能形成三角形的範圍內有k3的概率剪了之後能組成四邊形

n=3時p(3)=1/4+(1-1/4)*k3

同理推廣

p(n)=p(n-1)+(1-p(n-1))*kn

現在主要問題是求kn

個人理解：

①對於不能組成n邊形（剪n-1刀）的情況是有一段長度大於等於1/2總長度，然後這裡需要求出剪了之後沒有大於1/2總長度的概率

②已知的是剪一刀只有，有一段長度大於1/2，再剪一刀使得沒有線段的長度大於1/2總長度的概率為1/4（即n=2的情況）

個人認為①與②所描述的概率是一樣的，故而kn=1/4

所以，p(n)=1/4+3/4*p(n-1)

得到p(n)=1-(3/4)^(n-1)

寫完發現和別人的答案不一樣，求指出我的問題在哪裡？~~

$1-left( frac{1}{2} ight) ^{n-1}$

上面都錯,有空再解釋。

1 - (1 / 2) ^ n

簡單說下思路，可以假定存在切的最長的一段，因為最長的是兩段完全一樣的概率為0。

則最長可以在第一段，第二段，。。。等等，在每個地方的都可以通過剪切的方式把最長斷移動到最後一段。

最長段為末尾一段，那麼不能組合成n+1邊形的可能性是每一切都在前面n / 2，可以組合成n + 1邊形就是剩下的。

============================

正確答案已經出來了，所以我厚顏無恥的跑來把我的答案往正確上的湊。

對於最長的在某個確定段的不能組合成多邊形的概率是上面說到的，但是可以在n+1個地方出現，於是要乘以n+1。

正如評論裡面那位同學說的那樣。

我認為以上答案都是錯誤，我能夠說清楚你們錯在哪，並且我也有正確答案