數學模型與遊戲 最新協作平台活動 衛道中學程式設計

數學模型與遊戲

數學模型與遊戲

2011

年

2

月

21

過河問題是世界名題，有很多種說法。最早引進中國的 是中國數學會第一屆理事，揚州中學的數學教師陳懷書 先生。後我國數學科普作家、哈軍工大教授薛鴻達先生 曾寫過一篇專文《渡河難題》，對此進行了全面介紹。

我們將介紹三種不同的形式。

例

1

商人們怎樣安全過河

問題 ( 智力遊

戲

)







3

名商

人







3

名隨

從

隨從們密約

_,

在河的任

一岸

_,

一旦隨從的人數

比商人多

_,

就殺人越

貨

.

乘船渡河的方案由商人決定 .

商人們怎樣才能安全過河

?

問題分析

多步決策過

程

決策

~

每一步 ( 此岸到彼岸或彼岸到此岸 ) 船上的

人員

要求

~

在安全的前提下 ( 兩岸的隨從數不比商人

多

),

經有限步使全體人員過河

_.

河

小船

(

至多

2

模型構成

x

_k

~

第

k

次渡河前此岸的商人

數

y

_k

~

第

k

次渡河前此岸的隨從

數

x

_k

, y

_k

=0,1,2,3;

k

=1,2,



s

_k

=(

x

_k

, y

_k

) ~

過程的狀態

S={(

x

, y

)



x

=0,

y

=0,1,2,3;

x

=3,

y

=0,1,2,3;

x

=

y

=1,2}

S ~

允許狀態集

合

u

_k

~

第

k

次渡船上的商人

數

v

_k

~

第

k

次渡船上的隨從

數

d

_k

=(

u

_k

, v

_k

) ~

過程的決策

D ~

允許決策集合

u

_k

, v

_k

=0, 1, 2;

k

=1,2,



s

_k+1

=

s

_k

+(-1)

k

d

_k

~

狀態轉移

律

D={(

u

, v

)



u+v

=1, 2}

x y

3

3 2

2

1

1 0

•窮舉法

_~

編程上

機

•

_圖解法

狀態

s

=(

x,y

) ~ 16

個格

點

_{~ 10}

_{個 點}

允許決策

_~

移動

₁

_或

₂

格

;

k

奇

,

左下移

;

k

偶

,

右上移

.

s

₁

s

_n+1

d

₁

,



d

₁₁

給出安全渡河方案

d₁

d₁₁

允許狀態

模型構

成

模型求

解

求

d

_k



D(

k

=1,2,



n),

使

s

_k



S,

並按轉移

律

s

_k+1

=

s

_k

+

(-1)

k

d

k

由

s

1

=(3,3)

到達

s

n+1

=(0,

0).

商人和隨從人數增加或小船容量加

大

;

商人們怎樣安全過河

智力遊戲

多步決策過程 ( 數學模

型

)

易於推廣

:

規格化方法

考慮

4

名商人各帶一隨從的情

況

.

多步決策模

型

:

恰當地設置狀態和決策

,

確定狀

態轉移律及目標

(

目標函數

).

例

2.

人、狗、雞、米過河問題

這是一個人所共知而又十分簡單的智力遊戲。某人要帶狗 、雞、米過河，但小船除需要人劃外，最多只能載一物過 河，而當人不在場時，狗要咬雞、雞要吃米，問此人應如 何過河。

在本問題中，可採取如下方法：一物在此岸時相應分量

為 1 ，而在彼岸時則取 為 0 _，例如（ 1,0,1,0 ）表示人

和雞在此岸，而狗和米則在對岸。

（ i _{）可取狀態}：根據題意，並非所有狀態都是允許的，例

如（ 0,1,1,0 ）就是一個不可取的狀態。本題中可取狀態

（即系統允許的狀態）可以用窮舉法列出來，它們是： 人在此岸 人在對岸

(1 _， 1 _， 1 _， 1) (0 _， 0 _， 0 _， 0) (1 _， 1 _， 1 _， 0) (0 _， 0 _， 0 _， 1) (1 _， 1 _， 0 _， 1) (0 _， 0 _， 1 _， 0) (1 _， 0 _， 1 _， 1) (0 _， 1 _， 0 _， 0) (1 _， 0 _， 1 _， 0) (0 _， 1 _， 0 _， 1)

總共有十個可取狀態，對一般情況，應找出狀態為可取的 充要條件。

（ ii _{）可取運算}：狀態轉移需經狀態運算來實現。在實際 問題中，擺一次渡即可改變現有狀態。為此也引入一個四 維向量（轉移向量），用它來反映擺渡情況。例如

（ 1 _， 1 _， 0 _， 0 ）表示人帶狗擺渡過河。根據題意，允 許使用的轉移向量只能有（ 1 _， 0 _， 0 _， 0 ，）、（ 1 _， 1

， 0 _， 0 ）、（ 1 _， 0 _， 1 _， 0 ）、（ 1 _， 0 _， 0 _， 1 ）

規定一個狀態向量與轉移向量之間的運算。規定狀態向量與 規定一個狀態向量與轉移向量之間的運算。規定狀態向量與 轉移向量之和為一新的狀態向量，其運算為對應分量相加， 轉移向量之和為一新的狀態向量，其運算為對應分量相加，

且規定

且規定 0+0=00+0=0 _，， 1+0=0+1=11+0=0+1=1 _，， 1+1=01+1=0 _。。 ( _解釋 )

在具體轉移時，只考慮由可取狀態到可取狀態的轉移。問題 化為：由初始狀態（ 1 ， 1 ， 1 ， 1 ）出發，經奇數次上述

運算轉化為（ 0 _， 0 _， 0 _， 0 ）的轉移過程。

我們可以如下進行分析_： （第一次渡河）

(不可取) (不可取)

(可取) (不可取)

（第二次渡河）

      



(1,0,0,0) (1,0,0,1) (1,0,1,0) (1,1,0,0)

(0,1,0,1)

(可取) (不可取)

) 过的状态 (循环 回到原先出现,

(不可取)

(1,1,0,1) (1,1,0,0) (1,1,1,1) (1,0,0,1)

  

      

＝

人在此岸

人在對岸

(1

，

1

，

1

，

1) (0

，

0

，

0

，

0)

(1

，

1

，

1

，

0) (0

，

0

，

0

，

1)

(1

，

1

，

0

，

1) (0

，

0

，

1

，

0)

(1

，

0

，

1

，

1) (0

，

1

，

0

，

0)

(1

，

0

，

1

，

0) (0

，

1

，

0

，

1)

圖解法 問題轉化為求點 (1,1,1,1) 到點 (0,0,0,0) 的一條通路

。

1,1,1,0 0,1,0,1 1,1,0,1

0,0,0,1

0,1,0,0

1,0,1,1

例 3 ：高塔逃生：鐵匠海喬 90 ，公主安娜 50 ，侍女 40 ，鐵鏈 30

原則：

人下來時兩個筐子必須都有人或鐵鏈，並且重量相差 10

公斤。

兩個筐子裝的總重量不超過 170 公斤。

轉化：用向量表示狀態 : _如 (9,5,4,3) 表示四者均在上面， (9,4) 表示海喬和侍女在上面，其餘在下面。從 (9,5,4,3)

開始，到 (3) 結束。

方案之一：

開始 鐵鏈下去 侍女下去鐵鏈上來 鐵鏈拿到筐外 公主

在下面

可把鐵鏈拿到筐裏

(9,5,4,3) →(9,5,4) →(9,5,3) → (9,5)→(9,4)→(5,4,3) →(5,4) →(5,3) →(5)→(4)→(3) 。

注意不同於過河

問題，此過程是

不可逆的。共有

八種不同的方案

，可試著做一下

德國著名的藝術家 Albrecht Dürer(1471-1521)

于 1514 年曾鑄造了一枚名為“ Melencotia I” 的

銅幣。令人奇怪的是在這枚銅幣的畫面上充滿

了數學符號、數位及幾何圖形。這裏，我們僅

研究銅幣右上角的數字問題

德國著名的藝術家 Albrecht Dürer(1471-1521)

于 1514 年曾鑄造了一枚名為“ Melencotia I” 的

銅幣。令人奇怪的是在這枚銅幣的畫面上充滿

了數學符號、數位及幾何圖形。這裏，我們僅

研究銅幣右上角的數字問題

所謂的魔方是指由 1~n2 這 n2 個正

整數按一定規則排列成的一個 n

行 n 列的正方形 。 _n 稱為此魔方 的階 。

Dürer 魔方： 4 階，每一行之和 為 34 ，每一列之和為 34 ，對角

線（或反對角線）之和是 34 ，

每個小方塊中的數字之和是 ₃₄ ，四個角上的數字加起來也是 34

什麼

是

Dürer

魔

方

多麼奇妙的

魔方！

銅幣鑄造時間： ₁₅₁₄

構造魔

方是一個

古老

的數學遊戲，

起初

它

還

和

神靈聯繫

在一

起

，帶有

深厚

的

迷信色彩

。

傳

說三

千二百

多

年

前（

西元

前

2200

年

），因

治水

出名

皇帝

大

禹

就

構造

了三

階魔

方（

被

人們

稱“洛

書

”

），

至今還

有人

把

它當作

符咒

用於

某

些迷信活

動，大約在十

五

世

紀

時，

魔

方

傳

到

了

西

方，

著

名的科

尼利厄斯

·

阿

格

裏帕

（

1486-1535

）先後

構造

出了

3~9

階

的

魔

方 。

構造魔

方是一個

古老

的數學遊戲，

起初

它

還

和

神靈聯繫

在一

起

，帶有

深厚

的

迷信色彩

。

傳

說三

千二百

多

年

前（

西元

前

2200

年

），因

治水

出名

皇帝

大

禹

就

構造

了三

階魔

方（

被

人們

稱“洛

書

”

），

至今還

有人

把

它當作

符咒

用於

某

些迷信活

動，大約在十

五

世

紀

時，

魔

方

傳

到

了

西

方，

著

名的科

尼利厄斯

·

阿

格

裏帕

如何

構造魔

方

奇數（不妨 n=5 ）階的情況

Step1: 在第一行中間寫 1

Step2: 每次向右上方移一格依次填按由小到大排列的

下一個數，向上移出界時填下一列最後一行的小方格

；向右移出界時填第一列上一行的小方格。若下麵想

填的格已填過數或已達到魔方的右上角時，改填剛才

填的格子正下方的小方格，繼續 Step2 直到填完

1

2 3 4

5 6

7 8

9 10

11 12

13 14

15 16 17

18 19

20 21

22 23

24

25

偶數階的情況

偶數階的魔方可以利用奇數階魔

方拼接而成，拉爾夫 · 斯特雷奇

給出了一種拼接的方法 ，這裏

不作詳細介紹

你想構造

_Durer

魔

方

嗎？

五階 沒人知道有多少個！！！

三階 1 個 反射

和中心旋轉生成 8 個

四階 880 個 反射和中心

旋轉生成 7040 個

魔方數量隨階數 n 增長

的速度實在是太驚人了

！

0 6 1 18

9 10 6 0

15 0 9 1

1 9 9 6

0 7 1 18

9 10 7 0

16 0 9 1

1 9 9 7

10 80 100 150

140 110 50 40

70 20 160 90

120 130 30 60

定義：如果 _4×4 數字方，它的每一行、每一列、每一對

角線及每個小方塊上的數位之和都為一確定的數，則稱

這個數字方為 Durer 魔方

。

_R=C=D=S

仍以 4 階方陣為例

其中： R 為行和， C 為列和， D 為對角線和， S 為小方塊和

設 D 為所有滿足 R=C=D=S _{的 Durer 魔方的集合。}

允許取相同的數位

，並且允許數位在 某個數域裏任意取

a₁₁ a₁₂ a₁₃ a₁₄ a₂₁ a₂₂ a₂₃ a₂₄ a₃₁ a₃₂ a₃₃ a₃₄ a₄₁ a₄₂ a₄₃ a₄₄

A=

b₁₁ b₁₂ b₁₃ b₁₄ b₂₁ b₂₂ b₂₃ b₂₄ b₃₁ b₃₂ b₃₃ b₃₄ b₄₁ b₄₂ b₄₃ b₄₄

B=

類似

於

矩陣

的加法和數乘，定

義魔

方的加法和數乘。

易驗證，

D

對加法和數乘

封閉

，

且構成

一

_線性空間

_。

記 M ={

所有的

_4×4

數

字

方

}

，則

其維

數為

₁₆

。

而 D 是

M

的

子空間

，則

D 是

有限維

的

線性空間

。

根據

線性空間

的

性質

，如

果

能

得

到

D 的一組基

，

1 在第一行中共有 4 種取法，為保持上

述性質的成立，第二行中的 1 還有兩種取法。 當第二行的 1 也取定後，第三行與第四行的

1 就完全定位了，故一共可作出 8 個不同的 最簡方陣，稱之為基本魔方並記之為 Q_{1 ，} … ， Q₈

R=C=D=S=1 的方陣構成的線性空間具有什麼樣的性質 ？（這是非常必要的，因為我們一般取的是整數。）

類似于構造 n 維歐氏空

間的標準基，利用 0 和 1

我們來構造一些

R=C=D=S=1 的最簡單的

方陣。

類似于構造 n 維歐氏空

間的標準基，利用 0 和 1

我們來構造一些

R=C=D=S=1 的最簡單的 方陣。

由

0,1

數

位組

合，

構造

所有的

R=C=D=S=1

的

魔

方。共有

8

個，

記

為

Q

_i

, i=1,2,…,8

。

Q

₁

=

1 0 0 0

0 0 1 0

0 0 0 1

0 1 0 0

Q

₂

=

1 0 0 0

0 0 0 1

0 1 0 0

0 0 1 0

Q

₃

=

Q

4

=

0 0 0 1

1 0 0 0

0 0 1 0

0 1 0 0

0 0 0 1

0 1 0 0

1 0 0 0

Q

₅

=

0 0 1 0

1 0 0 0

0 1 0 0

0 0 0 1

Q

₆

=

0 1 0 0

0 0 1 0

1 0 0 0

0 0 0 1

Q

₇

=

0 0 1 0

0 1 0 0

0 0 0 1

1 0 0 0

Q

₈

=

0 1 0 0

0 0 0 1

0 0 1 0

1 0 0 0

可以證明， Dürer 空間（簡稱 D 空間）中任何一

個元素都可以用 Q_{1 ，} Q_{2 ，…，} Q₈ 來線性表示，但

它們能否構成 D 空間的一組基呢？

是否线性无关？

8

2

1

,

Q

,

,

Q

Q



容易看出：

0

7 6 3 2 8 5 4

1



Q



Q



Q



Q



Q



Q



Q



Q

Q_{1 ，…，} Q₈ 這 8 個基本方是線性相關的，即至少存在一個 Q_j

，可以通過其他 7 個基本方的線性組合得到。這 8 個基本方的 地位是等同的，故可不妨設 j=8 。下麵驗證 Q_{1 ，} Q_{2 ，…，} Q₇

是否線性7 相關

₀

。

1





 i i i

Q

r

令： ，即

等號兩邊對應元素相比較，_得 r₁=r₂=…=r₇=0 _， 所以 是Q1

,

Q2

,



,

線性無關Q7

7 2

1

,

Q

,

,

Q

Q



_{是 D 空間的最小生成集。}

令 D

即解方程組：

7 7 2

2 1

1Q d Q d Q

d









             1 14 15 5 12 7 6 9 8 11 10 5 13 2 3 16                         6 5 4 2 3 1 7 7 1 3 5 2 6 4 2 6 1 7 4 5 3 4 3 7 5 6 2 1 d d d d d d d d d d d d d d d d d d d d d d d d d d d d

=

解得 D=8Q_{1 ＋} 8Q_{2 ＋} 7Q_{3 ＋} 6Q_{4 －} 2Q_{5 ＋} 3Q_{6 ＋} 4 Q

D 空間的子空間和 D 空間的擴展

（ 1 ）要求數字方的所有數都相等

這是集合 G={rE,r R}∈ ，

G 是以 β_G={E} 為基的一維向量空間

（ 2 ）要求列、行及每條主、付對角線上各和都相等

。

得到 5 維泛對角方的向量空間 B 。例如：

它的基 B_{B 為：}

   

 

   

 

 

12 7

26 1

21 6

7 12

3 22

11 16

16 11

2 17

P

H=N=R=C=46

其中 H 為主對角線

和， _N 為付對角線

0 1 1 0

1 0 0 1

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0

1 0 0 1

0 1 1 0

0 1 0 1

1 0 1 0

1 0 1 0

0 1 0 1

1 1 0 0

0 0 1 1

1 1 0 0

0 0 1 1



2

P

_P

₃

_



4

P

P

5



1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1



1

（ 3 ）要求行和，列和及兩條對角線上的元素和相等

得到 8 維向量空間 Q 。

基向量 Q_B={Q₁ ， Q₂ ，…， Q₇ ， N₀} ， 其中 Q₁ ， Q₂ ，…， Q₇ 是 D 的基，而

               0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0

N _{例如： R=C=D=30}

（ 4 ）僅要求行和與列和相等

得到 10 維向量空間 ψ

基向量 ψ_B={Q₁ ， Q₂ ，…， Q₇ ， N₁ ， N₂ ， N₃} 其中 Q₁ ， Q₂ ，…， Q₇ 是 D 的基，而

               0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 N                  0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 2 N              0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 3 N

（ 5 ）對數字沒任何要求

所有 4×4 數位方組成 16 維向量空間 M

基向量 M_B 的元素應是標準基（即僅有一個

元素為 1 ，其餘元素均為 0 的陣）。

Botsch （ 1976 年）證明了對

於 1 與 16 之間的每一個數 K

，都存在 K 維的 4×4 方的向

量空間

Botsch （ 1976 年）證明了對

於 1 與 16 之間的每一個數 K ，都存在 K 維的 4×4 方的向

量空間

由上可知，有下式成立 ：

由上可知，有下式成立 ：

（向量空間）

（向量空間）

（維數）

（維數） _{0 1 5 7 8 10 0 1 5 7 8 10} 16

16

由上可知，有下式成立 ：

由上可知，有下式成立 ： （向量空間）

（向量空間）

（維數）

（維數） _{0 1 5 7 8 10 0 1 5 7 8 10} 16

16

練習

完成下面的

Durer

方

6

14

9 48

8 7 11

6 7 9 8 5

9 7



奇偶

數

校驗

及相

關

問題

q p 2



證明：

採用反證法，設 ，其中 p 、 q 互素， 則有

p2=2q2 。因為 2|p2 ，故 2|p 。記 p=2p

1 ，可得 4p12=2q2

，即

2p₁2_=q2 _{，故又有 2|q ，與 p} 、 _{q 互素矛盾。}

例

證明 是

2

無理數。

同樣方法可以證明：若 m 是 大於 1 的素數， n 是大於 1

的整數，則 必為

無理數。

例 1 ：擬用 40 塊方形瓷磚鋪設如下圖所示的地面，但商

店只有長方形瓷磚，其大小為方形的兩塊。問購買 20 塊

長方形瓷磚後，是否可能不裁開而直接鋪好地面？

解

將圖 11.4 _中的 (a) (b) _{黑白相間染色。}

顯然，如長方形瓷磚不裁開，只能用來複蓋相鄰的兩格，

故複蓋的兩格必為一白一黑。

圖 (a) 中共有 21 個黑格和 19 個白格，故不可能直接鋪好 ；

圖 (b) 中黑白格各為 20 個，大家很容易找到直接鋪設的方 法。

圖 (a) _圖 (b)

例 2 ：設一塊 m×n 的棋盤被若干個形如 的板塊恰好蓋滿，試證明 m×n 必能被 8 整除。

證明

:

顯然有 4|m×n ，故 m 、 n 中至少有一個為偶數，不妨

設 n 為偶數，將棋盤按列黑白相間染色，如下圖 (a ) ， 由於 _n 為偶數，黑、白列的數目相同，故黑白格數相

同，設各為 2k 個。

板塊可以有許多種拼湊法，但容易看出，每一板塊放 置 的方向（稱之為定向）只有八種可能的選擇，如下圖 (b) 所示。

圖 (b)

容易看出，不論按什麼方向放置板塊，每一板塊均蓋住

奇數個黑格（ 1 格或 3 格），故蓋住棋盤的板塊必有偶數

個，從而， _m×n 的棋盤必能被 ₈ 整除。

例 3 ：擬將一批尺寸為 1×2×4 的商品裝入尺寸為 6×6×6 的

正方體包裝箱中，問是否存在一種裝法，使裝入的該商品

正好充滿包裝箱。

解

將正方體剖分成 27 個 2×2×2 的小正方體，並

按下圖所示黑白相間地染色。

再將每一 2×2×2 的小正方體剖分成 1×1×1 的小

正方體。

易見， 27 個 2×2×2 的正方體中，有 14 個是黑

的， ₁₃ 個是白的（或 ₁₃ 黑 ₁₄ 白），故經兩 次剖分，共計有 14×8=112 個 1×1×1 的黑色小

正方體和 13×8=104 個 1×1×1 的白色小正方體 。

雖然包裝箱的體積恰好是商品體積的 27 倍，

但容易看到，不論將商品放置在何處，它都將

佔據 4 個黑色和 4 個白色的 1×1×1 小正方體的

在每一次人數不少於 6 人的聚會中必可找出這 樣的 3 人，他們或者彼此均認識或者彼此均不

認識 。

利用圖的方法來描述該問題。將人看成頂

點，兩人彼此都認識用實線連，否則虛線。

證明：



相

識

問題（

拉

姆齊

問題）

問題轉化為在一個 6 階圖中必存在實線三角

形或虛線三角形。

υ₂ υ₁

υ₃

υ₄

υ₆

υ₅ υ₁ υ₂

υ₃

υ₄ 任取一頂點，不妨 _υ1

考察 υ₂υ_{3 、} υ₂υ_{4 和} υ₃υ₄

υ₂υ₃ 、 υ₂υ₄ 和 υ₃υ₄ 只能是虛線，否則得證

但這樣三角形 υ₂υ₃υ₄ 的三邊均為虛線

不妨取 υ₁υ_{2 、} υ₁υ_{3 、} υ₁υ_{4 實線} 與 υ₁ 相連的邊必然有：（鴿籠原

理）

實線條數不小於 3 或虛線條數不小於 ₃

拉姆齊問題也可這樣敘述：

6 階 2 色完全圖中必含有 3 階

其他類似

可

推

出的結

果

：

命題 11.1 任一 6 階 2 色完全圖中至少含有兩個 3 階單色完

全圖。_證明：前面證明必存在 3 階單色完全圖，不妨設 _υ1υ2 υ₃ 為紅色完全圖

υ₁υ_{5 、} υ₂υ_{5 、} υ₃υ₅ 中至少有兩條黑色、故 υ₁υ₅ 與 υ₂υ₅ 中至少有一條是黑色

若 υ₄υ₅υ₆ 也是紅色三角形，命題已得證

故至少一邊與 υ₁υ₂υ₃ 的邊異色，不妨設 υ₄υ_{5 黑色}

υ₁υ_{4 、} υ₂υ_{4 、} υ₃υ₄ 至少應有兩條黑色，不妨設 υ₁υ_{4 、} υ₂υ_{4 黑色}

所以存在第二個 3 階單色完全圖

。

υ₂ υ₁

υ₃

υ₄

υ₆

命題 11.27 階 2 色完全圖至少含有 4 個 3 階單色安全圖。

命題 11.318 階 2 色完全圖中必含有 4 階單色完全圖。

對拉姆齊問題的認識不能僅僅停留在

例 11.1 的水準上。利用邏輯推理方法

，實際上還可獲得一大批結果。命題 11.2 和命題 11.3 的證明留給大家自己

例

2

17 位學者中每人都和其他人通信討論 3 個方向的課題。 任意兩人間只討論其中一個方向的課題，則其中必可找出 3 位學者，他們之間討論的是同一方向的課題。

证明

将每一学者看成一个顶点，作一个 17 _阶完

全图。按讨论课题的方向对边染色，相同方向染 成同一颜色，得到一个 17 _阶 3 _{色完全图。}

任取一顶点 A_{，与它相关联的有} 16 _条边，

其中必能找出 6 _{条相同颜色的边，不妨设} A _与

υ 1， ，… υ 6的连线有相同颜色。连接 A 和 6 个 υ

顶点 1， ，… υ 6。如果这 6 个顶点间也有这种

颜色的边，则已找到讨论同一方向课题的三位学

υ

者；否则， 1， ，… υ 6及连接它们的边构成一

个 6 _阶 2 _{色完全图，由例} 1_{，必可从中找到一个}

3 _{阶单色完全图，即找出三位讨论同一方向课题}

什麼是拼方問題

在 H.E.Dudeney 所寫的《 Cantebury 難 題》 一 書 中 有 一 個正方 形 的圖案 ， 這 個正方 形圖案 是 由 一 個小長方 形和若

干個邊 長各異的 小正方形組 成的。 小

長方形的長為 ，寬為 ，要求 求 出 所 有正方 形 的邊 長和拼 接方法 。 這 種拼 接過 程稱為拼方， 而 這 種類型 的問題稱為拼方問題。

4 1

10 1₄



拼方問題

12

8 5 3

2 7 21/4

11/45/2

31/4

受上一問題的啟示，加拿大數學家 W.T.Tutte, A.Stone

等人考慮了如下問題：

怎樣的長方形可以剖分成若干個邊長各異的小正方

形？

正方形能否剖分成邊長各異的小正方形？

怎樣的長方形可以剖分成若干個邊長各異的小正方 形？

正方形能否剖分成邊長各異的小正方形？

稱具有上述性質的長方形為完美長方形_，正方

形為完美正方形。

波蘭數學家 Z.Moron 的工作

Z.Moron 在 W.T.Tutte 等之前已經作出

了一個 9 階完美長方形，見右圖 ₁₈

14

4 10

15

7

9 8 1

Z.Moron _{的完美長方}

形很接近完美正方形

Z.Moron _{的完美長方}

Tutte _{等人用來分析} Moron _{給出例子的 奇特方法：}

用點表示水準邊，用邊表示小正方形。邊長即小正方形

之邊長，方向規定由上到下。於是一個剖分好的完美長

方形被十分巧妙地轉化成了一個有向圖網路，見下圖

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

除表示上、下兩底邊的頂點以

外，其餘頂點處指入邊邊長之

和應等於指出邊邊長之和

除表示上、下兩底邊的頂點以 外，其餘頂點處指入邊邊長之

和應等於指出邊邊長之和 A

B

C

D

E

F

1

x

₂

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

1

x

7

x

由上面說明：假如我們把 得到的有向圖網路看作電

網路，則所述性質恰好就 是電學中的基爾霍夫定律

。

若將每邊看成一個單位電阻，在給出

正極 A 與負極 F 之間的電勢差後（相 當於給出長方形的高），即可求出每 條邊上的電流強度（等於兩頂點間的 電勢差），而這些數恰好就是小正方

形的邊長。

此外還可看出，解應當是

唯一的，因為在給定

A 、 F 間的電勢差後，各

邊上的電流強度是唯一確 定的。

分析 Moron 給出的完美長方形，取高為 32 ，則相應電網

路中的電流強度 x_i(i=1,…,9) 應滿足：

其解為：

（ x₁,x₂,x₃,x₄,x₅,x₆,x₇,x₈,x₉)=(18,15,4,7,8,1,14,10,9) 恰為相應小正方形的邊長。此外，由 x₁+x₂₌₃₃ 可知，長

