stringtranslate.com

Проблема изуродованной шахматной доски

Изуродованная шахматная доска
Неудачное решение проблемы изуродованной шахматной доски: помимо двух углов, остаются открытыми две центральные клетки.

Задача об изуродованной шахматной доске — это головоломка на мозаику, предложенная Максом Блэком в 1946 году, в которой задаются следующие вопросы:

Предположим, что у стандартной шахматной доски 8×8 (или шахматной доски ) удалены два диагонально противоположных угла, в результате чего осталось 62 клетки. Можно ли разместить 31 домино размером 2×1 так, чтобы покрыть все эти клетки?

Это неразрешимая головоломка : не существует домино-замощения, удовлетворяющего этим условиям. Одно из доказательств его невозможности использует тот факт, что при удалении углов шахматная доска имеет 32 квадрата одного цвета и 30 другого, но каждое домино должно покрывать одинаковое количество квадратов каждого цвета. В более общем смысле, если любые два квадрата удалены с шахматной доски, оставшиеся могут быть замощены домино, если и только если удаленные квадраты имеют разные цвета. Эта задача использовалась в качестве тестового случая для автоматизированного рассуждения , креативности и философии математики .

История

Задача об изуродованной шахматной доске является примером плиток домино из сеток и полимино , также известных как «модели димеров», общего класса задач, изучение которых в статистической механике восходит к работам Ральфа Х. Фаулера и Джорджа Стэнли Рашбрука в 1937 году . [1] Плитки домино также имеют долгую историю практического использования в дизайне тротуаров и укладке напольных покрытий татами . [2]

Сама проблема изуродованной шахматной доски была предложена философом Максом Блэком в его книге «Критическое мышление» (1946) с намеком на решение ее невозможности, основанное на раскрашивании. [3] [4] Она была популяризирована в 1950-х годах благодаря более поздним обсуждениям Соломона В. Голомба (1954), [5] Джорджа Гамова и Марвина Стерна (1958), [6] Клода Берже (1958), [4] [7] и Мартина Гарднера в его колонке в Scientific American « Математические игры » (1957). [8]

Использование проблемы изуродованной шахматной доски в автоматизированном рассуждении вытекает из предложения по ее использованию Джоном Маккарти в 1964 году. [9] [10] Она также изучалась в когнитивной науке как тестовый случай для творческого понимания, [11] [12] [13] первоначальная мотивация Блэка для проблемы. [3] В философии математики она изучалась в исследованиях природы математического доказательства . [14] [15] [16] [17]

Решение

Головоломку невозможно решить. Домино, размещенное на шахматной доске, всегда будет покрывать одну белую клетку и одну черную клетку. Следовательно, любая коллекция домино, размещенная на доске, будет покрывать равное количество клеток каждого цвета. Но любые два противоположных квадрата имеют одинаковый цвет: оба черные или оба белые. Если их убрать, будет меньше клеток этого цвета и больше клеток другого цвета, что сделает количество клеток каждого цвета неравным и доску невозможной для покрытия. [8] Та же идея показывает, что никакая мозаика домино не может существовать, когда любые две клетки одного цвета (не только противоположные углы) удалены с шахматной доски. [18]

Также было найдено несколько других доказательств невозможности. Доказательство Шмуэля Винограда начинается с индукции. В данной мозаике доски, если ряд имеет нечетное количество квадратов, не покрытых вертикальными домино из предыдущего ряда, то нечетное количество вертикальных домино должно простираться в следующий ряд. Первый ряд тривиально имеет нечетное количество квадратов (а именно, 7), не покрытых домино из предыдущего ряда. Таким образом, по индукции, каждая из семи пар последовательных рядов вмещает нечетное количество вертикальных домино, что дает нечетное общее число. По тем же рассуждениям общее количество горизонтальных домино также должно быть нечетным. Как сумма двух нечетных чисел, общее количество домино — вертикальных и горизонтальных — должно быть четным. Но чтобы покрыть изуродованную шахматную доску, необходимо 31 домино, нечетное число. [19] [20] Другой метод подсчитывает края каждого цвета вокруг границы изуродованной шахматной доски. Их числа должны быть равны в любой области плитки шахматной доски, потому что каждая костяшка домино имеет три ребра каждого цвета, а каждое внутреннее ребро между костяшками домино образует пары границ противоположных цветов. Однако изуродованная шахматная доска имеет больше ребер одного цвета, чем другого. [21]

