之前我們講了哥尼斯堡七橋問題

這個問題最后被偉大的大數學家歐拉解決了。

他證明出這七座橋永遠不可能一次性不帶重復的走完。

后來我們又計算出：

如果只走其中的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種走法！