Kwadraty MacMahona
MacMahon Squares to nazwa nadana rekreacyjnej układance polegającej na dopasowywaniu krawędzi, opublikowanej po raz pierwszy przez Percy'ego MacMahona w 1921 roku, w której 24 unikalnie trójkolorowe kwadraty są ułożone obok siebie, dopasowując kolory , tworząc siatkę 4 na 6 . Takie teselacyjne mają wiele wariantów, które są określone przez ograniczenia dotyczące sposobu ułożenia 24 kwadratów. Ta gra została również skomercjalizowana w wielu formach fizycznych przez różne firmy.
Gra
Kwadraty MacMahona zostały po raz pierwszy opublikowane w traktacie Percy'ego Alexandra MacMahona z 1921 r. New Mathematical Pastimes . Oryginalna wersja składała się z jednej kopii każdego z 24 różnych kwadratów, które można wykonać, kolorując krawędzie kwadratu jednym z trzech kolorów. (Tutaj „różne” oznacza maksymalnie rotację.) Celem jest ułożenie kwadratów w siatkę 4 na 6, tak aby gdy dwa kwadraty mają wspólną krawędź, wspólna krawędź była tego samego koloru w obu kwadratach.
W 1964 roku superkomputer posłużył do wyprodukowania 12 261 rozwiązań podstawowej wersji układanki MacMahon Squares, o czasie działania około 40 godzin.
Gra MacMahon Squares jest przykładem układanki polegającej na dopasowywaniu krawędzi. Rodzina takich problemów to NP-zupełna . Istnieje w sumie 24 różnych kwadratów dla 3 kolorów. Dla danej liczby kolorów liczbę kwadratów można znaleźć za pomocą wyrażenia .
Warianty
Układ kontaktowy
W swojej książce MacMahon zasugerował możliwość określenia, które granice mogą się ze sobą stykać, na podstawie ich kolorów. Dzieje się tak przez pewną permutację 3 kolorów, opisaną przez C a,b,c . Tutaj a, b i c reprezentują przesunięcie kolorów, do którego można dopasować pierwszy, drugi i trzeci kolor. „1” jest dopasowane do samego siebie, a „2” oznacza, że musi być dopasowane do innego koloru.
Na przykład C 1,1,1 reprezentuje 1 do 1, 2 do 2 i 3 do 3, ponieważ każde z tych dopasowań jest reprezentowane przez liczbę 1. Alternatywnie, C 1,2 reprezentuje 1 do 1 i 2 do 3 jako dopasowanie 1 do 1 jest reprezentowane przez liczbę 1, a dopasowanie między 2 a 3 jest reprezentowane przez 2. Więcej kolorów można opisać w podobny sposób. Na przykład kolorowanie C 1,2,2,2 reprezentuje 1 do 1, 2 do 3, 4 do 5 i 6 do 7.
Stąd widzimy, że jedynymi możliwymi liczbami opisującymi parowanie są 1 i 2, ponieważ 3 lub więcej po prostu pomija kolor, który w przeciwnym razie byłby używany tak samo, ponieważ kolory są względne .
Granice
Innym sposobem na zmianę układanki jest ograniczenie, które kolory do kwadratu tworzą kolory obramowania. W klasycznej układance kwadratów MacMahona na granicy jest łącznie 20 miejsc. Liczba każdego koloru, która może być obecna w tych 20 miejscach, może być opisana przez B a, b, c, gdzie a, b i c to liczba każdego koloru elementów granicznych.
Na przykład B 20,0,0 reprezentuje 20 pierwszego koloru i żadnej reszty, ponieważ pierwszy kolor stanowi już wszystkie dostępne pola graniczne. Alternatywnie B 10,10,0 reprezentuje 10 pierwszego koloru i 10 następnego. W podobny sposób można opisać więcej kolorów. Na przykład granica B 22,16,8,2 reprezentuje 22 z pierwszego, 16 z drugiego, 8 z następnego i 2 z ostatnich kolorów, aby wypełnić kolory obramowania.
Stąd widzimy, że jedynymi możliwymi liczbami opisującymi liczbę każdego koloru tworzącego granicę są liczby parzyste, ponieważ oznaczałoby to nieparzystą liczbę innego koloru, co naruszałoby parzystość całkowitej liczby trójkątów .
Analogiczne łamigłówki
MacMahon Squares, wraz z wariacjami na temat tego pomysłu, został skomercjalizowany jako Multimatch.
Kolejną łamigłówką o podobnych właściwościach są Kostki MacMahona, czyli zestaw 30 kostek, których boki są pomalowane na jeden z 6 różnych kolorów. W przeciwieństwie do układanki Kwadraty MacMahona, nie uwzględniamy wszystkich 2226 możliwych kostek, ale tylko kostki zawierające dokładnie 6 różnych kolorów i po 1 z każdego z 6 kolorów.
Kwadraty MacMahon służyły jako punkt odniesienia dla wielu innych zagadek. Niektóre z nich to Układanka Nelsona, Płytka Wanga i TetraVex .