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

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

abcdefgh
8
h8 чорний хрестик
a1 чорний хрестик
8
77
66
55
44
33
22
11
abcdefgh
Проблема обрізаної шахівниці.

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

Більшість розмірковувань над цією проблемою надають рішення «в концептуальному сенсі» без доказів.[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. doi:10.2307/4146865. JSTOR 4146865. ; Honsberger, R. (1973). Mathematical Gems I. Mathematical Association of America. .

Джерела ред.

Посилання ред.