Проблема изуродованной шахматной доски - это мозаичная головоломка, предложенная философом Максом Блэком в его книге « Критическое мышление» (1946). Позже это обсуждалось Соломоном В. Голомбом (1954), Гамовым и Стерном (1958) и Мартином Гарднером в его колонке « Математические игры » в журнале Scientific American . Проблема в следующем:
Предположим, что на стандартной шахматной доске 8 × 8 удалены два диагонально противоположных угла, в результате чего осталось 62 клетки. Можно ли поставить 31 домино размером 2 × 1 так, чтобы покрыть все эти квадраты?
Большинство рассмотрений этой проблемы в литературе дает решения «в концептуальном смысле» без доказательств. [1] Джон Маккарти предложил это как сложную проблему для автоматизированных систем доказательства . [2] На самом деле, ее решение с использованием разрешения системы умозаключений экспоненциально трудно. [3]
Решение
Головоломку невозможно решить. Домино, размещенное на шахматной доске, всегда покрывает один белый квадрат и один черный квадрат. Таким образом, набор домино, размещенных на доске, покроет равное количество квадратов каждого цвета. Если убрать два белых угла с доски, то 30 белых квадратов и 32 черных квадрата останутся закрытыми домино, так что это невозможно. Если вместо этого удалить два черных угла, то останется 32 белых квадрата и 30 черных квадратов, так что это снова невозможно. [4]
Аналог
Аналогичная задача спрашивает, может ли муравей, начавший с углового квадрата неиспорченной шахматной доски, посетить все клетки ровно один раз и закончить на противоположном угловом квадрате. Диагональные ходы запрещены; каждый ход должен быть по ряду или по иерархии.
Используя те же рассуждения, эта задача невозможна. Например, если начальный квадрат белый, так как каждый ход чередуется между черными и белыми квадратами, последний квадрат любого полного тура будет черным. Однако противоположный угловой квадрат белый. [5]
Теорема Гомори
Удаление одного черного и одного белого квадратов на этом гамильтоновом цикле (примеры показаны знаком ×) дает один (A) или два (B) пути с четным числом квадратов. |
То же доказательство невозможности показывает, что не существует мозаики домино, когда любые два белых квадрата удаляются с шахматной доски. Однако, если убрать два квадрата противоположных цветов, то всегда можно выложить оставшуюся доску домино; Этот результат называется теоремой Гомори в , [6] и назван после того, как математик Ральф Гомори , доказательство которой было опубликовано в 1973 г. [7] теорема Гомори может быть доказана с помощью гамильтонова цикла в графе сетки , образованной шахматной доски квадратов; удаление двух квадратов противоположного цвета разбивает этот цикл на два пути с четным числом квадратов в каждом, оба из которых легко разделить на домино.
Смотрите также
- Замощение прямоугольника тетромино
- Теорема Де Брейна - Пример упаковки коробки 6 × 6 × 6 кубоидами 1 × 2 × 4
- Головоломка Ленивец – Граацма
Заметки
- ^ Эндрюс, Питер Б .; Бишоп, Мэтью (1996), "О множествах, типах, неподвижных точках и шахматных досках", доказательство теорем с помощью аналитических таблиц и родственных методов: 5-й международный семинар, Tableaux '96, Terrasini, Палермо, Италия, 15-17-е, 1996, Proceedings , Lecture Notes in Computer Science, Springer-Verlag,
большинство описаний проблемы в литературе решают ее в концептуальном смысле, но фактически не предоставляют доказательств теоремы ни в одной из оригинальных формулировок Маккарти.
- ^ Артхан, RD (2005), изувеченного шахматная теорема в Z (PDF) , извлекаются 2007-05-06 ,
изувеченного шахматная теорема была предложена более 40 лет назад Джоном Маккарти как «крепкий орешек» для автоматического рассуждения.
- ^ Алехнович, Майкл (2004), "Испорченная проблема шахматной доски экспоненциально трудно для разрешения", Теоретическая информатика , 310 (1-3): 513-525, DOI : 10.1016 / S0304-3975 (03) 00395-5.
- ^ Маккарти, Джон (1999), «Творческие решения проблем», семинар AISB по искусственному интеллекту и творчеству , извлечено 27 апреля 2007 г.
- ^ Миодраг Петкович, Математика и шахматы: 110 занимательных задач и решений , ISBN 0-486-29432-3
- ^ Уоткинс, Джон Дж. (2004), По всей доске: математика задач на шахматной доске , Princeton University Press, стр. 12–14 , ISBN 978-0-691-11503-0.
- ↑ Согласно Мендельсону, оригинальная публикация находится в книге Хонсбергера. Мендельсон, NS (2004), "Черепица домино", Колледж Математика Журнал , Математическая ассоциация Америки, 35 (2): 115-120, DOI : 10,2307 / 4146865 , JSTOR 4146865; Хонсбергер Р. (1973), Mathematical Gems I , Mathematical Association of America.
Рекомендации
- Гамов, Георгий ; Стерн, Марвин (1958), Puzzle-Math , Viking Press, ISBN 978-0-333-08637-7
- Гарднер, Мартин (1994), Мои лучшие математические и логические головоломки , Дувр, ISBN 0-486-28152-3
Внешние ссылки
- Домино на шахматной доске Джима Лоя
- Домино на шахматной доске
- Теорема Гомори Джея Варендорфа, Демонстрационный проект Вольфрама .