方形的寬應為 ₃₃ 。

                                       32 32 32 32 8 4 2 8 3 1 9 5 2 7 1 9 8 7 2 1 9 6 5 8 6 4 3 5 4 2 7 3 1 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 4

x

F 6

x

A B C D E

1

x

₂

x

3

x

5

x

7

x

8

x

可以不管長方形的剖

分，直接根據圖的各

種情況利用電腦來搜

查

前面分析是在對完

美長方形作了剖分 的前提下作出的，

不知道剖分情況怎

麼辦？

幾種最簡單的情況及尋查過程的簡要說明

有向圖只有三條邊的圖見圖 1 。

由 x₁= x₃ 可知不存在 3 階完美長方形。 由四條邊組成的有向圖可以有兩種形式 ，

見圖 2 中的（ a ）、 (b) ，它們均不可

能對

應完美長方形。

1 x

2 x 3 x

圖 1

1 x

2 x 3 x

4 x

圖 2 _（ b _）

2 x 1 x

3 x 4 x

逐階尋查下去可發現，完美長方形對應的電網路必有以下性

質 _{( 性質 1) 除兩端頂點外，其餘各項點的進出邊之和至少為 3 。}

( 性質 2) 電網路不具有對稱性。

根據這兩條性質，可以發現

完美長方形的最小階數為 9

