內固——n*n的棋盤上最多可以放多少個馬

優秀書籍

定理：

如果n是偶數（n>4）那么n*n的棋盤有一個哈密頓圈。

如果n是奇數（n>3）那么n*n的棋盤有一個哈密頓鏈。

像這樣的圖還可以構造一些，不過基本上都差不多。

總結起來就是，最中間的格子是比較特殊的，上圖中標號1-8的這8個格子構成1個圈，

其余的16個格子也構成1個圈，相當于5*5的棋盤其實就是3個圈組合而成，只要適當地選擇斷點，即可把3個圈連接成一條鏈。

如果選取的起點不同，得到的哈密頓鏈還是略有區別的。

比如：112象棋（12）

關于上面的2個定理，書上的意思是用數學歸納法來證明，從n=k變成n=k+4相當于在原來的基礎上，套上了一個寬度為2的邊框。這個邊框是若干個哈密頓圈組成的，只要在適當的地方斷開，就可以和里面的k*k連接起來。不過這個定理是否正確，我也不確定。

下面討論，7*7的棋盤去掉中間的3*3如何形成哈密頓圈。

首先，角落的點只有2個鄰居，那么在圈里面，這2個點也一定都是他的鄰居。

其他的，以此類推，可以得到下圖：

對于那些已經連了2條線的點，自然是沒有任何懸念了，所以接下來只需要考慮那些恰好連了1條線的點該如何連接起來。將上圖化簡如下：

黑色的線表示一定相連，紅色的線表示可能相連。

這樣，可以得到這16個點的哈密頓圈：

與此對應，可以得到原圖：

這是由2個哈密頓圈構成的。

這樣，整個通過把大的圈斷開一個地方，可以得到下圖：

在把紫色的哈密頓圈和這個長為41的哈密頓鏈連接起來，即可得到7*7的哈密頓鏈

下面用這個定理來分析，n*n的棋盤上（n>4）最多可以放多少個馬，使得它們互不攻擊，即馬的內固數是多少。

如果n=2*k，因為有一個哈密頓圈，圈的大小是4*k*k，所以內固數不超過2*k*k，即n*n/2。

如果n=2*k+1，因為有一個哈密頓鏈，圈的大小是4*k*k+4*k+1，所以內固數不超過2*k*k+2*k+1,即（n*n+1）/2。

我們將棋盤按照國際象棋的棋盤來染色，使得白色的格子數-黑色的格子數=0或1。

也就是說，白色格子有（n*n+1）/2個，在所有的白色格子里面放馬，這些馬都不能互相攻擊。

所以，馬的內固數是（n*n+1）/2

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。