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

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

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

Припустімо, зі стандартної (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 (PDF), процитовано 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.

Джерела

Посилання

Вікісховище має мультимедійні дані за темою: Проблема обрізаної шахівниці