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.
Edytor zaawansowany
  • andy._ 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 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 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.
  • andy._ 01.12.04, 23:15
    Nie może być takiej blokady, bo każdy może w swojej kolejce tylko zmniejszać
    bieżącą 1/N-tą. Zwiększanie czegokolwiek jest niedopuszczalne!
  • Gość: taterki 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
  • Gość: darekw IP: *.neoplus.adsl.tpnet.pl 01.12.04, 11:52
    Wiem jak się dzieli cośtam na 2 osoby ;)
    Jeden dzieli, a drugi wybiera.
    I wtedy jest ok.
  • andy._ 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 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 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 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 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 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 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 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._ 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ść: Corvax IP: *.neoplus.adsl.tpnet.pl 02.12.04, 11:25
    Bzdura............
  • Gość: taterki IP: *.media4.pl 02.12.04, 12:43
    > Bzdura............


    Podpis dałeś.
    Mógłbyś jeszcze uzupełnić treść?
    Pozdrawiam
    taterki :)
  • Gość: taterki 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 .
  • wojcd 26.12.04, 22:38
  • lapacz_w_zycie 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:

    -------- grzesiek napisał ----------
    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.
    -------- /grzesiek napisał ----------

    z tym że warunek:

    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.

    zamieniłbym na:

    Każdy pirat musi być przekonany że jego część jest niemniejsza niż
    część któregokolwiek innego pirata
    t.zn. że: dla każdego j Z[j] = suma po i z iloczynów p[i,j]*w[i,j]
    jest >= p[i,k]*w[i,j] dla dowolnego k


    Wprowadzę jeszcze jedną pomocnicze pojęcie,
    mianowicie tablicę przewartościowań.
    Dla każdego przedmiotu i
    przewart[i]= max(w[i,j])/avg(w[i,j]) dla każdego j-tego pirata
    czyli dla każdego przedmiotu liczę stosunek jego maksymalnej
    wartości do jego średniej wartości.


    Po drugie przy takiej formalizacji zaproponowałbym następujący algorytm:


    [1] Jeśli zostało jeszcze coś do podziału:

    Rozpoczynamy nową turę - wszyscy biorą w niej udział

    [2] jeśli już nikt nie bierze udziału w tej turze skaczemy do [1]
    w przeciwnym przypadku:

    wybieramy najbardziej przewartościowany przedmiot, który nie
    został jeszcze przydzielony
    (jeśli klika przedmiotów ma taką samą 'wartość przewartościowania'
    z tablicy przewart wybieramy którykolwiek z nich )

    Wybieramy osobę, która ceni ten przedmiot najbardziej.
    Przydzielamy jej taką część tego przedmiotu (być może cały),
    żeby wartość przedmiotów przydzielonych tej osobie w tej turze nie
    przekroczyła 1/20 skarbu który był do podziału przed tą turą
    (oczywiście 1/20 wg. oceny tej osoby)
    Jeśli po przydzieleniu przedmiotu (lub jego części), osoba dostała
    już w tej rundzie 1/20 skarbu dzielonego w tej rundzie to:
    ta osoba nie bierze udziału w dalszej części rundy;
    tabelę przewartościowań przeliczamy biorąc pod uwagę
    preferencje tych osób które biorą tej osoby.
    Skaczemy do [2].

    Po skończonej liczbie tur nie będzie już nic do przydzielenia.
    Każdy pirat zabiera to wszystko co zostało mu przydzielone w kolejnych turach.

    Po trzecie
    Powyższy algorytm nie zawsze daje optymalne rozwiązanie (ale się stara).
    Zawsze za to daje poprawne tzn. piraci się nie pozażynają (jeśli założona
    w "po pierwsze" formalizacja jest poprawna).
    Zadanie pachnie mi (a może raczej śmierdzi) NP trudnością
    Gdybym był zwolennikiem spiskowych teorii to pomyślałbym,
    że Autor ma nadzieję, że ktoś kto o tym nie wie, rozwiąże zadanie w czasie
    wielomianowym, a Autor zgarnie medal Fieldsa za dowód, że P=NP.
    (przepraszam, że na forum publicznym piszę coś co może nie wszyscy rozumieją,
    ale to jest dłuższa historia. Dla ciekawych google + ["p=np" problem])

    Po czwarte
    przyłączam się do chóru innych rozwiązujących z prośbą do autora
    o komentarz rozwiązań.
    Autor! Autor! Autor!

    lwz
  • Gość: grzesiek 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 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

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka