Afiliacja: Wydział Matematyki Stosowanej, Akademia Górniczo-Hutnicza w Krakowie
W niniejszym artykule zajmiemy się pewną łamigłówką – należy zawiesić obrazek na \(n\) gwoździach w taki sposób, aby po wyjęciu choć jednego gwoździa obrazek spadł.
Nawet dla \(n=2\) zadanie nie jest trywialne. Na rysunku 1 zilustrowany jest sposób zawieszenia, który nie jest rozwiązaniem: o ile wyjęcie prawego gwoździa faktycznie skutkuje upadkiem obrazka, to po wyjęciu lewego ramka wciąż będzie wisiała na ścianie. Zachęcamy Czytelnika, by przed przystąpieniem do dalszej lektury spróbował sam rozwikłać ten przypadek (a może również \(n=3\)?). By nie psuć zabawy, ilustrację jednego z możliwych rozwiązań zamieściliśmy dopiero na następnej stronie.
Rys. 1
Przedstawimy teraz notację pozwalającą łatwo opisywać różne sposoby wieszania obrazków. Wyobraźmy sobie, że prowadzimy linkę między gwoździami od lewego punktu zaczepienia do prawego. Aby oznaczyć przeprowadzenie nitki w prawo nad \(i\)-tym gwoździem, będziemy wykorzystywać symbol \(x_i.\) Jak się zaraz okaże, przeprowadzenie nitki w lewo (nad \(i\)-tym gwoździem) rozsądnie jest oznaczyć przez \(x_i^{-1}.\) Nie będziemy odnotowywać przeprowadzania nitki pod gwoździami. Dla przykładu, przedstawiony na rysunku 1 sposób zawieszenia odpowiada napisowi \(x_1x_2x_1^{-1}.\)
Zauważmy od razu, że przeprowadzenie nitki najpierw w jednym, a bezpośrednio po tym w drugim kierunku nad jakimś gwoździem niczego nie zmienia w sposobie zawieszenia – po naciągnięciu nitki ta operacja przestaje być widoczna. Odpowiada to swoistemu „prawu skracania”: z uzyskanego napisu możemy usunąć wszelkie wystąpienia \(x_i x_i^{-1},\) jak i \(x_i^{-1} x_i.\) Przy jakich napisach możemy zaś spodziewać się upadku obrazka? Takich, dla których po opisanej operacji skracania nic nie zostaje – pusty napis odpowiada sytuacji, w której nitka znajduje się cały czas pod gwoździami, więc obrazek niechybnie wyląduje na podłodze. Pozostaje rozstrzygnąć, czemu odpowiada operacja usuwania \(i\)-tego gwoździa. Nie jest to trudne, wystarczy pozbyć się z napisu wszystkich wystąpień symbolu \(x_i\) (i jego odwrotności).
Powróćmy do przykładu z rysunku 1. Czemu odpowiada usunięcie drugiego gwoździa? Należy z napisu \(x_1x_2x_1^{-1}\) usunąć \(x_2,\) otrzymując napis \(x_1 x_1^{-1},\) który po skróceniu staje się pusty – obrazek upada. Kiedy usuniemy drugi gwóźdź, musimy z napisu usunąć wszystkie wystąpienia \(x_1,\) zostając z samym \(x_2.\) Jest to niepusty napis, więc obrazek wciąż będzie wisiał.
Analiza ta pozwala nam już dość łatwo rozwiązać wyjściowe zadanie dla przypadku dwóch gwoździ. Wystarczy bowiem na końcu naszego napisu dopisać \(x_2^{-1}\) (tzn. rozważyć zawieszenie opisane przez \(x_1x_2x_1^{-1}x_2^{-1}\)). Wtedy usunięcie symboli \(x_2\) znów pozostawi nas z \(x_1x_1^{-1}=\emptyset,\) zaś usunięcie \(x_1\) da nam \(x_2x_2^{-1}=\emptyset,\) czyli obrazek upadnie również w tej sytuacji. Właśnie taki sposób zawieszenia został zilustrowany na następnej stronie. Ale jak można rozszerzyć to podejście na większą liczbę gwoździ?
W algebrze wyrażenie postaci \(x_1x_2x_1^{-1}x_2^{-1}\) nazywa się komutatorem i oznacza się je przez \([x_1,x_2].\) Operacji tej można poddać nie tylko symbole, lecz również większe napisy. W tym celu musimy jednak zdefiniować odwrotność napisu \(S,\) czyli napis \(S^{-1},\) który po doklejeniu do \(S\) i skróceniu da napis pusty. Nie jest to trudne – wystarczy ułożyć symbole wchodzące w skład \(S\) w przeciwnej kolejności, za każdym razem dopisując „odwrotność” tam, gdzie jej brakło, i zabierając tam, gdzie była. Dla przykładu, odwrotnością napisu \({S=x_1^{-1}x_2 x_3}\) jest \(S^{-1}=x_3^{-1}x_2^{-1} x_1,\) gdyż: \[x_1^{-1}x_2 \textcolor{var(--primary-color)}{x_3\ x_3^{-1}}x_2^{-1} x_1= x_1^{-1}\textcolor{var(--primary-color)}{x_2 x_2^{-1}} x_1= \textcolor{var(--primary-color)}{x_1^{-1} x_1}=\emptyset.\] Komutatorem napisów \(S\) i \(Q\) nazwiemy \({[S,Q]=S Q S^{-1} Q^{-1}}\) (umieszczanie napisów obok siebie odpowiada oczywiście tworzeniu z nich większego napisu).
Rozważmy teraz zdefiniowany rekurencyjnie ciąg napisów: \[\begin{aligned} S_2 & = [x_1, x_2] = x_1 x_2 x_1^{-1} x_2^{-1}, \\ S_3 & = [S_2, x_3] = S_2 x_3 S_2^{-1} x_3^{-1} \\ & = (x_1 x_2 x_1^{-1} x_2^{-1}) x_3 (x_1 x_2 x_1^{-1} x_2^{-1})^{-1} x_3^{-1} \\ & = x_1 x_2 x_1^{-1} x_2^{-1} x_3 x_2 x_1 x_2^{-1} x_1^{-1} x_3^{-1}, \\ & \vdots \\ S_n & = [S_{n-1}, x_n] = S_{n-1} x_nS_{n-1}^{-1} x_n^{-1}. \end{aligned}\]
Zauważmy, że napis \(S_n\) odpowiada szukanemu sposobowi zawieszenia obrazka na \(n\) gwoździach! Istotnie, jeśli z \(S_n=S_{n-1} x_n S_{n-1}^{-1} x_n^{-1}\) usuniemy \(x_n,\) zostaniemy z \(S_{n-1} S_{n-1}^{-1}=\emptyset.\) Jeśli zaś usuniemy z niego dowolne \(x_i,\) gdzie \(i<n,\) to usuniemy je z \(S_{n-1}.\) Możemy jednak indukcyjnie założyć, że napis \(S_{n-1}\) w związku z tym skraca się do napisu pustego, co zostawia nas z \(x_n x_n^{-1}=\emptyset.\)
Już dla \(n = 4\) długość rozwiązania jest horrendalna: \[\begin{aligned} S_4 = & \ x_1 x_2 x_1^{-1} x_2^{-1} x_3 x_2 x_1 x_2^{-1} x_1^{-1} x_3^{-1} x_4 \\& x_3 x_1 x_2 x_1^{-1} x_2^{-1} x_3^{-1} x_2 x_1 x_2^{-1} x_1^{-1} x_4^{-1}. \end{aligned}\]
Rozwiązanie to ma jednak jedną zasadniczą wadę – długość rozwiązań rośnie wykładniczo. Jeśli przez \(d_n\) oznaczymy długość napisu \(S_n,\) to spełniona jest rekurencja \(d_n=2d_{n-1}+2,\) co przy warunku \(d_2=4\) daje nietrudny do sprawdzenia jawny wzór \(d_n=2^n+2^{n-1}-2.\)
Sprytny podział gwoździ to połowa… sukcesu.
Rys. 2. Ilustracja rozwiązania dla \(n=2\)
Okazuje się, że możemy dokonać bardzo zgrabnej optymalizacji, osiągając złożoność wielomianową!
Wystarczy, że podejdziemy do sprawy choć odrobinę delikatniej, nie dokładając raz za razem po jednym gwoździu, a dzieląc zbiór gwoździ na coraz mniejsze połowy, które będą komutować ze sobą.
Zdefiniujmy w tym celu: \[\begin{aligned} E(i:i) & = x_i, \\ E(i:i+1) & = [x_i, x_{i+1}] \\ \end{aligned}\] i w ogólności: \[\begin{aligned} E(i:j) & = \left[E\left(i:\left\lfloor \frac{i+j}{2} \right\rfloor\right), E\left(\left\lfloor \frac{i+j}{2} \right\rfloor + 1:j\right)\right]. \end{aligned}\] Dla przykładu: \[\begin{aligned} E(1:4) & = [E(1:2), E(3:4)] \\ & = E(1:2) E(3:4) E(1:2)^{-1} E(3:4)^{-1} \\ & = (x_1 x_2 x_1^{-1} x_2^{-1})(x_3 x_4 x_3^{-1} x_4^{-1}) (x_2 x_1 x_2^{-1} x_1^{-1})(x_4 x_3 x_4^{-1} x_3^{-1}). \end{aligned}\] Tak zdefiniowane \(E(i:j)\) będzie rozwiązaniem dla gwoździ od \(i\) do \(j,\) pozwalając rozbić problem na mniejsze części. Aby się o tym przekonać, wystarczy przeprowadzić indukcję względem wartości różnicy \(j-i.\) Usunięcie \(x_s\) dla \({i\leq s\leq k},\) gdzie \(k=\lceil \frac{i+j}{2} \rceil,\) „anihiluje” nam \(E(i:k)\) na mocy założenia indukcyjnego i zostaje \(E(k+1:j)E(k+1:j)^{-1}=\emptyset.\) Rozumowanie jest analogiczne, gdy \(k+1\leq s\leq j.\)
Przyjrzyjmy się długości tak określonego rozwiązania. Dla uproszczenia przyjmijmy, że \(n\) jest potęgą dwójki. Jeśli \(\delta_m\) jest długością \(E(1:n),\) gdzie \(n=2^m,\) to spełniona jest zależność \(\delta_m=4 \delta_{m-1},\) co przy \(\delta_0=1\) daje nam po prostu \(\delta_m=4^m=n^2.\) Dla wartości \(n\) niebędących potęgami dwójki pozostaje prawdą, że długość napisu jest rzędu \(n^2.\)
Zagadka o wieszaniu obrazków jest świetnym przykładem na to, jak dobrze dobrany zapis matematyczny pozwala uprościć pozornie złożony problem kombinatoryczny do bardziej podstawowych, a przede wszystkim – czytelnych! zagadnień. Nada się ona również na efektowny pokaz matematyczny, jeżeli tylko zamiast na gwoździach, przeprowadzimy doświadczenie na wyciągniętych ramionach ochotników!
Tekst powstał na podstawie artykułu Picture-Hanging Puzzles, Erika Demaine’a, Martina Demaine’a, Yaira Minskiego, Josepha Mitchella, Ronalda Rivesta i Mihaia Patrascu.