Dodaj do ulubionych

20 piratów z Karaibów

01.12.04, 04:33
Zainspirowany pewnym pomysłem pewnego geniusza łamigłówek przedstawiam
następującą zagadkę:

Dwudziestu piratów, w tym kapitan Jack Sparrow, przybyło z łupami na swoją
wyspę-kryjówkę. Przenieśli ze statku skrzynię ze zrabowanymi skarbami, wsród
których były diamenty, złoto, perły, drogocenne tkaniny i inne rzeczy, po czym
wysypali jej zawartość na olbrzymią ławę, by podzielić łupy między sobą.
Piraci uzgodnili i stanowczo stwierdzili, że wszystkie kosztowności muszą
podzielić między siebie po "równo", czyli każdy z nich musi być absolutnie
zadowolony z przydzielonej mu części skarbów, bo inaczej dojdzie do
bratobójczych walk. Problemem było jednak to, że dla każdego z nich co innego
stanowiło 1/20 zagrabionych skarbów, bowiem każdy z dwudziestu piratów miał
inne upodobania. Jeden lubił diamenty i rubiny, inny wolał złoto jeszcze inny
preferował kaszmir i jedwab. Nie wchodziło więc w rachubę, żeby kapitan
Sparrow podzielił skarby na 20 części i każdą z nich obdarował jednego pirata
(w tym i siebie), bo wtedy na pewno znalazłby się choć jeden niezadowolony, a
to całkowicie dyskwalifikowałoby cały podział. Trzeba było wymyślić coś innego.

Jaki sposób podziału łupów, satysfakcjonujący każdego pirata, wymyślił kapitan
Jack Sparrow?

Jest to jedna z tzw. zagadek "z górnej półki", czyli tych najtrudniejszych,
dlatego tym mocniej będę dopingował i trzymał za wszystkich kciuki. Powodzenia!

CdM


