一個格點最短路徑問題的思考

金曉陽

【摘要】將平面格點最短路徑問題，放在平面直角坐標系中研究比較便捷.本文用三種不同的方法解決了一種平面格點最短路徑問題，進而將問題推廣到空間情形.通過對問題的探究，最終成功推廣了組合數性質.

【關鍵詞】

格點；最短路徑；概率；組合數性質

圖一格點最短路徑問題是十分有趣的數學問題.它與高中數學中的排列組合、概率等概念有很大關聯，讓我們先來做一道這樣的問題：

例1 如圖一所示，在平面直角坐標系中有一動點P，t0時刻位于原點處，之后每一秒內，點P沿x軸正方向或y軸正方向運動一個單位，兩種運動方式的概率相等.請問6秒后，點P運動了6個單位的路程，到達（3，3）的概率為多少？

分析：由于整個運動過程可能的路徑即基本事件數是有限的，且向右運動1個單位與向上運動1個單位為等可能事件，即每個基本事件出現的可能性相等，故該模型符合古典概型.

圖二解法一 點P到達某個格點之前，必然經過與該格點相鄰的左方一個格點或下方一個格點，即到達某格點的最短路徑數等于到達左方與之相鄰格點的最短路徑數和到達下方與之相鄰格點的最短路徑數之和.若到達x軸上的某個格點，之前必然由原點O開始不斷沿著x軸正方向運動，這是唯一的選擇，故到達x軸上每個格點的最短路徑數都是1，同理可得，到達y軸上每個格點的最短路徑數也都是1.由此可計算出到達任意格點的最短路徑數.

6秒后，點P一共移動了6個單位，可能到達（6，0）、（5，1）、（4，2）、（3，3）、（2，4）、（1，5）、（0，6），可由以上方法求出6秒后運動到這些格點的最短路徑條數（如圖二所示），這些路徑中任意兩條出現的概率相等.

由此，我們成功地推廣了組合數性質.