20 piratów z Karaibów

[cardemon]

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.

[andy._]

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]

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]

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._]

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]

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]

Wiem jak się dzieli cośtam na 2 osoby ;)
Jeden dzieli, a drugi wybiera.
I wtedy jest ok.

[andy._]

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]

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]

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]

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]

> 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]

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]

> 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]

> 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._]

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]

Bzdura............

[Gość: taterki]

> Bzdura............


Podpis dałeś.
Mógłbyś jeszcze uzupełnić treść?
Pozdrawiam
taterki :)

to może ważymy...?

[Gość: taterki]

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]

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]

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]

> 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]

> 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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

> 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]

"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]

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]

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]

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 .

zazsada - wybieram sasiadowi /nt

[wojcd]

[lapacz_w_zycie]

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]

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]

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]

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.