Теорема Гомори: Удаление любых двух противоположно окрашенных квадратов шахматной доски оставляет область, которую можно замостить домино. Два удаленных квадрата разбивают гамильтонов цикл через квадраты на один (левый) или два (правых) пути через четное число квадратов, позволяя замостить модифицированную шахматную доску домино, уложенными вдоль путей.
Область шахматной доски, не имеющая плитки домино, но для которой доказательства невозможности, основанные на раскраске, не работают.

Если удалить два квадрата противоположных цветов, то оставшуюся доску всегда можно замостить домино; этот результат — теорема Гомори [22] по имени математика Ральфа Э. Гомори , доказательство которого было опубликовано в 1973 году. [18] [20] Теорему Гомори можно доказать с помощью гамильтонова цикла графа сетки, образованного квадратами шахматной доски. Удаление любых двух квадратов противоположного цвета разбивает этот цикл на два пути с четным числом квадратов каждый. Оба эти пути легко разбить на домино, следуя по ним. [22] Теорема Гомори специфична для удаления только одного квадрата каждого цвета. Удаление большего числа квадратов с равным числом каждого цвета может привести к области, которая не имеет замощения домино, но для которой основанные на раскраске доказательства невозможности не работают. [23]

Применение к автоматизированному рассуждению

Задачи укладки плиток домино на полимино , такие как задача об изуродованной шахматной доске, могут быть решены за полиномиальное время , либо путем преобразования их в задачи теории групп , [21] [24] или как примеры двудольного сопоставления . В последней формулировке получается двудольный граф с вершиной для каждой доступной клетки шахматной доски и ребром для каждой пары смежных клеток; задача состоит в том, чтобы найти систему ребер, которая касается каждой вершины ровно один раз. Как и в основанном на раскраске доказательстве невозможности задачи об изуродованной шахматной доске, тот факт, что этот граф имеет больше вершин одного цвета, чем другого, подразумевает, что он не удовлетворяет необходимым условиям теоремы Холла о браке , поэтому сопоставления не существует. [23] [25] [26] Задачу также можно решить, сформулировав ее как задачу удовлетворения ограничений и применив полуопределенное программирование к релаксации . [27]

В 1964 году Джон Маккарти предложил изуродованную шахматную доску в качестве сложной проблемы для автоматизированных систем доказательства , сформулировав ее в логике первого порядка и попросив систему, которая может автоматически определять неразрешимость этой формулировки. [9] Большинство рассмотрений этой проблемы дают решения «в концептуальном смысле», которые не применимы к логической формулировке проблемы Маккарти. [28] Несмотря на существование общих методов, таких как методы, основанные на сопоставлении графов, для разрешения экспоненциально сложно решить логическую формулировку проблемы Маккарти, [29] [30] [31] подчеркивая необходимость методов в искусственном интеллекте , которые могут автоматически изменяться на более подходящее представление проблемы [32] и для систем представления знаний , которые могут управлять эквивалентностями между различными представлениями. [10] Короткие доказательства возможны с использованием разрешения с дополнительными переменными, [33] или в более сильных системах доказательства, позволяющих выражать избегаемые шаблоны мозаичного размещения, которые могут сокращать пространство поиска. [34] Помощники доказательства более высокого уровня способны обрабатывать доказательство невозможности, основанное на раскрашивании, напрямую; к ним относятся Isabelle , [35] система Mizar , [36] и Nqthm . [37]

Связанные проблемы

Проблема тура Вазира

Похожая задача заключается в том, может ли визирь, начинающийся с углового поля обычной шахматной доски, посетить каждое поле ровно один раз и закончить на противоположном угловом поле. Вазир — это сказочная шахматная фигура , которая может перемещаться только на одно поле по вертикали или горизонтали (не по диагонали). Используя рассуждения, аналогичные классическому решению проблемы изуродованной шахматной доски, этот тур визиря не существует. Например, если начальное поле белое, то при каждом ходе чередуются черные и белые поля, последнее поле любого полного тура — черное. Однако противоположное угловое поле — белое. [38] Этот вид тура по шахматной доске также составляет основу типа головоломки под названием Numbrix , которая требует тура, в котором позиции определенных полей соответствуют заданным подсказкам. [39] Невозможность тура из угла в угол показывает невозможность головоломки Numbrix с подсказками 1 в одном углу и 64 в противоположном углу.

Теорема де Брейна касается невозможности упаковки некоторых кубоидов в больший кубоид. Например, согласно этой теореме невозможно заполнить коробку 6 × 6 × 6 кубоидами 1 × 2 × 4. Доказательство использует аналогичный аргумент о раскраске шахматной доски, как и в случае с изуродованной шахматной доской. [40]

