Проблема обрізаної шахівниці
Проблема обрізаної шахівниці — це складальна головоломка, запропонована філософом Максом Блеком у книзі 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. Процитовано 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.