Od 14 do 24
Ile co najmniej pól szachownicy (8×8) należy zablokować (uczynić nieprzechodnimi), aby pozostałe można było obejść wieżą po jedynej możliwej trasie zamkniętej? To pytanie dotyczy tzw. unikalnych cykli wieżowych (UCW), które były tematem artykułu w sierpniowym Świecie Nauki. Z tym tematem wiązało się także zadanie autorstwa apartado, zamieszczone w poprzednim wpisie. Na diagramie tego zadania pojawia się w trakcie rozwiązania poniższy UCW.
Ten diagram z jedynym możliwym cyklem jest równocześnie odpowiedzią na powyższe pytanie: wystarczą 4 blokady. Takiego rozmieszczenia 4 blokad z UCW, jak na powyższym rysunku, brak jednak wśród kompletu 14 zaprezentowanych we wspomnianym artykule – na co zwrócił uwagę Andrzej111. W artykule jest jednak wzmianka, że nie ma pewności, czy te 14 ustawień to wszystkie – i okazało się, że istotnie nie wszystkie.
A teraz najlepsze. Pisząc o rzekomym komplecie 14 ustawień korzystałem z angielskich źródeł, zapominając o… polskich. Moja niepamięć wydaje się jednak usprawiedliwiona, bo temat blokad gościł w Łamiblogu przed 15 laty i wówczas w komentarzach Antyp zamieścił zestaw – bagatela – 24 różnych ustawień 4 blokad na szachownicy 8×8, dających UCW . Czy to już wszystkie? Nie wiadomo. Proponuję coś prostszego, ale też chyba dla programistów, bo „na piechotę”, czyli bez wsparcia komputerowego raczej nie do ruszenia, a przynajmniej zbyt żmudne.
Liczby całkowicie różnych (z dokładnością do obrotów i odbić lustrzanych) sposobów rozmieszczenia minimalnej liczby blokad na najmniejszych szachownicach, zapewniających UCW, wynoszą:
2×2 – 0 blokad – 1 sposób (brak sposobu to też sposób)
3×3 – 1 blokada – 2 sposoby
4×4 – 2 blokady – 3 sposoby
5×5 – 3 blokady – ? sposob(y)(ów)
Jaką liczbą należy zastąpić znak zapytania?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Jestem pewien, że w wolnych chwilach komputer HAL dzieli swoje procesory na dwóch graczy i delektuje się grą o następujących zasadach:
Na szachownicy 8×8 rozmieszczamy 4 figury szachowe (po dwie w kolorach czarny/biały) i wykonujemy nimi na przemian posunięcia.
Celem gry jest spowodowanie żeby przeciwnik ułożył jeden z układów „blokujących” / tworzących UCW wśród wolnych pól.
Trudność mogłaby sprawiać kwestia symetrii wszelakich, ale przecież dla HALa to nie jest problem.
Niuansów nie znam – proszę pytać HALa.
Znalazłem 12 układów
= = o = = = = o = = = = o = = = = o = = = = = = = = = = = =
= = o = = = = = = = = = = = = = = = = = = o o = = = o = = =
= = o = = = o = = = = = o = = = = = = = = = o = = = = o o =
= = = = = = = = o = = = o = = = o o = = = = = = = = = = = =
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
o = = = = o = = = = o = = = = o = = = = = = o = = = = o = =
= = o = = = = o = = = = = = = = = = = = = = = = = = = o = =
= = o = = = = = = = = = o o = = = = o = = o o = = = = = = =
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
= = = = = = = o = = = = = = = = = o = = = = = = = = = o = =
W poprzednim komentarzu pozżerało mi spacje.
= = o = =/= = o = =/= = o = =/= = o = =/= = = = =/= = = = =
= = o = =/= = = = =/= = = = =/= = = = =/= o o = =/= o = = =
= = o = =/= o = = =/= = o = =/= = = = =/= = o = =/= = o o =
= = = = =/= = = o =/= = o = =/= o o = =/= = = = =/= = = = =
= = = = =/= = = = =/= = = = =/= = = = =/= = = = =/= = = = =
o = = = =/o = = = =/o = = = =/o = = = =/= = o = =/= = o = =
= = o = =/= = o = =/= = = = =/= = = = =/= = = = =/= = o = =
= = o = =/= = = = =/= = o o =/= = = o =/= o o = =/= = = = =
= = = = =/= = = = =/= = = = =/= = = = =/= = = = =/= = = = =
= = = = =/= = o = =/= = = = =/= = o = =/= = = = =/= = o = =
Ciekawe jak bardzo się pomylę:
W miejscu znaku zapytania powinna się znaleźć liczba będąca wynikiem mnożenia liczby 7 oraz liczby poprawnych odpowiedzi w komentarzach.
Jeśli nie będzie problemu z ustaleniem poprawnej odpowiedzi, to pomyłka będzie niewielka.
mp
W międzyczasie wrzucam informację dotyczącą wpisu z 10 sierpnia Bezkwadratowo.
Trzecie zadanie, mrówcze, z podziałem na trzy grupy. Udało mi się znaleźć rozbicie zbioru [1,…,85]. Szczegóły w w/w wpisie.
Wyszło mi 12 po batalii z kompjuterem (mam nadzieję że poprawnie)
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
[1, 0, 0, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0]]
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
[1, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0]
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
Dziwnie mi te wartości przypominają ten ciąg przesunięty o 1
ale nie wiem
https://oeis.org/A307957
5×5 – 3 blokady – 13 sposobów.
A wśród nich dwupak
0-0-x-0-0
0-0-0-0-0
0-0-0-x-0
0-0-0-0-0
0-0-x-0-0
Dwupak ma niestety dwa rozwiązania. Symetryczne .