17338 WiZ1 072

puzeland

'redaguje Marek Penszko

I-

H

rys. 5

WĘDRÓWKI M ROWKI W.

Proste formy sztucznego życia mają przynajmniej jedną zaletę: są pozbawione dylematów. Mrówka Langdona, gatunek z rodziny turmitów, czyli najprostszych automatów komórkowych, znalazłszy się na rozdrożu, nie staje przed koniecznością wyboru. W zależności od koloru rozstajnego pola skręca w prawo lub w lewo, potem zmienia kolor pola na przeciwny i rusza w dalszą drogę.

Ta mrówka ma jednak przynajmniej jedną wadę: jest mało łamigłówkowa, bowiem cała zabawa sprowadza się do obserwacji śladu, który za sobą zostawia i zaskakujących regularności, pojawiających się po dłuższej wędrówce. Bardziej „zmyślne” są niektóre jej koleżanki, na przykład mrówka W.

Dlaczego W.? Z kilku „pierwszolitero-wych" powodów: mrówka musi dotrzeć Wszędzie, czyli do Wszystkich Węzłów sied, po której się porusza oraz Wrócić do punktu Wyjścia. Sieć jest regularna, kwadratowa, a więc przypomina pokratkowaną kartkę, a dodatkowa bardzo istotna zasada wędrówki brzmi: do każdego węzła, czyli skrzyżowania, mrówka powinna dotrzeć tylko raz. Z reguły do obejścia jest prostokątny fragment sieci. Wyznaczenie trasy wędrówki to zadanie trywialne (jeżeli w ogóle możliwe), ale do czasu. Sprawa się komplikuje, gdy pojawiają się dodatkowe warunki albo przeszkody na trasie. Zacznijmy od warunków.

Na wstępie warto zauważyć, że nie każdy fragment sieci o wymiarach mxn rzędów uda się mrówce W obejść. Jeśli m i n są nieparzyste, to z wędrówki będą nici, co nietrudno sprawdzić i udowodnić, na przykład na najmniejszym fragmencie S x 3. Możliwe są wówczas tylko trzy całkowicie różne trasy wiodące przez wszystkie skrzyżowania (rys. 1 a), ale żadna nie jest okrężna. I być nie może, jeśli bowiem oznaczymy skrzyżowania jak szachownicę (rys. 1 b), to zauważymy, że

kolory kolejnych nieparzystych i parzystych pól na trasie są różne, a zatem start i meta nie mogą być tym samym polem, bo wówczas pole to byłoby równocześnie pierwszym i dziesiątym.

Przyglądając się minitrasom na rys. 1a łatwo wpaść na pomysł warunku utrudniającego życie mrówce. Liczba zakrętów może być różna, a więc postawmy przed mrówką dwa zadania ekstremalne: w pierwszym powinna zakręcać jak najmniej razy, w drugim jak najwięcej.

Ustalenie minimum wydaje się prostsze. Gdyby w jakimś rzędzie nie pojawił się żaden zakręt, to przez każde skrzyżowanie w tym rzędzie musiałby przechodzić odcinek drogi do tego rzędu prostopadły, zakończony, rzecz jasna, dwoma zakrętami. Stąd wniosek, że albo w każdym wierszu, albo w każdej kolumnie muszą być co najmniej dwa zakręty. W przypadku sieci mxn minimalna liczba zakrętów powinna więc być równa mniejszej z dwu wartości - 2m lub 2n. Tak jest w przypadku parzystych m i n. Jeśli jednak mniejsza z tych wartości, na przykład n, będzie nieparzysta, to zejście z liczbą zakrętów poniżej 2m okaże się niemożliwe. Dlaczego? Oto zagadka. Rekapitulując: odpowiedzią pozostaje dwukrotna wartość parzystego wymiaru, a jeśli oba są parzyste - to mniejszego.

Dla sieci o konkretnych wymiarach, gdy m i n nie przekraczają 10, można wyznaczyć kilka lub kilkanaście całkowicie różnych, najmniej „zakręconych” tras. Niektóre z nich

■■■■■■■■■

rys. 1a

rys. 1b

"WIEDZA I ŻYCIE

CZERWIEC 2008

rys. 2

mają charakterystyczne kształty i są często symetryczne, np. przypominają grzebień (rys. 2). Rysowanie takich tras na sieci 8x8 jest łamigłówką znaną od dawna w wersji szachownicowej z Wieżą (sic!) w roli mrówki W. Przy dodatkowych warunkach bywa to nieproste. Proszę spróbować oznaczyć dwie takie trasy (a i b) z 16 zakrętami na rys. 3. Warunki dodatkowe mają w obu przypadkach postać graficzną:

(a)    sieć jest przerwana w dwóch miejscach,

(b)    w Wiśniowym Węźle mrówka powinna zakręcić.

