2024年10月20日 星期日

演算法觀點的圖論 習題 1-1

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

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


Q: 證明假設把 8x8 的 西洋棋盤上 位於同一條對角線上的兩個頂角格子去掉(於是剩下一個只有 62 格的棋盤), 則這個棋盤沒辦法分割成若干個 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 個 長方形是奇數個, 矛盾, 所以無法分割


Q: 二分圖的一般性原則, 有可能是 定理 1.8 ?

    二分圖 若且唯若 沒有奇圈

待續


--

2024.10.21

今天問了一下 chatgpt 

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


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

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


Ans: 

要證明這個問題,我們首先觀察原始 8x8 的西洋棋盤。
這個棋盤可以看作是一個由 64 個格子組成的棋盤,其中有黑白相間的格子排列。
如果我們把棋盤上的格子來進一步思考,那麼不妨把左上角的格子視為白色。 在這樣的黑白交錯排列中,無論是在橫排還是縱列上,兩個相鄰的格子一定是一黑一白。
因此,一個 1x2 的長方形(也就是所謂的「骨牌」)必定覆蓋一個黑色格子和一個白色格子。 8x8 的棋盤中擁有 32 個白色格子和 32 個黑色格子。

現在我們去掉了兩個位於同一條對角線上的頂角格子,這兩個被去掉的格子的顏色必定是相同的。這是因為棋盤的對角線上,所有格子的顏色都是一樣的。因此,如果第一個頂角格子是白色,那麼另一個被去掉的頂角格子也會是白色(或都為黑色)。 
去掉這兩個相同顏色的格子之後,留在棋盤上的格子們會呈現不平衡的色塊數。

例如,如果你去掉了兩個白色格子,那麼棋盤上便剩下 30 個白色格子和 32 個黑色格子。 
由於每個 1x2 的長方形要求必須覆蓋一個白色和一個黑色格子,因此在剩下的 62 格棋盤中,我們總有兩個格子的顏色無法成對,導致無法用 1x2 長方形完整地覆蓋。 

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


沒有留言:

張貼留言

熱門文章