Проблема обрізаної шахівниці
| 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 | ||
Проблема обрізаної шахівниці — це складальна головоломка, запропонована філософом Максом Блеком у книзі Critical Thinking (1946). Пізніше цієї проблеми торкалися Соломон Голомб (1954), Гамов та Штерн, (1958) та Мартін Гарднер в його колонці «Математичні ігри» в Scientific American. Проблема формулюється таким чином:
Припустімо, зі стандартної (8x8) шахівниці видалили дві клітинки в діагонально протилежних кутах, і залишилось 62 клітинки. Чи можливо розмістити 31 доміно розміром 2x1 так, щоб покрити всі ці клітинки?
Більшість розмірковувань над цією проблемою надають рішення «в концептуальному сенсі» без доказів.[1] Джон МакКарті запропонував її[2] як складну проблему для автоматичних доказових систем.[3] Насправді рішення цієї проблеми з використанням резолютивної системи виходу надзвичайно важке.[4]
Головоломку неможливо закінчити. Доміно, покладене на шахівницю, завжди покриє одну білу і одну чорну клітинку. Отже, набір доміно, розташований на шахівниці, покриє однакову кількість клітинок кожного кольору. Якщо з шахівниці забрати дві білі клітинки, то залишиться 30 білих клітинок та 32 чорних клітинки, тому закрити всі клітинки, що залишились, неможливо. Якщо з шахівниці забрати дві білі клітинки, то залишиться 30 чорних клітинок та 32 білих клітинки, і ситуація та сама.[5]
Доказ тої самої неможливості показує, що не існує ніякого складання доміно, коли будь-які дві білі (або чорні) клітинки видалені з шахівниці. Однак, якщо видалені дві клітинки різних кольорів, то завжди можливо заповнити доміно клітинки, що залишились на шахівниці; цей наслідок називається теорема Гоморі,[6] на честь математика Ральфа Гоморі, чий доказ був опублікований в 1973 році.[7] Теорема Гоморі була доведена з використанням гамільтонового циклу графу-решітки, сформованого клітинками шахівниці; видалення двох клітинок різних кольорів розриває цей цикл на два шляхи з рівною кількістю клітинок кожен та які дуже легко поділити на доміно.
- ↑ Andrews, Peter B.; Bishop, Matthew (1996), 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,
більшість рішень цієї проблеми в літературі вирішують її в концептуальному сенсі, однак не дають доказів теореми для обох оригінальних формулювань МакКарті.
- ↑ Bancerek, Grzegorz (1995), The Mutilated Chessboard Problem—checked by Mizar, у Boyer, Robert; Trybulec, Andrzej (ред.), QED Workshop, II, Warsaw University, с. 25—26,
Проблема, запропонована Джон МакКарті в лекції "Heavy duty set theory"1, була вирішена тут.
- ↑ Arthan, R. D. (2005), The Mutilated Chessboard Theorem in Z (PDF), процитовано 6 травня 2007,
Теорему обрізаної шахівниці запропонував більш як 40 років тому Джон МакКарті як “міцний горішок” для автоматичного міркування.
- ↑ Alekhnovich, Michael (2004), Mutilated chessboard problem is exponentially hard for resolution, Theoretical Computer Science, 310 (1-3): 513—525, doi:10.1016/S0304-3975(03)00395-5.
- ↑ Маккарті, Джон (1999), Creative Solutions to Problems, AISB Workshop on Artificial Intelligence and Creativity, процитовано 27 квітня 2007
- ↑ Watkins, John J. (2004), Across the board: the mathematics of chessboard problems, Princeton University Press, с. 12–14, ISBN 978-0-691-11503-0.
- ↑ Відповідно до Мендельсона, оригінальна публікація була у книзі Хонсбергера. Mendelsohn, N. S. (2004), Tiling with dominoes, The College Mathematics Journal, Mathematical Association of America, 35 (2): 115—120, doi:10.2307/4146865, JSTOR 4146865; Honsberger, R. (1973), Mathematical Gems I, Mathematical Association of America.
- Гамов, Джордж; Штерн, Марвін (1958), Puzzle-Math, Viking Press, ISBN 978-0-333-08637-7
- Гарнднер, Мартін (1994), My Best Mathematical and Logic Puzzles, Dover, ISBN 0-486-28152-3
- Доміно на шахівниці від Джима Лоя
- Доміно на шахівниці
- Теорема Гоморі від Джея Варендорффа на Wolfram Demonstrations Project.