之前我們講了哥尼斯堡七橋問題
這個問題最後被偉大的大數學家歐拉解決了。
他證明出這七座橋永遠不可能一次性不帶重複的走完。
後來我們又計算出:
如果只走其中的6座橋(不帶重複一次性走完),一共有256種走法。
今天我們計算一下:
如果允許重複走其中的一座橋,要把七座橋全部走完有多少種走法?
下面帶大家一起解決它。
(下文所說的走法指的是不帶重複一次性走完圖中所有線路的走法)
首先,我們要明白這幾個事實。
一、允許重複走其中的一座橋相當於在這座橋的邊上再建一座橋,起點和終點不變,為什麼要這樣理解?為了看起來直觀、方便記數。
二、理論上來說,七座橋都可以重複走一次,因此有7種建橋的方法。但是實際上可以濃縮成3大種,因為有些情況是重複的,具體如下:
①(中間線,一種情況,無重複)
②(右上和右下,二種重複情況,記數×2)
③(左邊四座橋,四種重複情況,記數×4)
因此,一會兒我們把①②③的記數分別求出來,
然後①+②×2+③×4,就可以得到最終結果了。
但是在這之前,我們還是要從簡單的圖形入手。
【1】下圖中,從A到B有4種走法。
(2×2=4)
【2】下圖中,從A到B有6種走法。
(3×2=6)
【3】下圖中,從O到O有8種走法。
(2×4=8)
下面,我們要進階一步。
【4】下圖中,從A到B有16種走法。
(1×4+2×6=16)(4是【1】的4,6是【2】的6)
【5】下圖中,從O到O有16種走法。
(2×8=16)(8是【3】的8)
【6】下圖中,從O到O有48種走法。
(6×8=48)(8是【3】的8)
【7】下圖中,從A到B有24種走法。
(3×8=24)(8是【3】的8)
下面,我們再進階一步。
【8】下圖中,從A到B有64種走法。
(24×2+16=64)(24是【7】的24,16是【5】的16)
【9】下圖中,從A到B有72種走法。
(2×2×6+3×16=72)(6是【2】的6,16是【5】的16)
【10】下圖中,從A到B有64種走法。
(2×2×4+2×24=64)(4是【1】的4,24是【7】的24)
【11】下圖中,從A到B有64種走法。
(4×16=64)(16是【4】的16)
好了,進入今天的主題。
先求①:
走法一:這其實是【8】,只不過樣式變了,但是不影響本質,所以走法是64
走法二:這其實是【9】,只不過樣式變了,但是不影響本質,所以走法是72
但是要×2,因為走法二有2種。(左邊2個橋)
72×2=144
綜上:64+144=208
但是要×2,因為可以從A到B,也可以從B到A。
208×2=416
再求②:
走法一:這其實是【10】,只不過樣式變了,但是不影響本質,所以走法是64
走法二:這其實是【11】,只不過樣式變了,但是不影響本質,所以走法是64
但是要×2,因為走法二有2種。(左邊2個橋)
64×2=128
綜上:64+128=192
但是要×2,因為可以從A到B,也可以從B到A。
192×2=384
再求③:
走法一:這其實是【7】×2,只不過樣式變了,但是不影響本質,所以走法是24×2=48
走法二:這其實是【9】,只不過樣式變了,但是不影響本質,所以走法是72
但是要×2,因為走法二有2種。(左邊2個橋)
72×2=144
綜上:48+144=192
但是要×2,因為可以從A到B,也可以從B到A。
192×2=384
結論:
根據①+②×2+③×4
416+384×2+384×4=2720
如果允許重複走其中的一座橋,要把哥尼斯堡七座橋全部走完共有2720種走法!