Problem z okaleczoną szachownicą
okaleczonej szachownicy to układanka ułożona przez Maxa Blacka w 1946 roku, która pyta:
Załóżmy, że standardowa szachownica 8 × 8 (lub szachownica ) ma usunięte dwa przeciwległe rogi po przekątnej, pozostawiając 62 pola. Czy można ułożyć 31 kostek domina o wymiarach 2×1 tak, aby pokryły wszystkie te kwadraty?
To niemożliwa łamigłówka : nie ma kostki domina spełniającej te warunki. Jednym z dowodów na to, że jest to niemożliwe, jest fakt, że po usunięciu rogów szachownica ma 32 pola w jednym kolorze i 30 w drugim, ale każde domino musi pokrywać tyle samo pól każdego koloru. Mówiąc bardziej ogólnie, jeśli dowolne dwa pola zostaną usunięte z szachownicy, resztę można ułożyć kostkami domina wtedy i tylko wtedy, gdy usunięte kwadraty mają różne kolory. Ten problem został wykorzystany jako przypadek testowy automatycznego rozumowania , kreatywności i filozofii matematyki .
Historia
Problem z okaleczoną szachownicą jest przykładem układania płytek domina siatek i poliomino , znanych również jako „modele dimerów”, ogólnej klasy problemów, których badania w mechanice statystycznej datuje się na prace Ralpha H. Fowlera i George'a Stanleya Rushbrooke'a w 1937 r. Domino płytki mają również długą historię praktycznego zastosowania w projektowaniu nawierzchni i układaniu podłóg tatami .
Sam problem okaleczonej szachownicy został zaproponowany przez filozofa Maxa Blacka w jego książce Critical Thinking (1946), z wskazówką dotyczącą rozwiązania jego niemożliwości opartego na kolorowaniu. Został spopularyzowany w latach pięćdziesiątych XX wieku dzięki późniejszym dyskusjom Solomona W. Golomba (1954), George'a Gamowa i Marvina Sterna (1958), Claude'a Berge'a (1958) i Martina Gardnera w jego kolumnie Scientific American „ Gry matematyczne ” (1957).
Wykorzystanie problemu okaleczonej szachownicy w zautomatyzowanym rozumowaniu wywodzi się z propozycji jego wykorzystania przez Johna McCarthy'ego w 1964 roku. Został on również zbadany w kognitywistyce jako przypadek testowy twórczego wglądu, pierwotnej motywacji Blacka do problemu. W filozofii matematyki badano ją w badaniach natury dowodu matematycznego .
Rozwiązanie
Układanka jest nie do ułożenia. Kostka domina położona na szachownicy zawsze zakrywa jedno białe pole i jedno czarne pole. Dlatego każda kolekcja kostek domina ułożona na planszy będzie obejmować równą liczbę kwadratów każdego koloru. Ale dowolne dwa przeciwległe kwadraty mają ten sam kolor: oba czarne lub oba białe. Jeśli zostaną usunięte, będzie mniej kwadratów tego koloru i więcej kwadratów drugiego koloru, przez co liczba kwadratów każdego koloru będzie nierówna, a plansza będzie niemożliwa do zakrycia. Ta sama idea pokazuje, że żadne kafelki domina nie mogą istnieć, gdy dowolne dwa kwadraty tego samego koloru (nie tylko przeciwległe rogi) zostaną usunięte z szachownicy.
Znaleziono również kilka innych dowodów niemożliwości. Dowód autorstwa Shmuela Winograda zaczyna się od indukcji. W danym ułożeniu planszy, jeśli rząd ma nieparzystą liczbę pól nie zakrytych pionowymi kostkami domina z poprzedniego rzędu, to nieparzysta liczba pionowych kostek domina musi sięgać do następnego rzędu. Pierwszy rząd trywialnie ma nieparzystą liczbę kwadratów (mianowicie 7), które nie są pokryte kostkami domina z poprzedniego rzędu. Zatem przez indukcję każda z siedmiu par kolejnych rzędów zawiera nieparzystą liczbę pionowych kostek domina, co daje nieparzystą liczbę całkowitą. Z tego samego rozumowania całkowita liczba poziomych kostek domina również musi być nieparzysta. Suma dwóch liczb nieparzystych oznacza, że całkowita liczba kostek domina — pionowych i poziomych — musi być parzysta. Ale do zakrycia okaleczonej szachownicy potrzeba 31 kostek domina, co jest liczbą nieparzystą. Inna metoda liczy krawędzie każdego koloru wokół granicy okaleczonej szachownicy. Ich liczba musi być równa w dowolnym obszarze szachownicy, który można ułożyć kafelkami, ponieważ każde domino ma trzy krawędzie każdego koloru, a każda wewnętrzna krawędź między kostkami domina tworzy pary granic przeciwnych kolorów. Jednak okaleczona szachownica ma więcej krawędzi jednego koloru niż drugiego.
Jeśli usunie się dwa kwadraty o przeciwnych kolorach, pozostałą planszę zawsze można wyłożyć kostkami domina; ten wynik jest twierdzeniem Gomory'ego , na cześć matematyka Ralpha E. Gomory'ego , którego dowód został opublikowany w 1973 roku. Twierdzenie Gomory'ego można udowodnić za pomocą cyklu Hamiltona wykresu siatki utworzone przez kwadraty szachownicy. Usunięcie dowolnych dwóch kwadratów o przeciwnych kolorach dzieli ten cykl na dwie ścieżki, z których każda ma parzystą liczbę kwadratów. Obie te ścieżki można łatwo podzielić na kostki domina, podążając nimi. Twierdzenie Gomory'ego jest specyficzne dla usunięcia tylko jednego kwadratu każdego koloru. Usunięcie większej liczby kwadratów z równą liczbą każdego koloru może skutkować regionem, w którym nie ma płytek domina, ale dla którego dowody niemożliwości oparte na kolorowaniu nie działają.
Zastosowanie do zautomatyzowanego wnioskowania
Problemy układania płytek domina na poliomino , takie jak problem okaleczonej szachownicy , można rozwiązać w czasie wielomianowym , albo przekształcając je w problemy w teorii grup , albo jako przypadki dopasowywania dwuczęściowego . W tym ostatnim sformułowaniu otrzymuje się graf dwudzielny z wierzchołkiem dla każdego dostępnego kwadratu szachownicy i krawędzią dla każdej pary sąsiednich kwadratów; problem polega na znalezieniu systemu krawędzi, który dotyka każdego wierzchołka dokładnie raz. Podobnie jak w opartym na kolorowaniu dowodzie niemożliwości problemu z okaleczoną szachownicą, fakt, że ten wykres ma więcej wierzchołków jednego koloru niż drugiego, oznacza, że nie spełnia on niezbędnych warunków twierdzenia Halla o małżeństwie , więc dopasowanie nie istnieje . Problem można również rozwiązać, formułując go jako problem spełnienia ograniczeń i stosując programowanie półokreślone do relaksacji .
W 1964 roku John McCarthy zaproponował okaleczoną szachownicę jako trudny problem dla zautomatyzowanych systemów dowodowych, formułując ją w logice pierwszego rzędu i prosząc o system, który może automatycznie określić nierozwiązywalność tego sformułowania. Większość rozważań nad tym problemem dostarcza rozwiązań „w sensie pojęciowym”, które nie mają zastosowania do logicznego sformułowania problemu przez McCarthy'ego. Pomimo istnienia ogólnych metod, takich jak te oparte na dopasowywaniu grafów, rozwiązanie jest wykładniczo trudne rozwiązać logiczne sformułowanie problemu McCarthy'ego, podkreślając potrzebę metod sztucznej inteligencji , które mogą automatycznie zmieniać się na bardziej odpowiednią reprezentację problemu, oraz systemów reprezentacji wiedzy , które mogą zarządzać równoważnościami między różnymi reprezentacjami. Krótkie dowody są możliwe przy użyciu rozdzielczości z dodatkowymi zmiennymi lub w silniejszych systemach dowodowych umożliwiających wyrażenie możliwych do uniknięcia wzorów kafelków, które mogą przyciąć przestrzeń wyszukiwania. Asystenci sprawdzający wyższego poziomu są w stanie bezpośrednio obsłużyć dowód niemożliwości oparty na kolorystyce; obejmują one Isabelle , system Mizar i Nqthm .
Powiązane problemy
   |
