2019 STEP II Q11 —— 挑棍子游戏拼出三角形的概率问题

Created on May 04, 2020

2020   ·   probability   step   ·   mathematics   step

本篇的问题来自于 2019 STEP II 数学考试中的第11题。

STEP (Sixth Term Examination Paper) 是英国剑桥考试中心为本科申请者提供的数学专项考试，通常会是剑桥、帝国理工、伦敦大学、华威等名校的数学、计算机、工程等专业的录取要求之一。每年都会有一些非常精彩的考题，我在此挑选一些个人喜欢的考题作分享。

问题

现有 $2M+1$ 根小棍，长度分别为 $1,2,3,\cdots, 2M+1$，其中 $M$ 为一个正整数。求从这些小棍中随机挑选3根能拼打成一个三角形的概率。

解答

我们先来考虑这样一个问题。如果一个三角形的三条边满足 $a<b<c$，其中 $a,b,c$ 均为整数长度。如果最长边 $c$ 给定，那 $a,b$ 的取值有多少种不同的组合？

对 $c$ 分奇数和偶数的情况分类讨论

如果 $c=2n+1$，那么 $b$ 可以取的值为 $2n, 2n-1, \cdots n+3, n+2$

若 $b=2n$，则 $a=2,3,\cdots,2n-1$，共 $2n-2$ 个值可取。

若 $b=2n-1$，则 $a=3,4,\cdots,2n-2$，共 $2n-4$ 个值可取。

$\cdots$

若 $b=n+3$，则 $a=n-1,n, n+1,n+2$，共 4 个值可取。

若 $b=n+2$，则 $a=n,n+1$，共 2 个值可取。

所以所有可能的组合的总数为：

\[(2n-2)+(2n-4)+\cdots+4+2 = n(n-1)\]

如果 $c=2n$，那么 $b$ 可以取的值为 $2n-1, 2n-2, \cdots n+2, n+1$

若 $b=2n-1$，则 $a=2,3,\cdots,2n-2$，共 $2n-3$ 个值可取。

若 $b=2n-2$，则 $a=4,5,\cdots,2n-3$，共 $2n-5$ 个值可取。

$\cdots$

若 $b=n+2$，则 $a=n-1,n, n+1$，共 3 个值可取。

若 $b=n+1$，则 $a=n+1$，共 1 个值可取。

所以所有可能的组合的总数为：

\[(2n-3)+(2n-5)+\cdots+3+1 = (n-1)^2\]

我们接下来计算从 $2M+1$ 根长度不等的小棍中任选3根可以拼搭出的三角形的数量。

其中最长边为奇数（最长的最长边对应 $c=2M+1$）的三角形数量为：

\[\sum_{n=1}^M n(n-1)\]

其中最长边为偶数（最长的最长边对应 $c=2M$）的三角形数量为：

\[\sum_{n=1}^M (n-1)^2\]

因此可能的三角形的总数为

\[\begin{aligned} & \, \sum_{n=1}^M \left[ n(n-1) + (n-1)^2\right] \\ = & \, \sum_{n=1}^M (2n^2-3n+1) \\ = & \, \frac{2M(M+1)(2M+1)}{6}-\frac{3M(M+1)}{2}+M \\ = & \, \frac{M}{6}\left[ 2(M+1)(2M+1) - 9(M+1) + 6\right] \\ = & \, \frac{M}{6}\left[ 4M^2 - 3M -1 \right] \\ = & \, \frac{M(M-1)(4M-1)}{6} \end{aligned}\]

而从 $2M+1$ 根棍子中随机取3根的所有可能取法共有：

\[{2M+1 \choose 3} = \frac{(2M+1)(2M)(2M-1)}{6}\]

上面得到的两个结果相除，就得到随机选出的小棍可以形成三角形的概率：

\[P(\triangle) = \frac{(M-1)(4M-1)}{2(2M+1)(2M-1)}\]

比较有意思的是，当 $M\to\infty$ 时，$P(\triangle) \to \frac{1}{2} $。也就是说，只要棍子足够多，随便抓3根，能不能形成三角形的概率大概就是一半一半。

数值验证

选这个问题来玩耍，一部分原因是这个概率问题很容易写一个小程序来做模拟。

自己随手写了个 Python 练手，供参考。

import random

MAX_ROD_LENGTH = 99
TRIALS = 1000

rods = []
for rod_length in range(MAX_ROD_LENGTH):
    rods.append(rod_length+1)

can_form_trig = 0

for trial in range(TRIALS):
    picked = random.sample(rods, 3)
    if sum(picked) > 2*max(picked):
        can_form_trig += 1

def predicted_prob(MAX_ROD_LENGTH):
    M = (MAX_ROD_LENGTH - 1) / 2
    return (M-1) * (4*M-1) / 2 / (2*M+1) / (2*M-1)

print("Probability found from running multiple tests: {0:.3f}".format(can_form_trig/TRIALS))
print("Probablilty from theoretical prediction: {0:.3f}".format(predicted_prob(MAX_ROD_LENGTH)))