娱乐 数学挑战：走楼梯与概率

[qwer56]

大家每天都在上楼梯吧～

先来一个基础问题：魔法少女蓝毛要上楼梯到二楼，要上10个台阶，她最多可以一步上3个台阶，最少也要上1个台阶，魔法少女不会往后下台阶，请问有多少种上二楼的方法呢？

A作为一名邪恶干部，给第5层楼梯设下了机关，蓝毛每次上几层台阶都是随机的（就是任性！），那么请问蓝毛不踩上第5层阶梯的概率是多少？（踩上第5层，魔法少女就要落入不可名状的陷阱之中）

如果身边没有电脑，你能笔算出来吗？没有过程可没有步骤分了。

接下来是脑补的小故事：蓝毛被抓后，魔法少女总部设法营救，魔法少女粉毛带着全自动分析仪器来到楼梯前，分析仪器分析了阶梯的层数，自动计算了上二楼的方法有多少种，随机挑了一种方法给粉毛，粉毛很听话，按照仪器指示上阶梯。请问粉毛中陷阱的概率和蓝毛一样吗？如果不一样，那谁中陷阱概率高？（还是加上严谨一些：粉毛最多可以一步上3个台阶，最少也要上1个台阶，魔法少女不会往后下台阶，分析机器知道并以此计算。）

[t5rt]

我已经知道红毛和蓝毛是谁了

1:0C10+1C8+2C6+3C4

2:蓝毛上楼不可能随机（平均分布），比如位于第9个时只能上一个台阶

3：红毛(0C5+1C3)种方法上5阶，5阶后同样种方法再上5阶，则概率为(0C5+1C3)^2/(0C10+1C8+2C6+3C4)

二月 22, 2022，由t5rt修改

[猫锅]

让我深刻的体会到我果然是个笨蛋！完全看不懂呢（估计只有初中数学水平了）

[t5rt]

34 分钟前, 猫猫番茄锅 说道:

让我深刻的体会到我果然是个笨蛋！完全看不懂呢（估计只有初中数学水平了）

您过奖了……排列组合和古典概型是初中内容。。。

[fangaa]

f_0=1
f_1=1
f_2=2
f_{k+3}=f_{k+2}+f_{k+1}+f_k
f_{10}=148

p_0=1
p_1=1/3
p_2=4/9
p_{k+3}=1/3*(p_{k+2}+p_{k+1}+p_k)
p_5=121/243

 

[GMRK]

5 小时前, t5rt 说道:

我已经知道红毛和蓝毛是谁了

1:0C10+1C8+2C6+3C4

2:蓝毛上楼不可能随机（平均分布），比如位于第9个时只能上一个台阶

3：红毛(0C5+1C3)种方法上5阶，5阶后同样种方法再上5阶，则概率为(0C5+1C3)^2/(0C10+1C8+2C6+3C4)

第三问显然是相等的，因为粉毛和蓝毛的上法一样

说起来5阶不就gg了吗XD，怎么还有5阶w

[黔驴技穷]

穷举法算出了235种

[fangaa]

36 分钟前, GMRK 说道:

第三问显然是相等的，因为粉毛和蓝毛的上法一样

说起来5阶不就gg了吗XD，怎么还有5阶w

其实不相等。

比如一共3级的情况，蓝毛踩到第1级的概率是1/3，而红毛是1/2。

二月 23, 2022，由fangaa修改

[GMRK]

2 小时前, fangaa 说道:

其实不相等。

比如一共3级的情况，蓝毛踩到第1级的概率是1/3，而红毛是1/2。

当然是相等的啊，，，

三级台阶假如第二级是危险台阶

对于粉毛来说她有四种上法：111、12、21、3 其中111和21是会中的概率是1/2

对于蓝毛来说第一步她有1/3概率直接踩2，或者在1/3踩1的概率后1/2的概率再踩1，1/3+1/6还是1/2

--------------------------------------------

修正一下，刚刚想得太特殊了

以台阶数中间为危险台阶的话大于三阶应该都是粉毛概率大

二月 23, 2022，由GMRK修改

[fangaa]

27 分钟前, GMRK 说道:

当然是相等的啊，，，

三级台阶假如第二级是危险台阶

对于粉毛来说她有四种上法：111、12、21、3 其中111和21是会中的概率是1/2

对于蓝毛来说第一步她有1/3概率直接踩2，或者在1/3踩1的概率后1/2的概率再踩1，1/3+1/6还是1/2

3-2的情况是个特例

[qwer56]

2 小时前, 黔驴技穷 说道:

穷举法算出了235种

穷举法太有毅力了…

[qwer56]

8 小时前, t5rt 说道:

我已经知道红毛和蓝毛是谁了

1:0C10+1C8+2C6+3C4

2:蓝毛上楼不可能随机（平均分布），比如位于第9个时只能上一个台阶

3：红毛(0C5+1C3)种方法上5阶，5阶后同样种方法再上5阶，则概率为(0C5+1C3)^2/(0C10+1C8+2C6+3C4)

所以你的第一个答案是1+8+15+4=28吗？