Podobny problem polega na pytaniu, czy wazir zaczynający od rogu zwykłej szachownicy może odwiedzić każde pole dokładnie raz i zakończyć na przeciwległym polu narożnym. Wazir to bajkowa figura szachowa , która może poruszać się tylko o jedno pole w pionie lub poziomie (nie po przekątnej). Używając podobnego rozumowania do klasycznego rozwiązania problemu okaleczonej szachownicy, ta trasa wazira nie istnieje. Na przykład, jeśli początkowe pole jest białe, ponieważ każdy ruch zmienia się między czarnymi i białymi kwadratami, ostatnie pole każdej pełnej trasy jest czarne. Jednak przeciwległy kwadrat narożny jest biały. Ten rodzaj zwiedzania szachownicy stanowi również podstawę układanki zwanej Numbrix , który prosi o wycieczkę, w której pozycje niektórych kwadratów pasują do podanych wskazówek. Niemożliwość zwiedzania od rogu do rogu pokazuje niemożliwość układanki Numbrix ze wskazówkami 1 w jednym rogu i 64 w przeciwnym rogu.
Twierdzenie De Bruijna dotyczy niemożności upakowania pewnych prostopadłościanów w większy prostopadłościan. Na przykład, zgodnie z tym twierdzeniem niemożliwe jest wypełnienie pudełka 6 × 6 × 6 prostopadłościanami 1 × 2 × 4 . Dowód wykorzystuje podobny argument dotyczący szachownicy do problemu okaleczonej szachownicy.
Linki zewnętrzne
- Twierdzenie Gomory'ego autorstwa Jaya Warendorffa, The Wolfram Demonstrations Project .