Twierdzenie o naszyjniku

Uczciwi złodzieje powinni umieć się dzielić. Oczywiście, dzielić się łupami z innymi uczciwymi złodziejami, którzy pomagali w dokonaniu kradzieży. Można sobie wyobrazić, że taka uczciwość powoduje czasem pewne trudności, gdyż niektóre precjoza mogą być nieskore do podziału. Dla przykładu...

...wyobraźmy sobie, że dwoje uczciwych złodziei (powiedzmy, Bonnie i Clyde) skradło naszyjnik wysadzany diamentami i rubinami i chcą między sobą po równo rozdzielić zawarte w nim szlachetne kamienie. Oczywiście, aby to było możliwe, liczba diamentów oraz liczba rubinów na naszyjniku muszą być parzyste. Załóżmy dodatkowo, że złodzieje - ceniący sztukę i misterną konstrukcję naszyjnika - chcą go przeciąć w jak najmniejszej liczbie miejsc, tak aby powstałe w ten sposób fragmenty mogli między siebie rozdzielić w sposób sprawiedliwy względem liczby diamentów oraz rubinów (zapięcie naszyjnika nie musi być zamknięte). Rysunek 1 pokazuje sposób podziału naszyjnika z 10 diamentami i 4 rubinami przy użyciu dwóch cięć w taki sposób, by każdy złodziej otrzymał 5 diamentów i 2 rubiny. Oczywiście, mniejsza liczba cięć nie jest możliwa. Może jednak istnieje inny diamentowo-rubinowy naszyjnik, którego nie da się sprawiedliwie podzielić przy użyciu dwóch cięć? Okazuje się, że nie, co nietrudno jest udowodnić.

Rozważmy naszyjnik z $|2k$ diamentami i $|2l$ rubinami. Dla $|i⩽ k+ l + 1$ rozważmy podział $Π , i$ w którym kamienie o numerach $|i,i +1,...,i + k +l −1$ przygarnia Bonnie, a pozostałe Clyde. Oczywiście, każdy taki podział jest możliwy do zrealizowania przy użyciu dwóch cięć. Załóżmy, że przy podziale $Π 1$ Bonnie dostał $d$ diamentów i bez straty ogólności przyjmijmy $d ⩽ k.$ Wówczas Clyde musi mieć $|2k− d$ diamentów, zatem tyle samo ma Bonnie przy podziale $Π k+l+1.$ Ponadto, gdy zmieniamy podział z $Π i$ na $Π i+1,$ liczba diamentów przyznanych Bonniemu zmienia się o co najwyżej 1. W tej sytuacji, zmieniając się od $|d⩽ k$ (przy $|Π 1$ ) do $|2k− d ⩾ k$ (przy $Π k+l+1$ ), liczba diamentów w posiadaniu Bonniego przy pewnym podziale będzie musiała wynosić $|k.$ Oczywiście, wówczas będzie on mieć $|l$ rubinów (gdyż zawsze otrzymuje $k + l$ kamieni), a zatem uzasadniliśmy istnienie sprawiedliwego podziału uzyskiwanego przy użyciu dwóch cięć.

Powstaje naturalne pytanie: co mogą zrobić złodzieje, jeśli rodzajów kamieni jest więcej? Rysunek 2 przedstawia naszyjnik wysadzany diamentami, rubinami i szmaragdami, którego nie da się sprawiedliwie podzielić, używając dwóch cięć, choć jest to możliwe przy użyciu trzech cięć. Czy zatem w przypadku 3 rodzajów kamieni zawsze wystarczą 3 cięcia? A jeśli tak, to czy przy naszyjniku z $n$ różnymi rodzajami kamieni zawsze możemy wykonać tylko $|n$ cięć, aby uzyskać sprawiedliwy podział? Twierdzącej odpowiedzi na to pytanie udzielili Noga Alon i Douglas West (The Borsuk-Ulam theorem and bisection of necklaces, Proceedings of the American Mathematical Society, 1986). Przedstawione przez nich rozumowanie jest niezwykle piękne, między innymi dlatego, że opiera się natwierdzeniu Borsuka-Ulama, kojarzonym z topologią, a nie z problemami natury tak dyskretnej, jak podział łupów. Twierdzenie to brzmi następująco.

Twierdzenie. Niech $n |S$ będzie $n$ -wymiarową sferą jednostkową, tzn.

n n+1 2 2 S = {(x1,...,xn+1)∈ R x 1 + ...+x n+1 = 1}

i niech $n n | f S R$ będzie dowolną funkcją ciągłą. Wówczas istnieje punkt $|x∈ Sn,$ dla którego $| f(x) = f(−x).$

Więcej o twierdzeniu Borsuka-Ulama można przeczytać w artykule Michała Miśkiewicza w Delcie 09/2018.

Przyjrzyjmy się, jak przedstawiony wynik "pracuje" w rozważanym zagadnieniu. Dla uproszczenia przyjmijmy, że mamy do czynienia z trzema rodzajami kamieni, dowód w ogólnym przypadku jest w pełni analogiczny. Rozważmy naszyjnik z $|2k$ diamentami, $|2l$ rubinami i $|2m$ szmaragdami. Załóżmy, że naszyjnik ma długość $2(k +l +m),$ a po jego rozprostowaniu $|i$ -ty kamień znajduje się w odległości $|(2i− 1)/2$ od górnego zapięcia. Dla ułatwienia opisu niech $|Ai$ będzie punktem na naszyjniku w odległości $i$ od górnego zapięcia (tzn. $i$ -ty kamień znajduje się w środku odcinka $|A A i−1 i$ ).

