網頁

2015年2月28日 星期六

高中數學:格子點上只能走↓↑→,共有幾種走法?

題目:

如上圖,從A沿著格子線到B,只能向右(→)、向上(↑)或向下(↓),且路徑不得重複,請問

(1)有幾種走法?
(2)不經過P有幾走法?
(3)經過P有幾走法?
(4)不經過P且不經過Q有幾走法?
(5)經過P且經過Q幾走法?

解:
(1)
無論如何走,從A到B一共有四次向右(→)

如上圖,第一次向右有3種選擇、第二次向右有4種選擇、第三次向右有4種選擇,最後一次向右有5種選種,所以共有3x4x4x5 = 240種走法。

(2) 由於不經過P,將一定會經過P的路徑標註起來(如圖b),再將其刪除(圖c)。
圖(b)

圖(c)


圖(d)

在圖(d)中,第一次向右有3種走法,最後一次向右仍有5種走法。由於P點已刪除,第二次向右與第三次向右被拆成上下兩部份。在上半部,第二次向右與第三次向合併成一種;在下半部,第二次向右有2種走法、第3次向右有3種走法,因此下半部有2x3=6種走法。全部共有3 x (1+2x3) x 5 = 3x7x5 = 105種走法。

(3)經過P有的走法 = 全部減去不經過P的走法 = 240-105 = 135

(4)將經過P, 或經過Q的路徑標示出來(圖e),並將其刪除(圖f)
圖(e)

圖(f)


圖(g)

第一次向右有三種走法,接著可區分成上半部與下半部,上半部有兩種走法;下半部有2x4=8種走法。由於不能向左走,所以上半部不能走到下半部,但下半部可往上走上半部。因此共有3x(2+2x4) = 3x10 = 30種走法。

(5)先計算不經過Q的走法,作法如題(2),先將必經Q的路徑刪除,如下圖(h)

圖(h)

第一次向右有三種走法、第二次向右有四種走法,接著分上半部有2x2=4種走法、下半部有2種走法,因此共有 3x4x(2x2+2) = 3x4x6 = 72 走法。
小結: 不經過Q有72種走法、經過Q有240-72=168種走法。


以上圖來解釋,最大的圈圈代表全部的走法,共有240種、黃圈圈代表經過P的走法、藍圈圈代表經過Q的走法。
黃圈圈與藍圈圈的聯集=全部-(不過P)且(不過Q) = 240-30 = 210
經過P且經過Q幾走法就是黃藍圈圈的交集=(過P)+(過Q)-聯集 = 135+168-210 = 93

-- END --

沒有留言:

張貼留言