演算法觀點的圖論 習題 1-1 8x8 西洋棋盤 對角線

前面為自己所想紀錄, 不一定正確; 圖片為 chatgpt 3.5 所回答, 非正解; 

最後 chatgpt 4 回答的, 看來是對的;

Q: 證明假設把 8x8 的 西洋棋盤上 位於同一條對角線上的兩個頂角格子去掉(於是剩下一個只有 62 格的棋盤), 則這個棋盤沒辦法分割成若干個 1x2 的長方形

我想的方式, 完全沒想到要用顏色, 果然還沒學圖論時, 解法超爛... (我放到網頁最後面）

--

2025.2.18 Grok 

要證明在去掉同一條對角線上的兩個頂角格子後的8x8棋盤（現在剩下62格）不能被分割成若干個1x2的長方形，我們可以使用著色法和矛盾證明：

### 著色法

1. **棋盤著色**：

   - 首先，把剩下的62格棋盤以棋盤的方式著色。也就是說，每個2x2的區域中，對角線上會有一個格子是黑色的，另一個是白色的。這意味著整個棋盤上會有32個黑色格子和32個白色格子。

2. **去掉頂角格子**：

   - 去掉同一條對角線上的兩個頂角格子，這兩個格子會是同一種顏色（假設是黑色）。因此，現在棋盤上會有30個黑色格子和32個白色格子。

### 無法分割的證明

3. **1x2長方形的性質**：

   - 每個1x2的長方形會覆蓋1個黑色格子和1個白色格子，因為它會橫跨兩個相鄰的格子，而相鄰的格子顏色一定不同。

4. **矛盾**：

   - 假設我們能把這個62格的棋盤分割成若干個1x2的長方形，那麼每個長方形都會覆蓋1個黑色格子和1個白色格子。這樣的話，用完所有的長方形後，黑色格子和白色格子的數量應該是一樣的。然而，我們現在有30個黑色格子和32個白色格子，這是不可能達成平衡的。因為30和32不是偶數，無法用1x2的長方形完美覆蓋。

因此，我們得到矛盾：如果我們能用1x2的長方形覆蓋整個棋盤，則黑色和白色的格子數量應該相等，但實際上兩種顏色的格子數量不同。所以，這個去掉兩個頂角格子的棋盤不能被分割成若干個1x2的長方形。

--

2025.2.11 deepseek

今天在自己的 macbook pro 2024 m4 上安裝了 deepseek model, 可以離線作答:

 (安裝步驟記錄在 - 此網頁 ）

--

2024.10.21

今天問了一下 chatgpt 

chatgpt 3.5 的時候, 它還不會解, 打了一個煙霧彈

到 chatgpt 4 時, 好像這思路有點道理, 比較像圖論的做法 (著色相關定理?) 

這樣比較能回答第二個問題

Ans: 

要證明這個問題，我們首先觀察原始 8x8 的西洋棋盤。

這個棋盤可以看作是一個由 64 個格子組成的棋盤，其中有黑白相間的格子排列。

如果我們把棋盤上的格子來進一步思考，那麼不妨把左上角的格子視為白色。 在這樣的黑白交錯排列中，無論是在橫排還是縱列上，兩個相鄰的格子一定是一黑一白。

因此，一個 1x2 的長方形（也就是所謂的「骨牌」）必定覆蓋一個黑色格子和一個白色格子。 8x8 的棋盤中擁有 32 個白色格子和 32 個黑色格子。

現在我們去掉了兩個位於同一條對角線上的頂角格子，這兩個被去掉的格子的顏色必定是相同的。這是因為棋盤的對角線上，所有格子的顏色都是一樣的。因此，如果第一個頂角格子是白色，那麼另一個被去掉的頂角格子也會是白色（或都為黑色）。 

去掉這兩個相同顏色的格子之後，留在棋盤上的格子們會呈現不平衡的色塊數。

例如，如果你去掉了兩個白色格子，那麼棋盤上便剩下 30 個白色格子和 32 個黑色格子。 

由於每個 1x2 的長方形要求必須覆蓋一個白色和一個黑色格子，因此在剩下的 62 格棋盤中，我們總有兩個格子的顏色無法成對，導致無法用 1x2 長方形完整地覆蓋。 

因此，去除棋盤上同一對角線的兩個頂角格子後，剩下的棋盤無法被完全分割成若干個 1x2 的長方形直接證明這個結論的正確性。

--

-- 剛開始學圖論時我想的方法 ：

由上而下, 由左而右, 將格子標記成 (0,0) ~ (7,7), 假設 (0,0) 和 (7,7) 格子被拿掉

在 第 0 row : (0, Y), 因為 (0,0) 被拿掉, 剩下 7 個格子為奇數, 所以從第 0 row  開始往下擺直的

1x2 的長方形有奇數個;

因為第0row 擺直的有奇數個, 所以第 1 row 擺直的有奇數個...到最後第 6 row 擺直的有奇數個

因為 0~6 為 奇數個 rows, 所以所有擺直的有奇數個

同理從 第 0 column 推導, 可得知, 所有擺橫的有奇數個

這樣所有 1x2 的 長方形 有 偶數個; 

但 62 格 只有 31 個 長方形是奇數個, 矛盾, 所以無法分割