Wyobraźmy sobie, że dla każdego $i ⩽2(k + l + m)$ "rozsmarowujemy" $i$ -ty kamień równomiernie po całym odcinku $A A . i− 1 i$ Dopuszczamy w ten sposób niecałkowitoliczbowe podziały naszych skarbów (tzn. można, na przykład, przeciąć diamentowy odcinek w połowie). Zastanówmy się, w jaki sposób można matematycznie opisać podział tego naszyjnika na cztery części, rozdzielone między dwóch złodziei. Po pierwsze, musimy określić punkty cięcia. Są one jednoznacznie wyznaczone przez długości kolejnych fragmentów naszyjnika, czyli cztery dodatnie liczby rzeczywiste, sumujące się do $|2(k+ l + m).$ Dla wygody podzielmy je przez $2(k + l + m),$ otrzymując dodatnie liczby $d ,d ,d ,d , 1 2 3 4$ sumujące się do 1. Następnie musimy rozdzielić tak otrzymane części między złodziei. W tym celu każdej części możemy przyporządkować liczbę $|±1,$ w zależności od tego, któremu rabusiowi chcemy ją wręczyć (powiedzmy, 1 dla Bonniego i $|−1$ dla Clyde). Niech $|σ i$ będzie znakiem przynależności $i$ -tej części. Wówczas czwórka $√ -- √ --- √ --- √ --- |(σ1 d1,σ2 d2,σ3 d3,σ4 d4)$ jest punktem na sferze $3 S .$ Z drugiej strony, każdy punkt $|x = (x1,x2,x3,x4)∈ S3$ definiuje podział naszyjnika poprzez wzięcie $|di = x2i$ oraz $σi = sgn(xi).$

Widzimy już, że twierdzenie Borsuka-Ulama ma coraz większą szansę okazać się pomocne. Aby z niego skorzystać, musimy jeszcze określić funkcję ciągłą z $S3$ w $|R3,$ w jakiś sposób związaną z naszym podziałem łupów. Naturalnym kandydatem jest funkcja $3 3 |F S R$ określona "wzorem"

F(x) = suma długości (diamentowych, rubinowych, szmaragdowych) fragment ów naszyjnika, przypad łych Bonniemu przy podziale zdefiniowanym przez x.

Rozważana funkcja jest ciągła dzięki temu, że "rozsmarowaliśmy" wcześniej nasze kamienie. Na mocy twierdzenia Borsuka-Ulama istnieje zatem $|x∈ S3,$ dla którego $F(x) = F(− x).$ Zauważmy jednak, że $|F(−x)$ określa sumy odpowiednich fragmentów przynależnych Clyde przy podziale zdefiniowanym przez $x.$ Istnieje zatem podział naszyjnika przy użyciu trzech cięć w taki sposób, że każde ze złodziei otrzyma taką samą sumaryczną długość fragmentów poszczególnych rodzajów.

Pozostaje nam teraz wrócić z "uciąglonej" wersji problemu do twardej rzeczywistości diamentów twardych jak diamenty, niemożliwych do "rozsmarowywania" na naszyjniku. Aby zakończyć dowód, wystarczy uzasadnić, że otrzymane w poprzednim akapicie punkty cięcia możemy przesunąć (nie zmieniając sprawiedliwości podziału) tak, aby wypadły w punktach $Ai.$ Nie jest to jednak trudne. Rozważmy wszystkie punkty cięcia, które wypadły wewnątrz pewnego diamentowego odcinka o końcach w kolejnych punktach $|Ai.$ Jeśli fragmenty po obu stronach cięcia należą do jednego złodzieja, to, oczywiście, bez uszczerbku sprawiedliwości możemy przesunąć cięcie do najbliższego punktu $Ai.$ Wszystkie pozostałe spośród rozważanych punktów cięcia przesuńmy "na korzyść" Bonniego. Wówczas Bonnie zyska "diamentową" długość będącą pewną liczbą całkowitą $a$ (gdyż suma "ułamkowych" diamentowych fragmentów Clyde musiała być całkowita). Wystarczy zatem, że Bonnie odda teraz $|a$ diamentów poprzez odpowiednie przesunięcie o 1 pewnych $|a$ punktów cięcia. To samo można zrobić dla pozostałych rodzajów kamieni, otrzymując w ten sposób "dyskretny", sprawiedliwy podział naszyjnika.

Kolejnym rozszerzeniem naszyjnikowej zagwozdki jest wzięcie pod uwagę większej liczby złodziei. Jaka jest zatem najmniejsza możliwa liczba cięć potrzebnych do podziału naszyjnika z $n$ rodzajami kamieni między $|m$ złodziei (zakładając, że jest to możliwe)? Odpowiedź jest znana, zachęcam jednak Czytelnika do próby samodzielnego sformułowania hipotezy na ten temat.