肢解西洋棋盤問題
肢解西洋棋盤問題（英語：mutilated chessboard problem）屬於平鋪拼圖問題，最早是由Max Black在1946年的《Critical Thinking》中提出。後來數學家所羅門·格倫布（1954年）及馬丁·加德納（在雜誌《科學人》中的專欄《Mathematical Games》中）都有討論到此問題。問題：「假設一個標準的8x8格西洋棋棋盤，移除對角的2個方塊，餘下62個方塊。可不可以用31個2x1格骨牌來蓋上餘下方塊呢？」
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
肢解西洋棋盤問題
大部份討論此問題的文獻是在概念上說明此問題[1]，電腦科學家約翰·麥卡錫認為這問題對於自動證明系統而言是很難的問題[2]。若使用歸結系統，其解的困難度是指數等級[3]。
解法
肢解西洋棋盤問題是無解的。西洋棋盤上的2x1格骨牌一定會佔據一個白色方格及一個黑色方格，因此被骨牌填滿的位置，白色方格及黑色方格的個數相同。在肢解西洋棋盤問題中，若移除的二個是白色方格，有32個黑色方格及30個白色方格要填滿，兩者數量不同，無法用2x1格骨牌填滿。若移除的二個是黑色方格，有30個黑色方格及32個白色方格要填滿，還是無法用2x1格骨牌填滿[4]。
高莫利定理
只要西洋棋盤上移除二個同色的方格，相同的方式可以證明，移除方格後的棋盤無法用2x1格骨牌填滿。不過若填除的是二個不同顏色的方格，一定可以用2x1格骨牌填滿，這個結果稱為高莫利定理（Gomory's theorem）[5]，得名自數學家拉爾夫·愛德華·高莫利，他在1973年提出的證明[6]。高莫利定理可以用棋盤組成格子圖的哈密頓圖來證明，移去二個不同色的方格會將哈密頓圖切成二部份，每個部份的黑色方格及白色方格都一樣多，兩部份都可以用2x1格骨牌填滿。
參見
引用來源
- ^ Andrews, Peter B.; Bishop, Matthew, On Sets, Types, Fixed Points, and Checkerboards, Theorem Proving With Analytic Tableaux and Related Methods: 5th International Workshop, Tableaux '96, Terrasini, Palermo, Italy, 15-17th, 1996, Proceedings, Lecture Notes in Computer Science, Springer-Verlag, 1996,
most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations.
- ^ Arthan, R. D., The Mutilated Chessboard Theorem in Z (PDF), 2005 [2007-05-06], （原始內容 (PDF)存檔於2017-12-14）,
The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a "tough nut to crack" for automated reasoning.
- ^ Alekhnovich, Michael, Mutilated chessboard problem is exponentially hard for resolution, Theoretical Computer Science, 2004, 310 (1-3): 513–525, doi:10.1016/S0304-3975(03)00395-5.
- ^ McCarthy, John, Creative Solutions to Problems, AISB Workshop on Artificial Intelligence and Creativity, 1999 [2007-04-27], （原始內容存檔於2019-04-05）
- ^ Watkins, John J., Across the board: the mathematics of chessboard problems, Princeton University Press: 12–14, 2004, ISBN 978-0-691-11503-0.
- ^ According to Mendelsohn, the original publication is in Honsberger's book. Mendelsohn, N. S., Tiling with dominoes, The College Mathematics Journal (Mathematical Association of America), 2004, 35 (2): 115–120, JSTOR 4146865, doi:10.2307/4146865; Honsberger, R., Mathematical Gems I, Mathematical Association of America, 1973.
參考資料
- Gamow, George; Stern, Marvin, Puzzle-Math, Viking Press, 1958, ISBN 978-0-333-08637-7
- Gardner, Martin, My Best Mathematical and Logic Puzzles, Dover, 1994, ISBN 0-486-28152-3
外部連結
- Dominoes on a Checker Board by Jim Loy
- Dominoes on a Checker Board （頁面存檔備份，存於網際網路檔案館）
- Gomory's Theorem （頁面存檔備份，存於網際網路檔案館） by Jay Warendorff, The Wolfram Demonstrations Project.