Проблема обрізаної шахівниці це запропонована філософом Максом Блеком у книзі Critical Thinking 1946 Пізніше цієї пробле

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

	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

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

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

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

Рішення

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

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

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

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

Примітки

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"¹, була вирішена тут.
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 .
Відповідно до Мендельсона, оригінальна публікація була у книзі Хонсбергера. 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
Гарнднер, Мартін (1994), My Best Mathematical and Logic Puzzles, Dover, ISBN

Посилання

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

Доміно на шахівниці
Теорема Гоморі від Джея Варендорффа на .

[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"¹, була вирішена тут.

[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.

[McCarthy-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 .

[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.