Pora na trasy maksymalnie „zakręcone"; to określenie oznacza również, że ich szukanie nie jest takie łatwe. Nazwijmy węzeł, w którym trasa nie skręca, prostownikiem i zacznijmy wędrówkę równocześnie w dwu kierunkach od narożnego pola.

Z dwóch węzłów sąsiadujących z narożnym przynajmniej jeden musi być prostownikiem, bo w przeciwnym wypadku trasa natychmiast zostałaby zamknięta (rys. 4a), co odpowiadałoby sieci 2x2. Załóżmy, że prostownikiem jest węzeł w kolumnie (rys. 4b) oraz że więcej prostowników nie ma i kontynuujmy wędrówkę, najpierw przy lewym brzegu, zaliczając kolejno b3 i b4, a następnie a4 (na c4 skręcić nie można, bo wówczas a4 zostałby poza trasą). Podobnie łamana będzie

przebiegać wzdłuż dolnej krawędzi: b1-b2--c2<1-d1-d2... (rys. 4c). Z rysunku widać, że gdzieś na drodze powinien się znaleźć fragment c4-c3-d3, który jest taki sam, jak narożny, a w związku z tym jeden z węzłów, c4 lub d3, musi stać się prostownikiem.

Wędrując dalej w taki sposób - równocześnie w dwie strony kolejno różnymi fragmentami, z których każdy nowy zaczyna się od narożnika z prostownikiem - można tworzyć najbardziej zakręcone trasy dla dowolnie dużych sieci. Niewielkie problemy będą się pojawiać tylko przy zamykaniu dróg. Korzystając z opisanej me

tody, można określić maksymalną liczbę zakrętów dla sieci o konkretnych wymiarach. Na przykład z rys. 4c wynika, że w narożnym fragmencie obejmującym 16 węzłów znajdą się przynajmniej 2 prostowniki, a więc zakrętów będzie co najwyżej 14, zatem w sieci 8x8, złożonej z czterech takich fragmentów, zakrętów nie może być więcej niż 56 (rys. 5).

rys. 4a

rys. 4b

rys. 4c

Nie jest znany ogólny wzór na maksymalną liczbę zakrętów trasy mrówki W. w sieci mxn. Przed pięciu laty kanadyjski matematyk Richard Guy podał dwa wzory dla sieci w kształcie kwadratu 2nx2n. Dla n parzystych z = 4n² - 2n; dla n nieparzystych z = 4n² - 2n - 2.

Pełna trasa mrówki W. tworzy wielokąt, którego długość obwodu równa jest co do wartości liczbie węzłów i nie zależy od kształtu trasy. To oczywiste, bo każdemu węzłowi odpowiada jeden wychodzący z niego odcinek o jednostkowej długości. Nie jest już jednak takie oczywiste, że pole tego pokrętnego wielokąta również nie zależy od kształtu trasy i zawsze wynosi mn/2-1. Zauważmy, że jego szerokość nie może być większa od jednostkowej, czyli równej odległości między sąsiednimi węzłami. Inaczej mówiąc, wielokąt ten nigdzie nie obejmie kwadratu 2x2 utworzonego z czterech jednostkowych kwadratów, będących jakby oczkami sieci, bo gdyby tak było, to węzeł w środku kwadratu pozostałby poza trasą. Czy na tej podstawie uda się Państwu wyprowadzić powyższy wzór?

I na zakończenie jeszcze jeden problem: czy jest możliwe, aby dokładnie połowa trasy mrówki W. w sieci 8x8 przebiegała w kolumnach, a druga połowa oczywiście w wierszach?

ROZWIĄZANIE KONKURSU GOMOKU Z „WiŻ" 4/2008

Zadanie 1. Zwycięstwo zapewnia ruch na d6, a następnie d4, tworzący widełki (rys. 6).

Zadanie 2. Dobrym atakiem wydaje się c4, po którym grożą dwa ruchy, każdy prowadzący do widełek 4-3: c6 i c7. Jednakże na c4 białe mają znakomitą odpowiedź-kontratak neutralizujący oba zagrożenia: c3. Zwycięstwo gwarantuje czarnym ruch c8, a następnie (po najlepszej obronie białych) d9 (rys. 7).

Ze względu na niezbyt ścisłe sformułowanie zasad drugiego zadania (przy najlepszej obronie białych utworzenie czarnej piątki będzie wymagało wyjścia jednym pionkiem poza diagram) laureatów wyłoniono spośród wszystkich, którzy poprawnie rozwiązali pierwsze zadanie. Gry Pentago (ufundowane przez firmę Logorajd) otrzymują: Zuzanna Lewicka z Sulnówka, Lucja Majczak z Krakowa, Bartosz Zmuda z Ryk.

rys. 6

rys. 7

czerwiec 2008 WIEDZA I ŻYCIE"

&

74