[aoisaki_ichika]

先做一下第一题后面有时间再写

设要上n个台阶有F(n)种方法，容易得到F(0) = 1，F(1) = 1，F(2) = 2 

这F(n) 种方法可以分成三类，每种方法有两个步骤：

方法1：先走n-1步，再走1步，共F(n-1)种方法

方法2：先走n-2步，再走2步，共F(n-2)种方法

方法3：先走n-3步，再走3步，共F(n-3)种方法

得到3阶常系数线性齐次递推方程：

F(n)- F(n-1) - F(n-2) - F(n-3) = 0

照理说可以通过构造特征方程 x^3 - x^2 - x - 1 = 0用特征根求通解，但是一元三次方程解起来太麻烦了……

这里用求F(10)就直接通过递推方程写出这个数列:

从F(1)开始有：

1，2，4，7，13，24，44，81，149，274，……

共274种

 

 

二月 23, 2022，由aoisaki_ichika修改

[qwer56]

3 分钟前, aoisaki_ichika 说道:

先做一下第一题后面有时间再写

设要上n个台阶有F(n)种方法，容易得到F(0) = 1，F(1) = 1，F(2) = 2 

这F(n) 种方法可以分成三类，每种方法有两个步骤：

方法1：先走n-1步，再走1步，共F(n-1)种方法

方法2：先走n-2步，再走2步，共F(n-2)种方法

方法3：先走n-3步，再走3步，共F(n-3)种方法

得到3阶常系数线性齐次递推方程：

F(n)- F(n-1) - F(n-2) - F(n-3) = 0

照理说可以通过构造特征方程 x^3 - x^2 - x - 1 = 0用特征根求通解，但是一元三次方程解起来太麻烦了……

这里用求F(0)就直接通过递推方程写出这个数列:

从F(1)开始有：

1，2，4，7，13，24，44，81，149，274，……

共274种

 

 

第一问正确呢，274。终于看到想要的答案了。

话说还有列方程，是大佬，我理解不了。也没学过。

2 小时前, 黔驴技穷 说道:

穷举法算出了235种

可惜了～穷举法最后还是落败，少数了几种呢，在计算量不大的情况下，穷举不失一种好方法。

4 小时前, fangaa 说道:

f_0=1
f_1=1
f_2=2
f_{k+3}=f_{k+2}+f_{k+1}+f_k
f_{10}=148

p_0=1
p_1=1/3
p_2=4/9
p_{k+3}=1/3*(p_{k+2}+p_{k+1}+p_k)
p_5=121/243

 

你的第一问答案是148吧，思路正确，可惜最后答案错误了，是不是计算有误呢？

[aoisaki_ichika]

1 小时前, qwer56 说道:

第一问正确呢，274。终于看到想要的答案了。

第二问也是一样的方法，设第n层的概率为p(n)，有p(0) = 1，p(1) = 1/3，p(2) = 4/9

然后就有p(n) - p(n-1)/3 - p(n-2)/3 - p(n-3)/3 = 0

从p(1)开始就有

1/3，4/9，16/27，37/81，121/243，……

答案是121/243

1 小时前, qwer56 说道:

话说还有列方程，是大佬，我理解不了。也没学过。

嘛……离散数学里的一点知识吧，

斐波那契数列这样的数列的通项公式就是这么来的

像这种 a_0*F(n)+a_1*F(n-1)+……+a_k*F(n-k) = 0 的递推方程

可以构造特征方程 a_0*x^k + a_1*x^(k-1) + …… + a_k = 0

求出这个方程的根（这个根叫做递推方程的特征根，可以是复数根）