，進而可作出各種 9

階、 10 階、 11 階…完美長

方形。

當然，隨著階數增大，計算

量將按指數增長，因為相應

電網路的數目是按指數增長

的。

幾點說明：

對一個指定的有向圖求相應的完美長方形時，高可以先隨 意選取一個整數。求出所有小正方形的邊長後再將所有資 料同乘一個適當的數，使所有有資料均化為整數。顯然， 變動長方形的高所得到的剖分是相似的，在將相似看作等

同的意義下，這種剖分是唯一的。

Tutte 等人將他們用人工方法得到的完美長方形列成了一

個表，其中包括有二百多個完美長方形。 1960 年，人們

用電子電腦求得了 9 至 15 階的全部完美長方形，可其中

沒有一個是完美正方形！

Tutte 等人將他們用人工方法得到的完美長方形列成了一 個表，其中包括有二百多個完美長方形。 1960 年，人們 用電子電腦求得了 9 至 15 階的全部完美長方形，可其中

是否存在完美正方形？

當求得的完美長方形的長恰好等於寬的十分巧合的情況下， 我們才能得到一個正方形的剖分。由於計算量過大，在電腦 上尋查並未獲得成功，最早作出的正方形的剖分是基於非常 複雜的圖形並用對稱性人工湊出來的，它具有 69 階。後來 又作出了 ₃₉ 階和 ₃₈ 階的完美正方形。接著 _Tutte 等人利用

他們獲得的完美長方形表又拼湊出一個 26 階的完美正方形

，它是由一個邊長為 231 的正方形和兩個完美長方形拼合而

成的，如圖所示。

完美長方形

正方形 完美長方形

在此之前，人們對圖論還沒有多少研究。 Tutte 等人在

引入網路圖方法後，十分自然地將興趣轉向了對圖論的研

究，並因此而獲得了許多具有重大意義的開創性結果，直

接促進了圖論的發展。

在此之前，人們對圖論還沒有多少研究。 Tutte 等人在 引入網路圖方法後，十分自然地將興趣轉向了對圖論的研 究，並因此而獲得了許多具有重大意義的開創性結果，直

接促進了圖論的發展。

Tutte 等人從著迷於一個數學遊戲開始，而最終卻成了研究圖 論問題的專家創建了圖的對偶理論、 3- 連通理論等。在他們 取得的極其豐碩的研究成果中，人們可以清晰地看到豐富的

抓棋子遊戲

思考題

答案

5

偶數