Проблема обрізаної шахівниці

Проблема обрізаної шахівниці — це складальна головоломка, запропонована філософом Максом Блеком у книзі Critical Thinking (1946). Пізніше цієї проблеми торкалися Соломон Голомб (1954), Гамов та Штерн, (1958) та Мартін Гарднер в його колонці «Математичні ігри» в Scientific American. Проблема формулюється наступним чином:

Припустімо, зі стандартної (8x8) шахівниці видалили дві клітинки в діагонально протилежних кутах, і залишилось 62 клітинки. Чи можливо розмістити 31 доміно розміром 2x1 так, щоб покрити всі ці клітинки?

abcdefgh
8
8
77
66
55
44
33
22
11
abcdefgh
Проблема обрізаної шахівниці.

Більшість розмірковувань над цією проблемою надають рішення «в концептуальному сенсі» без доказів.[1] Джон МакКарті запропонував її[2] як складну проблему для автоматичних доказових систем.[3] Насправді, рішення цієї проблеми з використанням резолютивної системи виходу надзвичайно важке.[4]

Рішення

Головоломку неможливо закінчити. Доміно, покладене на шахівницю, завжди покриє одну білу і одну чорну клітинку. Отже, набір доміно, розташований на шахівниці, покриє однакову кількість клітинок кожного кольору. Якщо з шахівниці забрати дві білі клітинки, то залишиться 30 білих клітинок та 32 чорних клітинки, тому закрити всі клітинки, що залишились, неможливо. Якщо з шахівниці забрати дві білі клітинки, то залишиться 30 чорних клітинок та 32 білих клітинки, і ситуація та сама.[5]

Приклад проблеми шахівниці, що показує пусті клітинки



Теорема Гоморі

Доказ тої самої неможливості показує, що не існує ніякого складання доміно, коли будь-які дві білі (або чорні) клітинки видалені з шахівниці. Однак, якщо видалені дві клітинки різних кольорів, то завжди можливо заповнити доміно клітинки, що залишились на шахівниці; цей наслідок називається теорема Гоморі,[6] на честь математика Ральфа Гоморі, чий доказ був опублікований в 1973 році.[7] Теорема Гоморі була доведена з використанням Гамільтонова циклу графу-решітки, сформованого клітинками шахівниці; видалення двох клітинок різних кольорів розриває цей цикл на два шляхи з рівною кількістю клітинок кожен та які дуже легко поділити на доміно.

Примітки
  1. 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. «більшість рішень цієї проблеми в літературі вирішують її в концептуальному сенсі, однак не дають доказів теореми для обох оригінальних формулювань МакКарті.»
  2. 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, була вирішена тут.»
  3. Arthan, R. D. (2005). The Mutilated Chessboard Theorem in Z. Процитовано 6 травня 2007. «Теорема обрізаної шахівниці була запропонована більше 40 років тому Джоном МакКарті як “міцний горішок” для автоматичного міркування.»
  4. 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..
  5. Маккарті, Джон (1999). Creative Solutions to Problems. AISB Workshop on Artificial Intelligence and Creativity. Процитовано 27 квітня 2007.
  6. Watkins, John J. (2004). Across the board: the mathematics of chessboard problems. Princeton University Press. с. 12–14. ISBN 978-0-691-11503-0..
  7. Відповідно до Мендельсона, оригінальна публікація була у книзі Хонсбергера. Mendelsohn, N. S. (2004). Tiling with dominoes. The College Mathematics Journal (Mathematical Association of America) 35 (2): 115–120. JSTOR 4146865. doi:10.2307/4146865.; Honsberger, R. (1973). Mathematical Gems I. Mathematical Association of America..

Джерела

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.