q_1 , q_2 , q_3 , …… ，q_k (如果没有重根的话）

则这个递推方程的通解就是 f(n) = C_1*q_1^n + …… + C_2*q_2^n+ …… +C_k*q_k^n

这个证明可以自己尝试一下，不是很难

然后代入k个初始条件就可以求得系数C_1,C_2,……C_k的值从而求出特解

如果出现重根的话对特征根的处理比较特殊，这里就不展开说了

-------------------------------------------------------------------------

第三问没理解错的话应该是选择每一上楼的方案的概率都是相等的，而不是每一步走的每一种台阶数的概率是相等的

这样的话就有

安全上二楼的概率  =  （所有方案的个数-需要经过第五层台阶的方案的个数）/所有方案的个数

如果第5层层没有设机关

则粉毛走到第5层台阶后还要再走5层才能到第10层

所以需要经过第五层台阶的方案的个数 = F(5)*F(5)

安全上二楼的概率 = (F(10) - F(5)*F(5))/F(10) = (274-13*13)/274 = 105/274<121/243

比蓝毛要危险一点呢

 

二月 23, 2022，由aoisaki_ichika修改

[fangaa]

21 分钟前, qwer56 说道:

第一问正确呢，274。终于看到想要的答案了。

话说还有列方程，是大佬，我理解不了。也没学过。

可惜了～穷举法最后还是落败，少数了几种呢，在计算量不大的情况下，穷举不失一种好方法。

你的第一问答案是148吧，思路正确，可惜最后答案错误了，是不是计算有误呢？

诶呦我去算错了。

丢人了。

[aoisaki_ichika]

2 小时前, GMRK 说道:

当然是相等的啊，，，

不相等，粉毛选择每一上楼的方案的概率都是相等的，而蓝毛是每一步走的每一种台阶数的概率是等价的

这两种模型计算结果不一样是因为每一种方案的步数可能是不一样的，导致蓝毛选择每一种上楼方案的可能性不同

按照蓝毛的情况，

爬到第5个台阶，

她可能选择“先走3步，再走2步”这个方案

概率是1/3*1/3 = 1/9

也可能选择“先走3步，再走1步，最后走1步”这个方案

概率是1/3*1/3*1/3 = 1/27

而对于粉毛来说选择这两种方案的概率是一样的

 

 

二月 23, 2022，由aoisaki_ichika修改

[aoisaki_ichika]

9 小时前, t5rt 说道:

2:蓝毛上楼不可能随机（平均分布），比如位于第9个时只能上一个台阶

 

你说的没错，不过这是走到8，9两层台阶后再选择一步走几层的情况

走到8层之前每一步走的每一种层数的可能性都是一样的

[qwer56]

9 小时前, aoisaki_ichika 说道:

安全上二楼的概率 = (F(10) - F(5)*F(5))/F(10) = (274-13*13)/274 = 105/274<121/243

比蓝毛要危险一点呢

正解，我完全没有想到走到第n层楼梯的概率它也是一个数列。即37/81=（1/3+4/9+16/27）/3

9 小时前, aoisaki_ichika 说道:

第二问也是一样的方法，设第n层的概率为p(n)，有p(0) = 1，p(1) = 1/3，p(2) = 4/9

然后就有p(n) - p(n-1)/3 - p(n-2)/3 - p(n-3)/3 = 0

从p(1)开始就有

1/3，4/9，16/27，37/81，121/243，……

答案是121/243

我的暴力计算：

蓝毛踩上5级概率：

5层楼梯1+1+1+1+1：1/243

2+1+1+1、1+2+1+1、…：4/81

3+1+1、1+3+1、1+1+3：3/27

2+3、3+2：2/9

1/243+4/81+3/27+2/9=121/243

9 小时前, aoisaki_ichika 说道:

你说的没错，不过这是走到8，9两层台阶后再选择一步走几层的情况

走到8层之前每一步走的每一种层数的可能性都是一样的

关于踩上第九级台阶的概率？根据蓝毛的行动模式有两种答案：

第一：蓝毛假如踩上第八级台阶时，没有注意脚下有还剩多少级台阶，也就是说她可以去踩那虚空的第11级台阶（踩到离第10级台阶还稍微远一点的地方），那么她就还是1/3概率踩9级台阶，1/3概率上刚刚好上10级台阶，和1/3概率大跨一脚，踩到10级台阶同一平面稍远一点的距离。p(9)=p(6)/3+p(7)/3+p(8)/3。

第二：蓝毛注意到了只剩两级台阶了：于是踩上9级台阶概率是1/2，10级台阶是1/2。p(9)=p(6)/3+p(7)/3+p(8)/2

[aoisaki_ichika]

2 小时前, qwer56 说道:

我完全没有想到走到第n层楼梯的概率它也是一个数列

这里讲一下我的思路吧

虽然你问的是”第10层“，”第5层“这样的特定的层数，

但是乍一看这几个层数本身好像没什么特别之处，也就是说解决这个问题的核心很可能和具体是哪一层关系不大

特性不好用就用共性嘛

于是就想到”第n层“，”第n-1层“，……这样更加一般的情况，这样就想到数列了

描述一个数列常用的就两个东西：通项公式和递推公式

直接求通项公式看起来不太容易……

但是这里很容易注意到”第n层“的情况会与前面若干层是有联系的，而且很好数学关系很好找

抽象成数学语言就是第n项与它之前若干项有所联系，数学上用来描述这一性质的就是递推公式

 

前两到题最终都是利用递推方程从初始条件出发计算得到结果的

但是在"得到递推方程“这一步我都利用了递归的思想

简单说就是把要解决的大问题先分解成若干小问题，

如果发现要解决这些小问题或者其中的一部分时所用的方法和解决大问题的方法类似（自相似）

往往利用这个自相似就能得出数学关系。

类似的可以看一下汉诺塔问题

 

才疏学浅，见笑了

二月 23, 2022，由aoisaki_ichika修改

[t5rt]

16 小时前, GMRK 说道:

第三问显然是相等的，因为粉毛和蓝毛的上法一样

说起来5阶不就gg了吗XD，怎么还有5阶w

不一样，在粉毛的计算种可不知道5阶gg，他们概率权重是不一样的

[t5rt]

13 小时前, qwer56 说道:

所以你的第一个答案是1+8+15+4=28吗？

对，我理解的是蓝毛只能上1步或3步。还能走两步的话就只能用迭代了f(n)=f(n-1)+f(n-2)+f(n-3)