PS. Wymyślony przez Jacka Sparrowa algorytm podziału łupów jest na tyle
uniwersalny, że daje się zastosować równie dobrze do 10, 40 czy 100 piratów.
Milczącym założeniem jest oczywiście to, że ilość skarbów jest dużo większa od
ilości kandydatów do obdzielenia, przy czym i tak każdy naszyjnik, bela
materiału, czy nawet pierścionek da się - w razie czego jakby co - podzielić
na mniejsze części.
Obserwuj wątek
    • andy._ Re: 20 piratów z Karaibów 01.12.04, 09:10
      Znam od dawna sposób podziału czegoś jednorodnego na N części i nawet zdarzało
      mi się stosować taki algorytm w praktyce. Dla N=2 znana jest reguła "jeden
      dzieli - drugi wybiera". Daje się ona w pewnym sensie uogólnić dla dowolnego N.
      Chętni siadają w kółko i ktoś wydziela 1/N-tą skarbu stając się jej
      potencjalnym właścicielem. Każdy kolejny w kółku może wydzieloną część
      zmniejszyć jeżeli uważa, że jest ona za duża i prawo do takiej części
      przechodzi na niego. Jeżeli po ostatnim wyborze/zmniejszeniu kolejka obiegnie
      kółko i nikt już 1/N-tej nie zmniejszy, to ten kto ostatni wybierał/zmniejszał
      zabiera swój przydział i zabawa zaczyna się od początku na N mniejszego o
      jeden. Powyższy sposób jest sprawiedliwy w tym sensie, że nikt nie może
      narzekać, bo jeżeli uważa ,że bieżąca 1/N-ta jest na duża to ma prawo do
      poprawki "w dół", a jeżeli uważa, że jest ona za mała to powinien się tylko
      cieszyć bo ktoś ją zabierze i w kolejnej rundzie nowa 1/N-ta będzie większa.
      Jedynym problemem może być niejednorodność skarbu, ale końcowe "milczące
      założenie" chyba sugeruje właśnie jednorodność.
      • Gość: taterki Re: 20 piratów z Karaibów IP: *.media4.pl 01.12.04, 21:59
        Bardzo ciekawy pomysł. Jednak tu się chyba nie sprawdzi.
        Otóż przy dwóch osobach sprawa jest prosta. Ale przy dwudziestu?
        Nie można wydzielić na początku 1/n skarbu bo:
        Wyobraźmy sobie taką sytuację:
        Pierwszy pirat (P1) wybiera połowę rubinów (plus coś tam innego) Rubinami są zainteresowani jeszcze np P2 i P3. Każdy z nich przepuści rubiny licząc, ze resztę dostanie właśnie on. Kiedy P1 zabierze połowę pozostali dwaj dostaną po 1/4. Z całą pewnością nie będą zadowoleni ;)

        Rozwiązaniem byłoby, zeby P1 wziął wszystkie rubiny, wtedy P2 zmniejszy do 1/2 a P3 do 1/3. Ale to prowadzi do sytuacji, ze P1 bierze cały (albo prawie cały) skarb i trzeba mocno pilnować ilu co dzieliło. Prostszą wersję tego przedstawię w osobnym poście.


        • Gość: taterki Re: 20 piratów z Karaibów IP: *.media4.pl 01.12.04, 22:30
          Jeszcze jedna uwaga. Pisałeś o jednorodności skarbu. Otóż wydaje mi się, ze jednorodne są tylko poszczególne asortymenty skarbu, a jako całośc skarb jednorodny nie jest. W związku z tym podział może zostać zablokowany przez dwóch piratów z których jeden będzie np. zmniejszał ilość złota a zwiększał rubinów a drugi odwrotnie.
            • Gość: taterki Re: 20 piratów z Karaibów IP: *.media4.pl 02.12.04, 00:06
              Zgoda. Ale znowu przy jednorodnym skarbie. Zauważ, że "wartość" części jest inna dla każdego pirata.
              Weźmy taka sytuację
              P1,P2,P3
              Z - złoto, R - rubiny, S - Sukno
              Załóżmy, że "obiektywna" wartość Z=S=R
              P1 Z-1, R-1 S-0 (1 tzn całe)
              w kolejnych ruchach P1 - nic nie robi

              A więc albo P1 dostanie 2/3 skarbu, albo P2 ani P3 nie dostana ani kawałka S. A jeżeli im na tym akurat zależy?
              Bez zwiększania się chyba nie da...
              Pozdrawiam
      • andy._ Re: 20 piratów z Karaibów 01.12.04, 23:20
        Przy skarbie niejednorodnym podział na dwie osoby jest też nierozstrzygalny.
        Jeżeli mamy do podziału jedną żarówkę i jedną świetlówkę, to żaden algorytm nie
        zapewni zgodnego podziału jeśli obie osoby chcą tego samego. Pozostaje w takim
        przypadku np. losowanie.
    • Gość: taterki Re: 20 piratów z Karaibów IP: *.media4.pl 01.12.04, 22:21
      Jack Sparrow woła:
      Dzielimy złoto!
      Wokół stołu zostaja tylko zainteresowani złotem. Jack dzieli złoto na tyle części ilu jest chętnych.

      Podobnie postępuje z każdym kolejnym "asortymentem" skarbu.
      Z dużym prawdopodobieństwem powstanie sytuacja, że każdy dostanie po 1/20 każdego asortymentu. A później mogą dokonywać wymian.


      Jedno mnie martwi.
      cardemon napisał:
      "> Jest to jedna z tzw. zagadek "z górnej półki", czyli tych najtrudniejszych"
      Więc pewnie gdzieś jest hak którego nie znalazłem...

    • lapacz_w_zycie Re: 20 piratów z Karaibów 02.12.04, 00:36
      Na miejscu Jacka S. zrobiłbym tak:

      Podzielił skarb na możliwie małe części,
      powiedział, że cały skarb jest wart 1000 rubli transferowych
      i kazał każdemu z piratów przypisać do każdej z cząstek
      skarbu jej wartość w rublach transferowych
      (w razie potrzeby można użyć także kopiejek).
      Ważne jest, aby suma wartości przypisanych poszczególnym
      częściom skarbu przez każdego pirata wynosiła 1000 r.t.
      Każdy pirat powinien dostać gadżety warte (w jego mniemaniu)
      co najmniej 50 r.t. żeby czuł się usatysfakcjonowany.
      Następnie zebrawszy te deklaracje rozpoczął podział skarbu w ten sposób:
      wziął pierwszą z brzegu rzecz (belę jedwabiu na ten przykład) i sprawdził kto
      przypisał jej największą wartość, i przydzielił ją temu własnie towarzyszowi
      piratowi.
      Jeśli rzecz jest warta ponad 50 r.t. należy odkroic z niej
      odpowiednią część, tak, żeby jej wartość (tej pozostałej części)
      osiągęła 50 r.t. (pozwalają na to warunki zadania).
      Następnie wziął kolejną rzecz i przydzielił temu dla którego ona jest
      najwięcej warta, wyłączając tych którym skończyły się już fundusze,
      tzn. tych którzy już mają fanty warte 50 r.t.
      I tak do wyczerpania całego skarbu.
      Jeśli w wycenie fantów występowały jakiekowlwiek różnice pomiędzy
      piratami to łatwo dowieść, że po zaspokojeniu każdego tzn.
      przydzieleniu błyskotek za 50 r.t. coś jeszcze na kupce zostanie
      (im bardziej wyceny poszczególnych rzeczy będą zróżnicowane tym więcej).
      I właśnie dlatego chciałbym być kapitanem Jackiem S. (ps. Wróbel).

      lwz

      P.S. Oczywiście algorytm andy._'ego jest poprawny
      i wszelkie zgłaszane do niego wątpliwości są bezpodstawne,
      nie daje on jednak takich możliwości dla dzielącego
      (bo nie ma wyróżnionego dzielącego) jak przedstawiony powyżej.
      • Gość: taterki Re: 20 piratów z Karaibów IP: *.media4.pl 02.12.04, 01:55
        lapacz_w_zycie napisał:
        > Na miejscu Jacka S. zrobiłbym tak:

        zagmatwane i nie działa

        > coś jeszcze na kupce zostanie
        > (im bardziej wyceny poszczególnych rzeczy będą zróżnicowane tym więcej).
        > I właśnie dlatego chciałbym być kapitanem Jackiem S. (ps. Wróbel).

        To niezgodne z warunkami - maja podzielić na 20 - Jack nie może mieć więcej

        > P.S. Oczywiście algorytm andy._'ego jest poprawny
        > i wszelkie zgłaszane do niego wątpliwości są bezpodstawne,

        Algorytm ów bardzo mi sie podoba (bo do mnie piłeś) ale ze względu na niejednorodność skarbu wydaje sie nieprzydatny.

        Zauważ, że piraci mają być zadowoleni nie tylko w momencie odbioru swojej częsci - ale i po porównaniu swoich części z częściami innych.
        Jeżeli jest jakieś rozwiązanie inne niż przedstawiłem - to musi sie opierać na wagach, ale na razie czekam na krytykę "podziału na 20 cześci każdego rodzaju skarbu"
        Pozdrawiam
        • lapacz_w_zycie Re: 20 piratów z Karaibów 02.12.04, 13:11
          > zagmatwane i nie działa
          aha. a to przepraszam, miałem nadzieję,
          że przejrzyste i działające


          >To niezgodne z warunkami - maja podzielić na 20 - Jack nie może mieć więcej
          Ależ zgodne. Skarb jest podzielony na 20 części. Każdy z 19 piratów
          ma przed sobą dobra, które w jego mniemaniu stanowią dokładnie 1/20 skarbu
          więc to co zostało również musi być 1/20.
          Oczywiście można sobie też wyobrazić "sprawiedliwą" wersję tego rozwiązania
          w której Jacek S. też deklaruje ile są warte dla niego poszczególne
          przedmioty i na równych prawach uczestniczy w podziale,
          a do tego co zostanie stosujemy algorytm jeszcze raz.
          I po zastosowaniu tej metody aż do podziału wszystkich dóbr
          każdy będzie miał wrażenie, że jego część jest warta więcej,
          albo przynajmniej tyle samo co każda z pozostałych.
          Ale odnoszę wrażenie, że gdyby Jacek S. miał skołonność do takich rozwiązań nie
          byłby kapitanem.

          A trochę poważniej, to ja to widzę tak:
          warunkiem minimalnym poprawności rozwiązania
          jest to, żeby każdy z piratów znalazł się w posiadaniu
          części skarbu, której wartość ocenia na co najmniej 1/20
          wartości skarbu. Ten warunek spełniają wszystkie trzy (Twoje, andy._'ego i moje)
          przedstawione rozwiązania.

          Poza tym można się domyślać innych pożądanych cech rozwiązania np.
          - może powinno zapewniać, żeby każdy pirat dostał to na czym mu najbardziej
          zależy, to co najbardziej ceni?
          - może powinno minimalizować podziały w obrębie poszczególnych asortymentów
          (takie diamenty, dajmy na to, boleśnie tracą na wartości przy podziale)?
          - może powinno zapewniać każdemu z piratów wrażenie że wszyscy inni mają mniej
          atrakcyjną część skarbu?
          - może powinno być możliwie niewrażliwe na kolejność obdarowywania piratów, czy
          kolejność rozdziału poszczególnych dóbr?

          > Algorytm ów bardzo mi sie podoba (bo do mnie piłeś)
          > ale ze względu na niejednorodność skarbu wydaje sie nieprzydatny.
          nie widzę żadnej przeszkody w stosowaniu uogólnionego "jeden dzieli, drugi
          wybiera"
          dla dóbr podzielnych (nieskwantowanych). A takie założenie, że każdą rzecz
          można
          dowolnie podzielić mamy w zadaniu.


          > Zauważ, że piraci mają być zadowoleni nie tylko w momencie odbioru
          > swojej częsci - ale i po porównaniu swoich części z częściami innych.
          tu już wkraczamy na grunt psychologii.
          a co jeśli po podziale Brzuchaty Bo zapała chęcią posiadania szabli
          zobaczywszy jak dostojnie wygląda jego kompan Gadatliwy Gdan przypasawszy ją do
          boku?
          Odnoszę nieodparte wrażenie, że myśl zasady "trawnik sąsiada jest zawsze
          zieleńszy",
          po podziale wielu miałoby wrażenie że inni mają więcej.

          > ale na razie czekam na krytykę "podziału na 20 cześci każdego rodzaju skarbu"
          Ja to się do krytyki specjalnie nie palę.
          Jak już napisałem powyżej Twoje rozwiązanie spełnia warunek sprawidliwości
          jeśli rozumiemy je tak, że najpierw dzielimy każdy rodzaj łupu na 20 równych
          części
          i dajemy każdemu po jednej części każdego rodzaju (a potem ewentualnie
          zezwalamy na zamiany, ale po zamianach może się okazać, że ktoś w wyniku zamian
          (satysfakcjonujących obie zamieniające się strony) wszedł w posiadanie zbioru
          który
          komuś trzeciemu wydaje się przekraczać 1/20).
          Bo jeśli robimy to metodą najpierw dzielimy złoto między tych co chcą złoto,
          potem diamenty a potem kolejne dobra, to algorytm oczywiście nie zadziała,
          pokrzywdzeni będą Ci, którzy są zainteresowani rzeczami dzielonymi jako
          ostatnie.

          lwz
          • Gość: taterki Re: 20 piratów z Karaibów IP: *.internetdsl.tpnet.pl 02.12.04, 15:42
            lapacz_w_zycie napisał:

            > > zagmatwane i nie działa
            > aha. a to przepraszam, miałem nadzieję,
            > że przejrzyste i działające

            Bez urazy, sprawdziłem na jednym przykładzie, a że zagmatwane ;) to nie podaję bom coś mógł pomieszać

            > > Zauważ, że piraci mają być zadowoleni nie tylko w momencie odbioru
            > > swojej częsci - ale i po porównaniu swoich części z częściami innych.
            > tu już wkraczamy na grunt psychologii.
            > a co jeśli po podziale Brzuchaty Bo zapała chęcią posiadania szabli
            > zobaczywszy jak dostojnie wygląda jego kompan Gadatliwy Gdan przypasawszy ją > do boku?
            > Odnoszę nieodparte wrażenie, że myśl zasady "trawnik sąsiada jest zawsze
            > zieleńszy",
            > po podziale wielu miałoby wrażenie że inni mają więcej.

            Nie o zmianę opinii mi chodziło(bo faktycznie rozwaliłaby zadanie) a o to, że biorąc powiedzmy 1/10 (i nic więcej dla uproszczenia) złota pirat będzie zadowolony do czasu aż okaże się, inny dostał np 1/9 albo 1/10 i coś.

            Pozdrawiam
            • lapacz_w_zycie Re: 20 piratów z Karaibów 02.12.04, 16:42
              > Bez urazy, sprawdziłem na jednym przykładzie, a że zagmatwane ;) to nie ?
              > podaję bom coś mógł pomieszać

              Hmmm, ktoś powiedział, że sprawy należy upraszczać tak bardzo
              jak to tylko możliwe i ani odrobinę bardziej.
              Czasami zdarza się, że najprostsze rozwiązanie nie jest najlepsze,
              że poprawę osiąga się przez komplikację, jak na przykład
              w zadaniu o więźniach.

              > Nie o zmianę opinii mi chodziło(bo faktycznie rozwaliłaby zadanie)
              > a o to, że biorąc powiedzmy 1/10 (i nic więcej dla uproszczenia)
              > złota pirat będzie zadowolony do czasu aż okaże się,
              > inny dostał np 1/9 albo 1/10 i coś.
              Nie wiem czy takiej sytuacji da się w jakikolwiek rozsądny sposób
              uniknąć.
              Wyobraźmy sobie taką sytuację:
              Jest pirat Eustachy Uszko, który uważa dwa kolczyki z czarnymi perłami są
              niezykle cenne, każdy z nich stanowi wg. niego 1/15 skarbu.
              To przekonanie nie jest podzielane przez żadnego z pozostałych piratów,
              wszyscy pozostali uważają że każdy kolczyk stanowi jedynie 1/30
              skarbu. Oczywiście dobrze by było, żeby jeden kolczyk przypadł Eustachemu,
              powinien on być zadowolony, dostał 1/15 skarbu,
              mimo, że miał prawo tylko do 1/20. Ale ktoś, kto dostał drugi kolczyk będzie
              oczekiwał jakichś dodatkowych przedmiotów.
              Jeśli nie dostanie nic więcej będzie się czuł pokrzywdzony, bo wg. niego
              jego część stanowi 1/30 łupu czyli za mało, jeśli dostanie coś jeszcze
              pokrzywdzony będzie się czuł Eustachy bo ktoś będzie miał więcej od niego.

              Wydaje mi się że ten przykład pokazuje, że nie da się uniknąć sytuacji
              w której, piraci mając różne zestawy łupów będą jednocześnie przekonani,
              że żaden z pozostałych nie ma więcej.
              Wyjąwszy przypadek kiedy wszyscy będą mieli dokładnie takie same zestawy
              przedmiotów.
              Mam jednak wrażenie, że nie o to w tym zadaniu chodzi.
              Oczywiście mogę się mylić.

              lwz
              • Gość: taterki Re: 20 piratów z Karaibów IP: *.internetdsl.tpnet.pl 02.12.04, 17:32
                > Jest pirat Eustachy Uszko, który uważa dwa kolczyki z czarnymi perłami są
                > niezykle cenne, każdy z nich stanowi wg. niego 1/15 skarbu.
                > To przekonanie nie jest podzielane przez żadnego z pozostałych piratów,
                > wszyscy pozostali uważają że każdy kolczyk stanowi jedynie 1/30
                > skarbu. Oczywiście dobrze by było, żeby jeden kolczyk przypadł Eustachemu,
                > powinien on być zadowolony, dostał 1/15 skarbu,
                > mimo, że miał prawo tylko do 1/20. Ale ktoś, kto dostał drugi kolczyk będzie
                > oczekiwał jakichś dodatkowych przedmiotów.

                Nie ma takiego problemu - bo w/g warunków zadania każdy kolczyk można podzielić
                Problemem jest porównanie wartości kolczyka z wartością sukna.

                Zapraszam do rozważenia ważenia ;)
    • andy._ Re: 20 piratów z Karaibów 02.12.04, 10:23
      Algorytm, który podałem zadziała bez problemów dla jednorodnego skarbu.
      Dodatkowo wydaje mi się też, że uniemożliwia on zmowy uczestników podziału (czy
      to też jest warunkiem zadania?). Przy skarbie quasi-jednorodnym z jakim mamy do
      czynienia chyba trzeba sprecyzować założenia. Wyobraźmy sobie, że drobną część
      skarbu (wyrażnie mniejszą od 1/20-tej intuicyjnej czy rynkowej oceny) stanowi
      kupka diamentów. Jeżeli w grupie piratów znajdzie się wielbiciel tych kamieni,
      który będzie zadowolony tylko wtedy jeżeli dostanie wszystkie diamenty (i
      rezygnuje wspaniałomyślnie z innych łupów) a drugi pirat chce koniecznie po
      jednym kamyku każdego rodzaju i brakuje mu do kolekcji tylko diamentu, to jest
      to sytuacja nierozstrzygalna bo przechodzimy ze sfery wartości materialnych do
      sfery emocji, a wtedy każdy algorytm może się zakleszczyć.
    • Gość: taterki to może ważymy...? IP: *.internetdsl.tpnet.pl 02.12.04, 16:56
      Kapitan dzieli skarb na rodzaje.
      Każdy pirat przypisuje każdemu rodzajowi skarbu wagę (w/g swoich upodobań)
      Wagi przypisane przez każdego pirata muszą się sumować do tej samej liczby(np. do 100).
      Kapitan sumuje wagi dla danego rodzaju skarbu (np złoto), dzieli złoto na sumę wag dla złota i każdemu wydaje tyle złota ile mu przypada.
      Podobnie robi z każdym rodzajem skarbu.

      Ponieważ w przypadku takiego podziału warto obstawiać mniej "popularne" rodzaje skarbu - pozostaje do rozwiązania system przyznawania wag.
      Najpewniejszą metodą byłoby pozwolenie na zmiany wag po kolei aż do momentu, gdy nikt żadnej wagi w danej kolejce nie zmieni.
      Pozdrawiam
      • lapacz_w_zycie Re: to może ważymy...? 03.12.04, 06:24
        Ten algorytm prowadzi do rozwiązań, nazywanych suboptymalymi,
        czyli takich, dla których istnieją inne rozwiązania
        z których wszyscy byliby bardziej zadowoleni.
        Przykład:
        Piratów jest trzech. A skarb składa się z 10 Złotych
        monet, 10 Diamentów i 10 Pereł.
        Preferencje piratów są następujące:
        P1: Z->8;D->1;P->1
        P2: Z->1;D->8;P->1
        P3: Z->1;D->1;P->8
        Czyli każdy z piratów ma swój ulubiony rodzaj kosztowności
        inne uważając za niewiele warte.
        W wyniku zastosowania zaproponowanego algorytmu każdy z nich
        dostanie 8 kawałków tego co uważa za najceniejsze i dwie
        rzeczy, które uważa za mało cenne. Od razu widać, że
        optymalnym rozwiązaniem byłoby gdyby pierwszy dostał całe złoto,
        drugi wszystkie diamenty, a trzeci wszystkie perły.

        Ale w zadaniu nie ma mowy o optymalości,
        tylko o tym żeby się nie powyżynali.
        A to algorytm z ważeniem w postaci zaproponowanej
        przez Ciebie zapewne zapewnia.

        lwz
        • Gość: taterki Re: to może ważymy...? IP: *.media4.pl 03.12.04, 12:30
          Preferencje piratów są następujące:
          > P1: Z->8;D->1;P->1
          > P2: Z->1;D->8;P->1
          > P3: Z->1;D->1;P->8
          > Czyli każdy z piratów ma swój ulubiony rodzaj kosztowności
          > inne uważając za niewiele warte.

          Dlatego pisałem, że problemem jest stworzenie "listy wag".
          W zaproponowanym przez Ciebie przykładzie - wydaje mi się, że będąc na miejscu któregokolwiek z piratów dażyłbym po prostu do stanu 10; 0; 0. Wiedząc, ze inni niewielką chrapkę na to co u mnie jest "10" mają opłaci mi sie to.

          Ale my się męczymy, a CarDeMoon tylko kciuki trzyma...
          Może by coś podpowiedział?
          Uściślił?
          Albo zakończył zagadkę - jeli padło już jedynie słuszne rozwiązanie ;)
          Pozdrawiam
          t.

          • lapacz_w_zycie Re: to może ważymy...? 05.12.04, 12:41

            > Dlatego pisałem, że problemem jest stworzenie "listy wag".
            Ja tę listę wag rozumiem jako określenie jaką część
            skarbu stanowią poszczególne jego składniki, tzn.
            podział Z->8;D->1;P->1 oznacza, że według deklarującego
            wartość złota stanowi 80% wartości skarbu a wartość pereł i diamentów
            po 10%. Podział 10;0;0 oznaczałby, że perły i diamenty nie przedstawiają
            dla szacującego żadnej wartości, co byłoby sprzeczne z tym co napisałem:
            > Czyli każdy z piratów ma swój ulubiony rodzaj kosztowności
            > inne uważając za _niewiele_ warte.
            Poza tym nawet preferencje 10;0;0 nie gwarantowałyby otrzymania całego złota,
            gwarantowałyby natomiast nie wzięcie udziału w podziale pozostałych dóbr.

            > Ale my się męczymy, a CarDeMoon tylko kciuki trzyma...
            > Może by coś podpowiedział?
            > Uściślił?
            > Albo zakończył zagadkę - jeli padło już jedynie słuszne rozwiązanie ;)
            Nie ująłbym tego celniej.
            Przyłączam się do apelu.

            I jeszcze jedna ciekawostka. Na jednej ze stron opisujących algorytm
            Bramsa-Taylora podziału niejednorodnych dóbr (do której ktoś podał linka), jest
            adnotacja:
            "The Brams Taylor algorithm is protected by U.S. Patent #5,983,205".
            Może to jest przyczyną milczenia Cardemona - nie chce zostać pociągniętym
            przed oblicze amerykańskiej sprawiedliwości.

            lwz
            • Gość: taterki Re: to może ważymy...? IP: *.media4.pl 06.12.04, 00:07
              > Poza tym nawet preferencje 10;0;0 nie gwarantowałyby otrzymania całego złota,
              > gwarantowałyby natomiast nie wzięcie udziału w podziale pozostałych dóbr.

              Zgadza się. Ale pisałem o sytuacji do której moze dojść jeśli będą po koleji kilka razy zmieniać swoje preferencje. Przy trzech piratach każdy rezygnowal z dwóch rodzajów skarbu w zamian za całość trzeciego.

              >I jeszcze jedna ciekawostka. Na jednej ze stron opisujących algorytm
              > Bramsa-Taylora podziału niejednorodnych dóbr (do której ktoś podał linka), jest
              > adnotacja:
              > "The Brams Taylor algorithm is protected by U.S. Patent #5,983,205".
              > Może to jest przyczyną milczenia Cardemona - nie chce zostać pociągniętym
              > przed oblicze amerykańskiej sprawiedliwości.

              Możliwe... :)
      • Gość: taterki Re: to może ważymy...? IP: *.media4.pl 06.12.04, 00:42
        Może trochę uproszczę, w końcu piraci to nie matematycy ;)
        1) Podział skarbu na rodzaje
        2) Rozdanie piratom kart w ilości większej (np po 100 każdemu) niż rodzajów skarbów. Na swoich kartach każdy pirat pisze swoje imię.
        3) Piraci kładą karty przy skarbach odpowiednio do swoich preferencji.
        Karty kładą w kilku kolejkach. Powiedzmy w pierwszych trzech po 15, kolejne 3 po 10, reszta po 5 kart. Potem kilka kolejek na zmiany - też z jakimś ograniczeniem ilościowym. Ideałem by było, żeby skończyć kolejką bez zmian.
        4) Kapitan dzieli każdy rodzaj skarbu proporcjonalnie do ilości kart na niego "postawionych"

        Jawność i możliwość zmian powoduje , że po odebraniu swojej części pirat nie będzie miał wrażenia, że ktoś dostał więcej niż on.

        Niestety nie możemy się doczekać uściśleń, ale groźba bratobójczych walk skłania mnie do poszukiwania rozwiązania w którym żaden z piratów nie będzie sądził, ze którykolwiek z jego kompanów ma więcej. Natomiast mniej mnie interesuje co będzie sądził o wielkości swojej części ;)

        Pozdrawiam
        t.
    • Gość: puciapucia Re: 20 piratów z Karaibów IP: 193.220.82.* 02.12.04, 17:03
      Proponuje wykorzystac jednak metode "jeden dzieli drugi wybiera"
      1.Piratow dziele na dwie dziesiecioosobowe grupy, jedna (droga losowania)
      dzieli skarb na polowe, druga wybiera
      2. Dziesiecioosobowe grupy dziele na piecioosobowe, jedna dzieli, druga wybiera
      3. W piecioosobowych grupach jedna osoba droga losowania czeka a cztery
      pozostale dziela ich czesc skarbu na piec czesci. Osoba wylosowana wybiera swoja
      4.pozostaly skarb dwie osoby dziela na dwie czesci, drugie dwie wybieraja.
      5 No i na koniec jeden dzieli drugi wybiera.
      • cynik5 Re: 20 piratów z Karaibów i TORT 03.12.04, 05:05
        Jednym ze skarbow ktory byl do podzialu byl piekny tort czekoladowy. Do
        podzialu tego tortu uzyto jednej z metod opisana w:
        www.cs.rpi.edu/~buschc/papers/cake.pdf
        zauwazmy ze nasz Rodak Hugo Steinhaus mial z tym cos do czynienia.
    • Gość: MarekG Re: 20 piratów z Karaibów IP: 81.15.189.* 03.12.04, 11:24
      troche nad tym myslalem i chcialbym zwrocic uwage na pewien fakt. Czlowiek (a w
      szczegolnosci pirat, jak mniemam) ma nature egocentryczna. Wynika z tego ze
      mierzy innych swoja miara, dlatego tez pirat A bedzie ocenial wartosc czesci
      skarbu pirata B stosujac wlasne kryteria. Taka juz jest natura czlowieka. Idąc
      dalej mozna stwierdzić, że pirat A bedzie usadysfakcjonowany tylko w takim
      przypadku jesli stwierdzi ze zaden z jego kolegow nie dostal czesci skarbu o
      wiekszej niz on wartości (taka wlasnie sytuacja byla by powodem sporow),
      podczas tej oceny stosowal bedzie oczywiscie wlasne kryteria, bo taka jego
      natura. Z powyzszego wynika ze podzial "wszystkiego po rowno". usadysfakcjonuje
      kazdego, poniewaz w ocenie kazdego z piratrow takie same czesci skarbu maja
      taka sama wartosć.
    • emkaminsk Re: 20 piratów z Karaibów 03.12.04, 12:47
      Problem jest rzeczywiście trudny, a naukowo rozwiązany został dopiero w latach
      90-tych przez Bramsa i Taylora. Historia problemu jest tutaj:
      www.colorado.edu/education/DMP/dividing_spoils.html , jednak sama
      procedura jest tam przedstawiona z błędami (np po podstawieniu do podanego wzoru
      n=5 wychodzi 7 a nie 9 jak jest w tekscie).

      Algorytm B-T pozwala podzielić niejednorodny zestaw dóbr pomiędzy n uczestników
      posiadających różne pola preferencji i wykluczając zjawisko 'zawiści'. W istocie
      każdy z uczestnikow dostaje W SWOJEJ OCENIE więcej, niż 1/n część całości.
      www.barbecuejoe.com/eco101.htm
      Niestety do szczegółów jeszcze nie dotarłem, ale gdy znajdę, może tu opiszę :)
      • Gość: grzesiek Re: 20 piratów z Karaibów IP: *.visp.energis.pl 05.12.04, 14:56
        Spróbuję sformalizować problem.

        Każdy j-ty pirat określa swój system wartości podając zestaw wartości W[i,j] poszczególnym
        i-tym elementom skarbu. Ocenia tu całe elementy, a nie jakieś tam jednostki. Np. podaje:
        cała kupa złota=200, wszystkie diamenty=127, itd. Każdy pirat uzywa do tej oceny
        swojej własnej, dowolnej jednostki wartosci. Herszt wszystkie te zestawy W[i,j]
        normalizuje do w[i,j] (dla każdego j suma w[i,j] po i = 1). Teraz herszt musi wypracować
        podział p[i,j] - j-ty pirat otrzyma p[i,j]-tą część i-tego elementu skarbu. Przy wyborze
        podziału będzie się kierował następującymi kryteriami:
        1) Piraci muszą być przekonani że podział jest sprawiedliwy, t.zn. że:
        dla każdego j Z[j] = suma po i z iloczynów p[i,j]*w[i,j] jest niezależna od j.
        Oznaczmy tę sumę Z. Jest to po prostu subiektywna, znormalizowana ocena
        tego co każdy pirat dostanie, dokonana według jego skali wartości, i wszystkie te
        oceny powinny być równe.
        2) Z powinno być maksymalnie duże. Wiadomo że przy podziale "wszysko po równo"
        Z=1/N, czyli że rzeczywiście uzyskane Z powinno być większe od 1/N.
        Oczywiście w zdegenerowanym przypadku gdy wszyscy piraci objawią taki
        sam system wartości nie jest mośliwe uzyskanie Z > 1/N.

        O ile pamiętam, rozwiązywaniem tego typu problemu optymalizacji zajmuje się
        t.zw. "programowanie liniowe". Liniowość problemu kryje się w fakcie że
        funkcja celu Z jest funkcją liniową p[i,j]. Tak więc najwygodniej by było, gdyby
        herszt miał komputer z oprogramowaniem do programowania liniowego.
        Jest jednak problem, że piraci mogli by się z tym przeteoretyzowanym
        wywodem nie zgodzić!
        • Gość: Corvax Re: 20 piratów z Karaibów IP: *.neoplus.adsl.tpnet.pl 10.12.04, 07:44
          Chyba studyjka zrobiły Ci wodę z mózgu i teraz próbujesz zrobić tak innym.
          Programowanie liniowe na pewno się tym nie zajmuje. Co najwyżej ogólnie
          programowanie matemetyczne, ale tego nie było.
          Funkcja celu to by była w tym zadaniu funkcja preferencji albo użyteczności, a
          kto powiedział że preferencje są liniowe. Ty tak masz? Nawet wyjątkowo
          nieskomplikowane jednostki trudno posądzać o posiadanie liniowych preferencji.
          A poza tym co chcesz optymalizować. Zadowolenie indywidualnych uczestników czy
          grupy. Jedno z drugim sie nie musi pokrywać.
          Mam pomysł.
          Najlepiej by było, gdybyś kupił komputer z oprogramowaniem do programowania
          liniowego. Skasowałbyś je sobie żeby nie przeszkadzało i wtedy mógłbyś
          poukładac sobie pasjansa zamiast wypisywać takie przeteoretyzowane wywody z
          którymi ktoś może się zgodzić!
    • rzeznicc_wc3 Re: 20 piratów z Karaibów 05.12.04, 15:37
      dane:

      P-pirat
      X-rodzaj skarbu (niezależnie od jego ilości)
      N-pewna wartość (ilość piratów,ilość rodzaji skarbów)
      n-pewna wartość (liczba pożądkowa , np Pn pirat nr n , Xn rodzaj skarbu nr n)

      -20P , jako że jest dwódziestu piratów
      -NX jest większe lub równe 7, jako że nie znamy ilości rodzaji zagrabionych
      dóbr , nie wiemy czy skarbów jest conajmniej 20 czyli tyle aby każdy piart mógł
      określić swój ulubiony gatunek/gatunki kosztowności , wiemy tylko że :"wsród
      których były diamenty, złoto, perły, drogocenne tkaniny(kaszmir i jedwab) i
      inne rzeczy(rubiny plus conajmniej jedna żecz)"
      -każde Pn musi mieć przypisane właściwą tylko sobie wartość NXn

      rozwiązywanie :

      1.Każdy pirat określa na głos skarby na których mu zależy ponad inne
      -przypożądkowywujemy każdemu Pn wartość NXn dla NP=20

      2.Skarby które nie znalazły chętnych dzielimy każdy z osobna na równe 20 części
      i rozdajemy po jednej części każdemu piratowi , lub jeśli dany skarb jest
      niepodzielny (a wiemy że na tych skarbach piratom nieszczególnie zależy) to
      albo wkłądamy go do kufra niepodzielony i zachowujemy do podziału na następne
      grabieże , albo zużywamy przy wachaniu podziału o któym będzie mowa w punkcie 4
      (czyli jeśli 2 piratom będzie zależało na rubinie , i zostanie on źle
      przełamany na mniejszą i większą część , to stawiamy na ugodę i jeden pirat
      otrzymuje większą częśc tego co porządał, a drugi mniejszą plus skarb pozostały
      z podziału ogólnego - niewybrany , niepodzielny - jako rekompensatę)
      -Xn dla n z nieoznaczonego przedziału nE{n1...nn} dzielimy przez 20P

      3.Rozdajemy każdemu z piratów , który jako jedyny pragnął danego dobra/dóbr owo
      dobro/dobra i wyłączamy go tymczasowo z podziału
      -przypisujemy dla NP NXn jeśli NP=1

      4.Dzielimy dany skab pomiędzy zainteresowanych (dla niepodzielności patrz punkt
      2)
      -Xn/NP

      w tym momencie każdy z piratów powinien mieć równą część tego czego pragnął (w
      wersji idealnej podzielności łupów) lub przyjajmniej jego starta zostanie
      powetowana

      sposób ten pozwala na obliczanie sytuacji gdy 7<x<20 , x=20 i x>20

    • Gość: Corvax Re: 20 piratów z Karaibów IP: *.neoplus.adsl.tpnet.pl 10.12.04, 07:22
      A kto powiedział że taki "sprawiedliwy" podział jest wogóle możliwy.
      Problem został sformułowany skrajnie nieprecyzyjnie. Co wiemy o tzw.
      upodobaniach piratów? Ano nic poza tym że każdy ma inne.

      Ten problem ma rozwiązanie ale tylko przy pewnych formalnych założeniach
      odnośnie indywidualnych preferencji poszczególnych graczy i łącznych
      preferencji całej grupy. Udowodnił to Arrow za co dostał nagrodę Nobla z
      ekonomii (wiadomo z matematyki nie dają) w 1972 roku.

      A więc po co umieszczać tu takie problemy, które nie mają jasnego rozwiązania.

      Uważam że autor tej zagadki sam nie ma pojecia o czym mówi.
      • Gość: taterki Re: 20 piratów z Karaibów IP: *.internetdsl.tpnet.pl 10.12.04, 09:43
        > A kto powiedział że taki "sprawiedliwy" podział jest wogóle możliwy.

        Nie było mowy o sprawiedliwości, miało byc po "równo"

        > Problem został sformułowany skrajnie nieprecyzyjnie.

        Zgadzam się.

        > Ten problem ma rozwiązanie ale tylko przy pewnych formalnych założeniach
        > odnośnie indywidualnych preferencji poszczególnych graczy i łącznych
        > preferencji całej grupy. Udowodnił to Arrow za co dostał nagrodę Nobla z
        > ekonomii (wiadomo z matematyki nie dają) w 1972 roku.

        Brawo


        > A więc po co umieszczać tu takie problemy, które nie mają jasnego rozwiązania.

        I tu się z Tobą kompletnie nie zgadzam. Weźmy przykład zagadki o 100 więźniach - nie ma rozwiązania jak dotąd a całkiem przyjemnie można popracować głową nad znalezieniem jakiejś drogi. Myślę nawet, ze warto by do niej wrócić bo jak ktoś zauważył w początkowej fazie rozwiązania poprzednia ekipa prawdopodobnie popełniła błąd.
        Poza tym nie wiem czym Ty się zajmujesz ale ja dzięki tym zagadkom przypominam sobie masę rzeczy ze szkoły i dowiaduję się czasem czegoś ciekawego.

        > Uważam że autor tej zagadki sam nie ma pojecia o czym mówi.

        Sformułował bym to nieco lżej. Nie umie przyznać się do błędu. Podobnie jak w jednej z poprzednich zagadek. Natomiast jeśli poczytasz archiwum grupy - bo nie wiem jak długo już tu jesteś to wrzucił tu całą mase bardzo ciekawych problemów i tej zasługi odebrać mu nie można.

        Pozdrawiam
        taterki
        • Gość: Corvax Re: 20 piratów z Karaibów IP: *.neoplus.adsl.tpnet.pl 11.12.04, 02:17
          "Sprawiedliwie" (co to wogóle znaczy?) czy po "równo"?
          Nadal nie wiadomo co autor miał na myśli.
          Chodziło pewnie żeby każdy był zadowolony z dokonanej alokacji.

          Nawet jeżeli istnieje jakiś szybki algorytm prowadzący do rozwiązania to
          trzeba najpierw wprowadzić szereg dodatkowych założeń. Następnie wypadałoby
          udowodnić że zaproponowany algorytm generuje podział spełniający (niekompletne)
          warynki zadania. NIewykonalne...

          Może Autor poda rozwiązanie? ;-)
          • cynik5 Re: 20 piratów z Karaibów Englis h 11.12.04, 03:22
            Gość portalu: Corvax napisał(a):

            > "Sprawiedliwie" (co to wogóle znaczy?) czy po "równo"?
            > Nadal nie wiadomo co autor miał na myśli.
            > Chodziło pewnie żeby każdy był zadowolony z dokonanej alokacji.
            >
            > Nawet jeżeli istnieje jakiś szybki algorytm prowadzący do rozwiązania to
            > trzeba najpierw wprowadzić szereg dodatkowych założeń. Następnie wypadałoby
            > udowodnić że zaproponowany algorytm generuje podział spełniający
            (niekompletne)
            >
            > warynki zadania. NIewykonalne...
            >
            > Może Autor poda rozwiązanie? ;-)

            Szkoda ze nikt nie komentowal na linki podane powyzej przez emkaminsk i autora
            tego wpisu.
            Niestety wszystkie trzy artukuly sa po angielsku
            Pozdrawiam
            CYNICZNy CYNIK
            • cynik5 Re: 20 piratów z Karaibów Englis h 11.12.04, 03:25
              cynik5 napisała:

              > Gość portalu: Corvax napisał(a):
              >
              > > "Sprawiedliwie" (co to wogóle znaczy?) czy po "równo"?
              > > Nadal nie wiadomo co autor miał na myśli.
              > > Chodziło pewnie żeby każdy był zadowolony z dokonanej alokacji.
              > >
              > > Nawet jeżeli istnieje jakiś szybki algorytm prowadzący do rozwiązania to
              > > trzeba najpierw wprowadzić szereg dodatkowych założeń. Następnie wypadało
              > by
              > > udowodnić że zaproponowany algorytm generuje podział spełniający
              > (niekompletne)
              > >
              > > warynki zadania. NIewykonalne...
              > >
              > > Może Autor poda rozwiązanie? ;-)
              >
              > Szkoda ze nikt nie komentowal na linki podane powyzej przez emkaminsk i
              autora
              >
              > tego wpisu.
              > Niestety wszystkie trzy artukuly sa po angielsku
              > Pozdrawiam
              > CYNICZNy CYNIK
              PS
              Podzial powyzszy ma nastepujace cechy:

              Proportional (proporcjonalny)
              Envy-free ( Nikt nie jest zazdrosny)
              • rzeznicc_wc3 Re: 20 piratów z Karaibów Englis h 25.12.04, 14:56
                powyżej podałem próbę , najprawdopodobniej błędną , rozwiązania .
                ktoś mógłby ja zweryfikować ?

                i proszę nei pisać że zadanie nei ma rozwiązań . to że komuś trudno napisać
                algorytm ( ? ) z niewiadomą niewiadomej niewiadomej nie oznacza że zadanie to
                nie ma rozwiązania .
    • lapacz_w_zycie Re: 20 piratów z Karaibów 28.12.04, 21:16
      Po zerowe
      Uwaga poniższy tekst zawiera znaczną ilość informatycznego slangu/bełkotu.
      Czytanie na własną odpowiedzialność.

      Po pierwsze
      Formalizacja zaproponowana przez grześka wydaje się być sensowna:

      ------
    • Gość: grzesiek Re: 20 piratów z Karaibów IP: *.warszawa.cvx.ppp.tpnet.pl 10.11.05, 21:53
      Pozwalam sobie odgrzać tę starą zagadkę, bo niedawno dowiedziałem się
      od kolegi jak wygląda algorytm podziału uogólniony na większą liczbe
      osób. W przypadku dwóch osób mamy znane: jeden dzieli drugi wybiera.
      Miałem szczęście, bo znalazłem tę zagadkę na samym końcu listy!

      Sposób podziału jest taki: dowolna osoba wydziela z całości to co by chciała
      dostać. Jeśli nikt nie zaprotestuje, to zabiera swoje i następny wybiera.
      Jeśli ktoś zaprotestuje, to kolejka przechodzi na niego, ale od tego momentu
      z wybranej przez pierwszego porcji można tylko ujmować. Jeśli po ujęciu
      kawałka nikt nie zaprotestuje, to on to zabiera i zaczynamy od początku.
      Jeśli zaprotestuje to na niego przechodzi kolejka, itd.

      Inaczej to ujmując - proces podziału może być w jednej z dwu faz: w fazie
      pierwszej ktoś wybiera fragment z całego skarbu i to zaczyna fazę drugą.
      W fazie drugiej przedmiotem zainteresowania jest wyłącznie wybrany fragment,
      być może stopniowo pomniejszany. Jeśli w jakimś momencie czyjaś propozycja
      zostanie przez wszystkich zaakceptowana, to wracamy do fazy pierwszej.

      Kluczowe w tym algorytmie jest to, że można wziąć swój kawałek tylko przy
      zgodzie wszystkich zainteresowanych, to znaczy tych którzy swojej doli jeszcze
      nie wzięli. Ważne jest również to, że jeśli skarb można dowolnie dzielić, to
      ten algorytm gwarantuje że się skończy.

      Sam jestem zafascynowany prostotą tego sposobu.
      • cardemon Re: 20 piratów z Karaibów 11.11.05, 05:51
        Gość portalu: grzesiek napisał(a):

        > Pozwalam sobie odgrzać tę starą zagadkę (...)

        Tak, rozwiązanie problemu jest w swej istocie zarówno genialne jak i proste, i
        kilka osób podało tu prawidłowy algorytm, aczkolwiek muszę dodać, że rzecz jest
        dużo bardziej skomplikowana niż nawet wydaje się takiemu bardzo aroganckiemu
        Corvaxowi, który twierdzi, że Nobel '72 z ekonomii cały niniejszy problem
        rozwiązuje jednym pstryknięciem palca. Nie, nie rozwiązuje w żadnym stopniu! Ale
        nie jest to tutaj miejsce na to, by dyskutować prace naukowe z ekonomii, a już
        na pewno nie na to, by wdawać się w pyskówki na poziomie Corvaxa...

        Moim zamiarem w zamieszczaniu łamigłówek na tym forum zawsze było i zawsze jest
        zainteresowanie forumowiczów pewnymi problemami zahaczającymi o zagadnienia z
        różnych dyscyplin naukowych. Jeśli ten cel udaje mi się osiągnąć, to moja misja
        jest spełniona. :)

        Pozdrawiam wszystkich łamigłówkowiczów, nie pozdrawiam impertynentów!
        CdM
        • cardemon Re: 20 piratów z Karaibów 11.11.05, 06:26
          Tych, którzy szukają dalszych informacji dotyczących przedstawionego tu
          zagadnienia, zachęcam do sięgnięcia do podanych już wyżej linków (wszystkie w j.
          angielskim):

          www.colorado.edu/education/DMP/dividing_spoils.html
          www.barbecuejoe.com/eco101.htm
          www.cs.rpi.edu/~buschc/papers/cake.pdf

          Wielkie podziękowania dla Emkaminksa i Cynika5!

          pzdr.

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka