Krasnoludy żyją w okolicy Zaczarowanej Góry, w której znajduje się jaskinia smoka. Raz do roku smok składa jedno Zaczarowane Jajo, którego skorupa jest wysoce cenioną przez każdego krasnoluda ozdobą. Aby je ukraść, Król zbiera drużynę, która udaje się na misję do jaskini Smoka. Po wielu latach Król, w obliczu nadchodzącej śmierci, postanowił rozdać drogocenne ozdoby swoim najbardziej zasłużonym wojownikom. Jaj nie można jednak dzielić, bo po stłuczeniu tracą swą wartość. W jaki sposób władca powinien rozdzielić jaja między wojowników?
Król był sprawiedliwym władcą i dlatego najpierw postanowił ocenić zasługi każdego wojownika.
Przejrzał swoje zapiski i za każdą wyprawę, w której
Pierwszy (zły) pomysł Króla.
No dobrze, wiadomo, że wojownik, którego udział jest równy 3,6 jaja, musi dostać ich przynajmniej 3. Odłożę dla każdego wojownika po części całkowitej jego udziału, a jutro zastanowię się, co zrobić z resztą. Już dość się dzisiaj namęczyłem. Zadowolony Król poszedł spać, a następnego dnia pod prysznicem (pod którym zawsze przychodzą do głowy najlepsze pomysły) doznał olśnienia. Wiem! Dam pozostałe jaja tym wojownikom, których ułamkowe części ich udziałów są największe! Oni są teraz najbardziej poszkodowani! W ten sposób sprawiedliwie zaokrąglę udziały i wszyscy wojownicy będą zadowoleni!
Władca ogłosił swoją decyzję podczas uroczystej kolacji. Niestety wojownicy nie byli zachwyceni. Okazało się, że uczestnikami pierwszych trzech wypraw byli dwaj doświadczeni wojownicy, Alojzy i Bonifacy. Należało im się zatem po 1,5 jaja. W kolejnych pięciu wyprawach udział brała natomiast trójka młodych poszukiwaczy przygód: Cecyl, Dorian i Eugeniusz. Należało im się zatem po 1,(6) jaja. W ogólnym rozrachunku, rozdzielając osiem jaj z tych wypraw, Król dał po jednym każdemu z wojowników, a pozostałe trzy rozdał krasnoludom z największą resztą, czyli Cecylowi, Dorianowi i Eugeniuszowi. Alojzy i Bonifacy zaczęli protestować: przecież wspólnie zdobyli trzy jaja, a król dał im łącznie tylko dwa! Król zrozumiał, że jeśli chce uniknąć buntu części swoich wojowników, musi znaleźć lepszy sposób na podział łupu.
Jak uniknąć buntu?
Król myślał intensywnie przez kolejny tydzień, codziennie przez pół godziny. Czy w ogóle da się tak zaokrąglić udziały krasnoludów, aby każda grupa dostała przynajmniej tyle jaj, ile sama przyniosła, czyli tyle, ile było wypraw złożonych tylko z wojowników tej grupy?
Szukając w swoim pomyśle źródła konfliktu, władca zauważył pewną zależność. Jeżeli każdy krasnolud dostanie tylko jaja pochodzące z wypraw, w których brał udział, to nigdy nie nastąpi sytuacja, w której członkowie pewnej grupy dostaną kolektywnie mniej, niż sami wypracowali. Czy jednak da się znaleźć takie dopasowanie jaj do uczestników wypraw, aby każdy dostał swój udział zaokrąglony do liczby całkowitej?
Jestem na to za stary. Niech sami sobie radzą – pomyślał król. Rozłożył wszystkie jaja na stole i przy każdym umieścił tabliczkę z informacją o tym, jacy wojownicy zdobyli to jajo. Następnie zwołał wszystkich krasnoludów i rzekł:
Wojownicy! Bierzcie na zmianę po jednym jaju, przy którym widnieje wasze imię, aż nie uzyskacie części całkowitej swojego udziału! Jeżeli nie będzie wolnego jaja z waszym imieniem, to spróbujcie się wymieniać: poproście pewnego współtowarzysza waszej wyprawy, aby oddał wasze wspólne jajo, a sam wziął wolne ze stołu. Jeżeli takiego nie będzie, to niech poprosi kolejnego o jajo i tak dalej – ktoś wreszcie powinien móc wziąć jajo ze stołu.
Krasnoludy szamotały się trochę, ale już po kwadransie każdy krasnolud miał tyle jaj, ile powinien mieć!
Czy król miał szczęście? Okazuje się, że nie! Powyższa procedura zawsze przydzieli krasnoludom pożądaną liczbę jaj!
Aby to pokazać, załóżmy nie wprost, że jest pewien krasnolud, powiedzmy Eugeniusz, który nie ma jeszcze części całkowitej swojego udziału i nie może już wziąć żadnego jaja ze stołu ani się powymieniać, aby je dostać.
Niech
Na pewno mają oni mniej jaj niż wynosi suma ich udziałów, bo wszyscy mają nie więcej niż swoje udziały, a Eugeniusz ma mniej; ich łączny udział w wyprawie
to więcZ drugiej strony, jeżeli pewien krasnolud miałby jajo, w którego zdobyciu uczestniczył ktoś z
to sam też należałby do Wynika z tego, że wszystkie jaja z wypraw krasnoludów z M są w ich posiadaniu:
Obie nierówności prowadzą do sprzeczności, z czego wynika, że na koniec procedury wszyscy muszą mieć już części całkowite swoich udziałów.
Co zrobić z pozostałymi jajami?
Krasnoludy, których udział był całkowity, miały już cały swój udział. Pozostałe jednak wciąż liczyły na dodatkowe jajo. Skoro wcześniejsza metoda okazała się tak skuteczna, ucieszony król postanowił ją kontynuować:
Poddani! Ustawcie się w kolejce zgodnie z tym, ile jeszcze Wam brakuje do całego udziału (czyli w kolejności największych części ułamkowych), i niech każdy spróbuje tak jak poprzednio wziąć jedno dodatkowe jajo.
Gdy krasnoludy ustawiły się zgodnie z tą kolejnością (remisy były rozstrzygane osobistymi preferencjami Króla) i zaczęły brać jaja, i się wymieniać, okazało się, że udało się rozdzielić wszystkie pozostałe jaja pomiędzy wojowników!
Ponownie okazuje się, że taki obrót spraw nie był dziełem przypadku, a powyższa procedura zawsze rozdystrybuuje wszystkie jaja pomiędzy wojowników.
Aby to pokazać, załóżmy nie wprost, że
na koniec procedury zostały jaja, których żaden krasnolud, który nie ma jeszcze całego swojego udziału, nie mógł wziąć w swojej kolejce, a więc tym bardziej na koniec procedury.
Niech
Na pewno mają oni nie mniej jaj niż suma ich udziałów. Ich udział w wyprawie
to więcZ drugiej strony, każde jajo, w zdobyciu którego uczestniczył ktoś spoza
musi być wzięte przez krasnoluda spoza W przeciwnym razie ktoś spoza mógłby się wymienić z kimś z aby zostało mniej jaj. Zatem krasnoludy z posiadają wyłącznie jaja z wypraw, do których należały tylko krasnoludy z Część z tych jaj jest jeszcze niewzięta, gdyż zostały wolne jaja, więc takich jaj jest więcej niż :
Obie nierówności prowadzą do sprzeczności. Zatem na koniec procedury wszystkie jaja będą rozdane!
Coś mi to przypomina…
Królowi udało się wymyślić, jak podzielić jaja, ale czy rozwiązania jego problemu nie dało się już znaleźć w przepastnej królewskiej bibliotece?
Jaja to miejsca w parlamencie?
Bardzo podobnym problemem do naszego wydaje się przydział miejsc w parlamencie. W tym problemie daną mamy liczbę miejsc
Metoda wymyślona przez króla pod prysznicem odpowiada metodzie największych reszt: przydzielamy wszystkim partiom po
Jaja to wypłata w grze koalicyjnej?
Bardziej adekwatnym modelem wydają się gry koalicyjne. Gra koalicyjna to para
Jeżeli potraktujemy krasnoludów jako graczy, to za wartość koalicji
Jaja to wierzchołki w grafie?
Najbardziej przydatne okazuje się spojrzenie na nasz problem jako na graf dwudzielny: krasnoludy będą wierzchołkami po lewej, a jaja – po prawej stronie.
Krawędziami łączymy teraz każde jajo z krasnoludami, którzy uczestniczyli w jego zdobyciu.
Użyjemy pojęcia skojarzenia – jest to podzbiór krawędzi, w których każdy wierzchołek jest końcem nie więcej niż jednej krawędzi; wierzchołki, które są końcami, nazywamy skojarzonymi.
Powielmy wierzchołek każdego krasnoluda
Podążając za mądrością króla, najpierw przydzielmy części całkowite. Zakryjmy po jednym wierzchołku każdego krasnoluda i znajdźmy skojarzenie, w którym to wszystkie wierzchołki z lewej są skojarzone. Korzystając z Twierdzenia Halla, możemy wykazać (podobnie jak w naszym dowodzie), że zawsze jest to możliwe. Następnie po kolei odkrywamy po jednym wierzchołku i, jeżeli się da, powiększamy skojarzenie. Znowu można wykazać, że w ten sposób skojarzymy wszystkie jaja.
A jak te skojarzenia znaleźć? Załóżmy, że po pewnej liczbie kroków mamy już pewne skojarzenie, czyli przyporządkowanie jaj. Aby je powiększyć, możemy znaleźć ścieżkę powiększającą, czyli ścieżkę, która zaczyna się i kończy na wierzchołku nieskojarzonym i w której na zmianę mamy krawędź ze skojarzenia i nie (przykład można zobaczyć na marginesie). Zamienienie krawędzi ze skojarzenia na pozostałe ze ścieżki powiększa skojarzenie o jedną krawędź. Twierdzenie Berge’a mówi, że skojarzenie jest maksymalne wtedy i tylko wtedy, gdy nie istnieje względem niego żadna ścieżka powiększająca, więc jeżeli skojarzenie nie jest jeszcze maksymalne, to na pewno nam się uda znaleźć taką ścieżkę. A czym są ścieżki powiększające w naszej procedurze? No tak, to system zamian wymyślony przez króla. Trzeba przyznać, że nieźle to król wymyślił…