Ссылки

  1. ^ Фаулер, Р. Х.; Рашбрук , Г. С. (1937), «Попытка расширить статистическую теорию совершенных растворов», Труды Фарадейского общества , 33 : 1272, doi : 10.1039/tf9373301272
  2. ^ Эриксон, Алехандро; Раски, Фрэнк ; Шурч, Марк; Вудкок, Дженнифер (2010), «Благоприятные расположения татами», на тайском языке, My T.; Сахни , Сартай (ред.), Вычислительная техника и комбинаторика, 16-я ежегодная международная конференция, COCOON 2010, Нячанг, Вьетнам, 19–21 июля 2010 г., Труды , Заметки лекций по информатике, т. 6196, Springer, стр. 288–297, arXiv : 1103.3309 , doi : 10.1007/978-3-642-14031-0_32, ISBN 978-3-642-14030-3, MR  2720105, S2CID  6603662
  3. ^ ab Black, Max (1946), Критическое мышление: Введение в логику и научный метод , Prentice Hall, стр. 157, 433
  4. ^ ab Robinson, JA (1991), «Формальные и неформальные доказательства», в Boyer, Robert S. (ред.), Автоматизированное рассуждение: эссе в честь Вуди Бледсоу , Серия «Автоматизированное рассуждение», т. 1, Springer Netherlands, стр. 267–282, doi :10.1007/978-94-011-3488-0_13, ISBN 978-94-010-5542-0; см. особенно раздел 13.1, «Проблема изуродованной шахматной доски», стр. 271–274 Архивировано 18 июля 2022 г. на Wayback Machine .
  5. ^ Голомб, SW (1954), «Шахматные доски и полимино», The American Mathematical Monthly , 61 (10): 675–682, doi :10.1080/00029890.1954.11988548, JSTOR  2307321, MR  0067055
  6. ^ Гамов, Джордж ; Стерн, Марвин (1958), «Игра в домино», Puzzle-Math , Viking Press, стр. 87–90, ISBN 978-0-333-08637-7
  7. ^ Берж, Клод (1958), Théorie desgraphes et ses application (на французском языке), Dunod, p. 176
  8. ^ ab Gardner, Martin (февраль 1957), «Ассортимент сводящих с ума головоломок», Mathematical Games, Scientific American , 196 (2): 152–158, doi :10.1038/scientificamerican0257-152, JSTOR  24941903; для решения см. Гарднер, Мартин (март 1957 г.), «Некоторые старые и новые версии игры «тик-так-нолики», плюс ответы на головоломки прошлого месяца», Математические игры, Scientific American , 196 (3): 160–168, doi :10.1038/scientificamerican0357-160, JSTOR  24940785. Перепечатано в книге «Мои лучшие математические и логические головоломки» (Dover Publications, 1994), страницы 2 и 39.
  9. ^ ab McCarthy, John (17 июля 1964 г.), A Hard ore for proof procedure, Stanford AI Memo, т. 16, архивировано из оригинала 2021-05-16 , извлечено 2022-07-18
  10. ^ ab Kerber, Manfred; Pollet, Martin (2005), "Крепкий орешек для управления математическими знаниями", в Kohlhase, Michael (ред.), Управление математическими знаниями, 4-я международная конференция, MKM 2005, Бремен, Германия, 15-17 июля 2005 г., Пересмотренные избранные статьи , Конспект лекций по информатике, т. 3863, Springer, стр. 81–95, doi :10.1007/11618027_6, ISBN 978-3-540-31430-1
  11. ^ Каплан, Крейг А.; Саймон, Герберт А. (июль 1990 г.), «В поисках понимания», Cognitive Psychology , 22 (3): 374–419, doi :10.1016/0010-0285(90)90008-r, S2CID  54334455
  12. ↑ Акин, Омер; Акин, Джем (январь 1998 г.), «О процессе творчества в головоломках, изобретениях и проектах», Автоматизация в строительстве , 7 (2–3): 123–138, doi :10.1016/s0926-5805(97)00057-5
  13. ^ Билалич, Мерим; Граф, Марио; Ваци, Неманья; Данек, Амори Х. (август 2019 г.), «Когда решение уже на пороге: более высокая производительность решения, но сниженный опыт «ага!» для шахматных экспертов в проблеме изуродованной шахматной доски», Cognitive Science , 43 (8): e12771, doi : 10.1111/cogs.12771 , PMID  31446653
  14. ^ Маккензи, Дональд (2005), «Вычисления и культуры доказательства», Philosophical Transactions of the Royal Society , 363 (1835): 2335–2350, Bibcode : 2005RSPTA.363.2335M, doi : 10.1098/rsta.2005.1649, JSTOR  30039731, MR  2197653, PMID  16188609, S2CID  18225791
  15. ^ Кербер, Манфред (2014), «Доказательство и некоторые представления», в Wyatt, Джереми Л.; Петтерс, Дин Д.; Хогг, Дэвид К. (ред.), От животных к роботам и обратно: размышления о сложных проблемах в изучении познания, сборник в честь Аарона Сломана , Cognitive Systems Monographs, т. 22, Springer International Publishing, стр. 65–73, doi :10.1007/978-3-319-06614-1_5, ISBN 978-3-319-06613-4
  16. ^ Тансвелл, Феннер (2015), «Проблема зависимости неформальных доказательств от формальных доказательств», Philosophia Mathematica , Серия III, 23 (3): 295–310, doi :10.1093/philmat/nkv008, MR  3404036
  17. ^ Старикова, Ирина; Ван Бендегем, Жан Поль (2021), «Возвращаясь к изуродованной шахматной доске или многочисленным ролям картины», Logique et Analyse , 64 (255): 289–312, doi :10.2143/LEA.255.0.3290192, MR  4396339, архивировано из оригинала 2022-07-19 , извлечено 2022-07-19
  18. ^ ab Honsberger, R. (1973), "Теорема Гомори", Mathematical Gems I , Математическая ассоциация Америки, стр. 65–67
  19. ↑ Маккарти, Джон (1999), «Творческие решения проблем», семинар AISB по искусственному интеллекту и креативности , заархивировано из оригинала 2018-10-23 , извлечено 2007-04-27
  20. ^ ab Mendelsohn, NS (2004), «Tiling with dominoes», The College Mathematics Journal , 35 (2): 115–120, doi :10.2307/4146865, JSTOR  4146865Мендельсон приписывает первоначальную публикацию теоремы Гомори Хонсбергеру (1973).
  21. ^ ab Propp, Jim (2021), «Влияние Конвея на изучение случайных мозаик», The Mathematical Intelligencer , 43 (2): 40–46, doi :10.1007/s00283-021-10089-3, MR  4278473, S2CID  236397105
  22. ^ ab Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, стр. 12–14, ISBN 978-0-691-11503-0
  23. ^ ab Wright, Colin (2014), «Изуродованная шахматная доска (повторный визит)» (PDF) , Recreational Mathematics Magazine (1): 4–9, MR  3323392, архивировано (PDF) из оригинала 2022-08-08 , извлечено 2022-07-18
  24. ^ Терстон, Уильям П. (1990), «Группы мозаики Конвея», The American Mathematical Monthly , 97 (8): 757–773, doi :10.2307/2324578, JSTOR  2324578, MR  1072815
  25. ^ Уркухарт, Аласдер (2003), «Доказательства разрешения принципов соответствия», Annals of Mathematics and Artificial Intelligence , 37 (3): 241–250, doi :10.1023/A:1021231610627, MR  1969128, S2CID  6753523
  26. ^ Codel, Cayden R.; Reeves, Joseph E.; Heule, Marijn JH ; Bryant, Randal E. (2021), "Bipartite perfect matching benchmarks" (PDF) , в Balyo, Tomáš; Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martin (ред.), Proceedings of SAT Competition 2021: Solver and Benchmark Descriptions , Department of Computer Science Report Series B, vol. B-2021-1, Helsinki: Department of Computer Science, University of Helsinki, pp. 52–53, hdl :10138/333647, архивировано (PDF) из оригинала 2022-07-18 , извлечено 2022-07-18
  27. ^ де Клерк, Этьен; Ван Маарен, Ханс; Уорнерс, Йост П. (2000), «Ослабления проблемы выполнимости с использованием полуопределенного программирования», Журнал автоматизированного рассуждения , 24 (1–2): 37–65, doi :10.1023/A:1006362203438, MR  1750258, S2CID  5727281, архивировано из оригинала 20 июня 2021 г. , извлечено 19 июля 2022 г.
  28. ^ Эндрюс, Питер Б.; Бишоп, Мэтью (1996), «О множествах, типах, неподвижных точках и шахматных досках», в Мильоли, Пьеранджело; Москато, Уго; Мундичи, Даниэле; Орнаги, Марио (ред.), Доказательство теорем с помощью аналитических таблиц и связанных с ними методов, 5-й международный семинар, TABLEAUX '96, Террасини, Палермо, Италия, 15–17 мая 1996 г., Труды , Заметки лекций по информатике, т. 1071, Springer, стр. 1–15, doi :10.1007/3-540-61208-4_1, ISBN 978-3-540-61208-7, заархивировано из оригинала 2022-07-18 , извлечено 2022-07-18 , большинство рассмотрений проблемы в литературе решают ее в концептуальном смысле, но фактически не предоставляют доказательств теоремы ни в одной из исходных формулировок Маккарти
  29. ^ Dantchev, Stefan S.; Riis, Søren (2001), «Трудные для разрешения 'Planar' tautologies», 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 октября 2001 г., Лас-Вегас, Невада, США , IEEE Computer Society, стр. 220–229, doi : 10.1109/SFCS.2001.959896, S2CID  18849777, архивировано из оригинала 2022-09-14 , извлечено 2022-07-18
  30. ^ Алехнович, Майкл (2004), «Проблема изуродованной шахматной доски экспоненциально сложна для разрешения», Теоретическая информатика , 310 (1–3): 513–525, doi : 10.1016/S0304-3975(03)00395-5 , MR  2020358
  31. ^ Разборов, Александр А. (2004), "Нижние границы разрешения для принципов идеального соответствия" (PDF) , Журнал компьютерных и системных наук , 69 (1): 3–27, doi : 10.1016/j.jcss.2004.01.004, MR  2070797, архивировано (PDF) из оригинала 2022-08-08 , извлечено 2022-07-19
  32. ^ Корф, Ричард Э. (1980), «К модели изменений представлений», Искусственный интеллект , 14 (1): 41–78, doi :10.1016/0004-3702(80)90033-8, MR  0587851
  33. ^ Кришнамурти, Балакришнан (1985), «Короткие доказательства для сложных формул», Acta Informatica , 22 (3): 253–275, doi :10.1007/BF00265682, MR  0806206, S2CID  2459540
  34. ^ Heule, Marijn JH ; Kiesl, Benjamin; Biere, Armin (2019), «Clausal proofs of mutilated chessboards», в Badger, Julia M.; Rozier, Kristin Yvonne (ред.), NASA Formal Methods – 11th International Symposium, NFM 2019, Хьюстон, Техас, США, 7–9 мая 2019 г., Труды , Lecture Notes in Computer Science, т. 11460, Springer, стр. 204–210, doi :10.1007/978-3-030-20652-9_13, ISBN 978-3-030-20651-2, S2CID  92989148
  35. ^ Полсон, Лоуренс К. (2001), «Простая формализация и доказательство для изуродованной шахматной доски» (PDF) , Logic Journal of the IGPL , 9 (3): 475–485, doi :10.1093/jigpal/9.3.475, MR  1828741, архивировано (PDF) из оригинала 2022-08-08 , извлечено 2022-07-18
  36. ^ Рудницкий, Петр (1996), Проблема изуродованной шахматной доски в теории облегченных множеств Мицара, Технический отчет, т. TR96-09, Кафедра компьютерных наук Университета Альберты, doi : 10.7939/R3QV3C738, архивировано из оригинала 2022-07-18 , извлечено 2022-07-18
  37. ^ Субраманиан, Сакти (1996), «Интерактивное решение проблемы изуродованной шахматной доски», Журнал логики и вычислений , 6 (4): 573–598, doi :10.1093/logcom/6.4.573, MR  1406233
  38. ^ Bivens, Irl C.; Holshouser, Arthur L.; Klein, Benjamin G. (октябрь 2008 г.), «Схемы Wazir на шахматной доске с препятствиями», Mathematics Magazine , 81 (4): 276–284, doi :10.1080/0025570X.2008.11953562, JSTOR  27643123, S2CID  125950546
  39. ^ Хансон, Мэри Грейс; Нэш, Дэвид А. (весна 2018 г.), «Минимальные и максимальные головоломки Numbrix», Pi Mu Epsilon Journal , 14 (8): 505–514, arXiv : 1706.09389
  40. ^ де Брейн, НГ (1969), «Заполнение коробок кирпичами», The American Mathematical Monthly , 76 (1): 37–40, doi :10.2307/2316785, JSTOR  2316785, MR  0234841

Внешние ссылки

На Викискладе есть медиафайлы по теме « Задача об изуродованной шахматной доске» .