前面為自己所想紀錄, 不一定正確; 圖片為 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 時, 好像這思路有點道理, 比較像圖論的做法 (著色相關定理?)
這樣比較能回答第二個問題
要證明這個問題,我們首先觀察原始 8x8 的西洋棋盤。
這個棋盤可以看作是一個由 64 個格子組成的棋盤,其中有黑白相間的格子排列。
如果我們把棋盤上的格子來進一步思考,那麼不妨把左上角的格子視為白色。 在這樣的黑白交錯排列中,無論是在橫排還是縱列上,兩個相鄰的格子一定是一黑一白。
因此,一個 1x2 的長方形(也就是所謂的「骨牌」)必定覆蓋一個黑色格子和一個白色格子。 8x8 的棋盤中擁有 32 個白色格子和 32 個黑色格子。
現在我們去掉了兩個位於同一條對角線上的頂角格子,這兩個被去掉的格子的顏色必定是相同的。這是因為棋盤的對角線上,所有格子的顏色都是一樣的。因此,如果第一個頂角格子是白色,那麼另一個被去掉的頂角格子也會是白色(或都為黑色)。
去掉這兩個相同顏色的格子之後,留在棋盤上的格子們會呈現不平衡的色塊數。
例如,如果你去掉了兩個白色格子,那麼棋盤上便剩下 30 個白色格子和 32 個黑色格子。
由於每個 1x2 的長方形要求必須覆蓋一個白色和一個黑色格子,因此在剩下的 62 格棋盤中,我們總有兩個格子的顏色無法成對,導致無法用 1x2 長方形完整地覆蓋。
因此,去除棋盤上同一對角線的兩個頂角格子後,剩下的棋盤無法被完全分割成若干個 1x2 的長方形直接證明這個結論的正確性。
沒有留言:
張貼留言