• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Problem sprawiedliwego podziału (c.d)

    16.06.2009. 22:50
    opublikowane przez: Przemysaw Szydzik

    Następny przedstawiony protokół będzie protokołem “bez zazdrości" rozpatrzonym dla trzech graczy. Wymaga on kombinacji idei wprowadzonych przez Banacha i Knastera o przycinaniu oraz podstawowej struktury użytej przez Steinhausa. Ponadto wprowadza ważne pojęcie “bezapelacyjnej przewagi" jednego z graczy nad drugim.

    Protokół “bez zazdrości" dla n=3. (Selfridge, Conway, ok. 1960)


    Krok 1. Gracz 1 tnie ciasto na 3 części, które uważa za równe.
    takie, że
    - miara gracza 1 (funkcja przyporządkowująca zbiorowi liczbę rzeczywistą określającą jego wielkość)


    Krok 2. Graczowi 2 dawany jest wybór:
    (i) spasować, jeśli myśli, że dwa lub więcej kawałków jest największych i równych
    tzn.
    (ii) przyciąć największy z trzech kawałków, żeby stworzyć przynajmniej dwa największe i równe
    tzn. takie, że
    Jeśli gracz 2 przycina kawałek, to przycięcie nazywamy L (od “leftover"=reszta) i odkładamy na bok.
    Krok 3. Gracze w kolejności 3, 2, 1 wybieraja kawałek, który uważają za największy, spośród trzech, gdzie jeden mógł być przycięty w kroku drugim. Jeśli gracz 2 przycinał, to wymagane jest, aby wybrał ten właśnie kawałek, jeśli nie zrobi tego wcześniej gracz 3.
    (a) takie, że
    (b) takie, że
    (c) Jeśli to
    Jeśli to takie, że
    (d)

    Uwaga: Zauważmy, że tylko cześć ciasta została podzielona. To daje podział ciasta , gdzie jest częściowym podziałem “bez zazdrości". Brak zazdrości jest prawdą, gdyż:
    (1) Gracz 3 wybierał pierwszy, wiec
    (2) Gracz 2 określił przynajmniej dwa kawałki jako jednakowe i największe, więc przynajmniej jeden jest wciąż osiągalny
    (3) Gracz 1 sam dzielił ciasto na kawałki o rozmiarze 1/n, a przycięta cześć na pewno została wzięta albo przez gracza 3 albo 2.

    Krok 4. Jeśli gracz 2 spasował w drugim kroku, to całe ciasto jest rozdzielone. Poza tym, albo gracz 2 albo 3 otrzyma przycięty kawałek, a ten który nie otrzymał dostanie nieprzycięty. Którykolwiek gracz otrzymał nieprzycięty kawałek dzieli teraz L na trzy części, które uważa za równe. Nazwiemy tego gracza “tnący", a pozostałych “nie tnący". Niech oznacza numer gracza.
    Jeśli to GP="tnący" a GC="nie tnący" dla
    gdzie

    Uwaga: Będziemy oznaczać gracza 1 jako posiadającego bezapelacyjna przewagę nad “nietnącymi". Ponieważ “nietnący" gracz otrzymał przycięty kawałek, gracz pierwszy nie zazdrości mu, nie zważając na to, jak później będzie podzielone L pomiędzy ich trzech.
    tzn.

    Krok 5. Trzy kawałki, na które zostało podzielone L są teraz wybierane przez graczy w następującej kolejności: “nie tnący", gracz 1, “tnący".
    (i) takie, że
    (ii) takie, że
    (iii)

    Ostatnim omówionym protokołem będzie protokół opracowany przez Stevena Bramsa i Alana Taylora, “bez zazdrości" dla dowolnej liczby graczy n. Główna cecha tego protokołu jest to, że dla 3 graczy przycinają oni kawałki, żeby stworzyć równe i uznając je za rozróżnialne. Kiedy n > 3 jeden z graczy musi zacząć przycinanie i wybrać proces, prowadzący do “częściowego podziału bez zazdrości" z większa ilością kawałków niż jest graczy. Dla nieformalnej ilustracji, jak osiągnac częściowy podział bez zazdrości załóżmy, że mamy 4 graczy. Pierwszy tnie ciasto na 5 równych częsci. Gracz drugi przycina dwie, tworząc trzy jednakowe i największe. Następnie gracz trzeci przycina jeden kawałek, tworząc dwa jednakowe i największe. Gracze teraz wybierają w kolejności: 4, 3, 2, 1, gdzie środkowi gracze muszą wybrać kawałek przycięty (który sami przycięli) jeśli jest on osiągalny. Istota takiego przestawienia n-osobowego protokołu “bez zazdrości" jest pokazanie, ze całkowity podział może być dokonany w skończonej liczbie kroków.

    Protokół bez zazdrości dla dowolnego n. (ok 1992)

    Dla ułatwienia przyjmujemy n=4.

    Krok 1. Gracz 2 dzieli ciasto na 4 części, które uważa za równe. Zatrzymuje jeden kawałek, a pozostałe rozdaje graczom.
    Krok 2. Każdy z graczy jest pytany o to, czy nie sprzeciwia się takiemu podziałowi. Gracz wznosi sprzeciw, jeśli zazdrości innemu graczowi.
    Krok 3. Jeśli żaden z graczy się nie sprzeciwia, to każdy zatrzymuje swój kawałek. Ciasto jest podzielone.
    Krok 4. W przeciwnym wypadku wybieramy najmniejsze i spośród graczy, którzy się sprzeciwili. Dla ułatwienia niech i = 1. Gracz 1 wybiera cześć przydzielona graczowi, któremu zazdrości i nazywa ja A . Kawałek przydzielony graczowi 1 nazywamy B.

    Uwaga: Mamy teraz części A i B . Pozostałe dwa kawałki z kroku 1 są zabrane. Ta częśc ciasta zostanie podzielona później. Zauważmy, że gracz 1 uważa, że A > B, zaś gracz 2 twierdzi, ze A = B.

    Krok 5. Gracz 1 podaje liczbę całkowita wybraną tak, że dla dowolnego podziału A na r części gracz 1 będzie wolał A nawet bez 7 najmniejszych części.

    Uwaga: Gracz 1 może z łatwością wybrać takie r, wystarczająco duże, aby gdzie jest miarą gracza 1.

    Krok 6. Gracz 2 dzieli A i B na r równych części.
    Krok 7. Gracz 1 wybiera najmniejsze 3 spośród podziału B i nazywa je . Wybiera też 3 największe części A, jeśli uważa je za większe od każdej , przycina co najmniej dwie (do rozmiaru najmniejszej z nich) lub dzieli jedną, największa część z A na 3 kawałki, które uważa za równe. W obu przypadkach nazywamy je .

    Uwaga: Strategia gracza 1 w kroku 7 gwarantuje, że będzie on uznawał wszystkie spośród za większe lub równe każdej . Jest to prawdą, nawet, jeśli wybierze drugą opcję.
    Gracz 2 uważa, ze wszystkie są równe i każda jest co najmniej tak duża jak .

    Krok 8. Gracz 3 bierze zbiór 6 kawałków . Nic nie robi, jeśli uważa, że przynajmniej dwa są równe i największe, albo przycina największy do rozmiaru następnego w kolejności, w ten sposób tworząc dwa równe i największe.
    Krok 9. Gracze 4, 3, 2, 1 w takiej kolejności wybierają kawałki spośród zmodyfikowanych w kroku 8 (które uważają za największe), gdzie od gracza 3 wymaga się, aby wybrał kawałek, który przycinał, jeśli nie zrobił tego wcześniej gracz 4. Gracz 2 musi wybrać jeden spośród zaś gracz 1 wybiera z .

    Uwaga: Zbiór podziałów tak jak zbiór jest częściowym podziałem bez zazdrości i jest resztą. Ponadto gracz 1 uważa, że jego kawałek jest ostro większy, powiedzmy o od kawałka gracza 2.

    Krok 10. Gracz 1 wybiera teraz dodatnią liczbę całkowitą , taką ze:

    Uwaga: s określa ile razy gracz iteracyjnie powtórzy sekwencje “przytnij i wybierz". Zauważmy, że gdyby zezwolić na kontynuowanie iteracji, dopóki gracz 1 nie powie “stop" (co mógłby zrobić w momencie, kiedy uznałby, ze “okruchy" są mniejsze od przewagi, która ma nad graczem 2) nie byłoby gwarancji, ze nie będzie on przetrzymywać gry w nieskończoność.

    Krok 11. Gracz 1 dzieli na 5 kawałków, które uważa za równe.
    Krok 12. Gracz 2 bierze zbiór tych 5 kawałków, wybiera 3 największe i przycina co najwyżej 2, aby stworzyć 3 równe i największe.
    Krok 13. Gracz 3 bierze zbiór 5 kawałków, prawdopodobnie przyciętych w kroku poprzednim, wybiera największe 2,przycina większy, aby stworzyć dwa równe i największe.
    Krok 14. Gracze w kolejności 4, 3, 2, 1 wybierają kawałek spośród zmodyfikowanych 5, gdzie od gracza 3 i 2 wymaga sie, aby wybrali części, które przycinali, jesli będą osiągalne.
    Krok 15. Kroki 11 - 14 powtarzane są s-1 razy, gdzie każde zastosowanie tych kroków dotyczy pozostałego kawałka z poprzedniego użycia procedury.

    Uwaga: Zbiory podziałów tak jak stanowią częściowy podział bez zazdrości i gracz 1 twierdzi, ze jego kawałek jest większy niż . Deklarujemy teraz, że gracz 1 ma bezapelacyjną przewagę nad graczem 2 i tworzymy podzbiór zbioru .

    Krok 16. Gracz 2 dzieli na 12 równych części.
    Krok 17. Każdy z graczy deklaruje się jako typ jeśli zgadza się z tym, ze każdy z 12-stu kawałków jest tego samego rozmiaru, lub jako typ , jeśli się nie zgadza. Gracz 2 naturalnie deklaruje się jako typ .
    Krok 18. Jeśli to dajemy 12 kawałków graczom ze zbioru , gdzie każdy z nich dostanie taką samą liczbę części. Jeśli tak zrobimy, to skończymy rozdzielanie.
    Krok 19. W przeciwnym wypadku wybieramy leksykograficznie najmniejszą parę należąca do , która nie należy do NP i wracamy do kroku 4 z graczem i-tym w roli gracza 1, graczem j-tym jako gracz 2 oraz zamiast całego ciasta.
    Krok 20. Powtarzamy kroki 5 - 18.

    Uwaga: Za każdym razem, kiedy przechodzimy przez krok 15 dodajemy i porządkujemy parę w NP. Zauważmy, że ponieważ oraz musi być, ze po co najwyżej 16-stu powtórzeniach. W związku z tym kończymy dzielenie całego ciasta bez zazdrości w kroku 18.

    Autor: Magda Dobrzeniecka*

    *Autorka jest studentką IV roku zastosowań matematyki Wydziału Matematyki i Informatyki Uniwersytetu Mikołaja Kopernika w Toruniu.

    Czy wiesz ĹĽe...? (beta)
    Chomp jest grą dla dwóch graczy, w której gra się na prostokątnej "tabliczce czekolady", która dzieli się na mniejsze, kwadratowe kostki. Gracz podczas ruchu musi wybrać jedną z kostek i "zjeść ją", tj. usunąć ją z planszy razem z tymi poniżej i na prawo od niej. Kostka w lewym górnym rogu jest zatruta – ten gracz, który ją weźmie, przegrywa. Wąż to gra komputerowa, która została wydana w połowie lat siedemdziesiątych XX. wieku, zyskując wielką popularność. W grze gracz kontroluje długie i cienkie stworzenie, podobne do węża, które porusza się po obramowanej planszy zbierając jedzenie (lub inne przedmioty), próbując nie uderzyć własną głową o "ściany" otaczające planszę gry, a także o część własnego ciała. Kiedy "wąż" zje kawałek jedzenia, jego ogon robi się coraz dłuższy, co utrudnia grę. Gracz kontroluje kierunek ruchu "węża" za pomocą klawiszy strzałek (góra, dół, lewo, prawo). Gracz nie może zatrzymać "węża", gdy gra jest w toku. Wąż może składać jaja, które są dodatkowymi przeszkodami. Equal offense jest grą bilardową wywodzącą się z Czternaście plus jeden. Każdy gracz dostaje dziesięć tur z rzędu. Oznacza to, iż najpierw podchodzi gracz pierwszy, wykonuje dziesięć tur, a następnie drugi i wykonuje swoje dziesięć. Za faul nie odejmuje się punktu. Po faulu następuje koniec tury, a gracz otrzymuje bilę rozgrywającą do umieszczenia w "kuchni".

    W teorii gier, strategia to plan działania gracza opisujący jego zachowanie w każdej możliwej sytuacji. Strategia w pełni określa akcję (ruch), którą gracz podejmie w danej sytuacji, na każdym etapie gry, dla każdej możliwej historii prowadzącej do tej sytuacji. Wikipedystka:IsadoraDeWitch/brudnopis4 Backgammon/Chouette: Chouette (z fr. Sowa), to odmiana backgammona dla więcej niż dwóch graczy. Istnieje wiele zasad gry w tę właśnie odmianę, dlatego osoby, które chcą się przyłączyć do gry, powinny najpierw zapoznać się z obowiązującymi przy danym stole wymaganiami. W tym artykule przedstawione zostaną podstawowe zasady gry w Sowę, gry w wielu aspektach bezwględnej, dla niektórych pewnie nie zawsze do końca uczciwej, ale na pewno atrakcyjnej i zupełnie innej niż gra w dwójkę. Przed rozpoczęciem gry, każdy z graczy rzuca jedną kostką i ten, który wyrzuci najwięcej oczek zostaje tzw. Boxem i będzie grać przeciwko drużynie. Gracz, który wyrzucił najwięcej oczek spośród pozostałych osób, zostaje Kapitanem drużyny. Zadaniem kapitana jest rzucanie kości i wykonywanie ruchu drużyny. Hierarchia drużyny jest ustalana również według ilości wyrzuconych oczek. W przypadku remisu, powtarza się rzut. Tak więc po losowaniu mamy następującą sytuację: po jednej stronie planszy jest Box, a po drugiej Kapitan, Gracz 1, Gracz 2, Gracz 3 itd. Jeżeli w grze bierze udział więcej niż osiem osób. Box może wybrać sobie partnera do gry. Partnerstwo takie oferuje się najpierw Kapitanowi, a potem kolejnym graczom. Jeśli nikt nie przyjmie oferty, partnera można wylosować spośród graczy, omijając przy tym kapitana. W Sowie obowiązują standardowe reguły gry z uwzględnieniem zasady Jacoby’ego, która mówi, że nie można wygrać gammonem lub backgammonem dopóki kostka dublująca nie znajdzie się w grze. Trzeba tu zauważyć, że Sowa jest zazwyczaj grana na pieniądze, zasada Jacoby’ego pozwala przyspieszyć grę, jak również eliminuje ryzyko wysokich przegranych w momencie, gdy jeden z przeciwników już na początku gry uzyskał sporą przewagę. W tym momencie (mając świadomość, że gammonem może wygrać tylko jeśli zdubluje) gracz z przewagą używa kostki dublującej, co jego przeciwnik może i powinien odrzucić, oddając graczowi z przewagą tylko jeden punkt. Wróćmy jednak do naszych graczy. Załóżmy, że przeciwko Boxowi gra Kapitan i pięciu graczy. Co się dzieje po zakończeniu gry. Jeśli Box wygra, zostaje na swoim miejscu, a Kapitan wędruje na koniec kolejki i staje się graczem numer pięć. Z kolei gracz numer jeden staje się Kapitanem. Natomiast jeśli Box przegra, wędruje on na koniec kolejki i staje się graczem numer pięć, a Kapitan staje się Boxem. Jeśli gra toczy się na pieniądze, przegrany Box wypłaca uzgodnioną wcześniej stawkę każdemu graczowi z drużyny przeciwnej. Jeśli Box wygra, każdy z przeciwników płaci jemu. Gracze mogą przyłączać i odłączać się od gry w dowolnym momencie. Gracz przyłączający się do gry zawsze siada na końcu kolejki. W zależności od ustaleń przed rozpoczęciem gry drużyna może lub nie może konsultować ruchy wykonywane przez Kapitana. Często gracze decydują się na kompromis w postaci konsultacji tylko po użyciu kostki dublującej. Kolejna dowolność ustaleń dotyczy ilości kostek dublujących w grze. Może to być jedna kostka. Wtedy drużyna ma prawo rozważać indywidualnie tylko duble zaoferowane przez Boxa. Natomiast oferty podwojenia ze strony drużyny leżą w wyłącznej gestii Kapitana. Jeśli Box podwaja, każdy z graczy może indywidualnie zdecydować, czy przyjmie czy odrzuci dubla. Ci, którzy odrzucą, wypłacają Boxowi należną stawkę i nie biorą udziału w dalszej części gry. Jeśli Kapitan odrzuci dubla, a wśród graczy znajdą się tacy, którzy przyjmą podwojenie, Kapitan zostanie przeniesiony na koniec kolejki i utraci stanowisko kapitańskie na rzecz jednego z pozostających w grze graczy. W przypadku, gdy tylko jeden z graczy chce przyjąć podwojenie Boxa, a w grze jest minimum pięciu graczy przeciwko Boxowi, to większość graczy wymusza decyzję i pojedynczy głos, chcący przyjąć dubla się nie liczy a drużyna rezygnuje. Inna popularna zasada mówi, że pojedyczny gracz, który chce przyjąć dubla Boxa, musi też przyjąć dodatkową kostkę dublującą o wartości 2 od dowolnego gracza drużyny, który chce mu zapłacić stawkę za jeden punkt. Gracz przyjmujący staje się teraz właścicielem dwóch kostek dublujących, których może użyć indywidualnie do kontrowania i jeśli wygra, zdobędzie stawkę za obydwie kości, a jeśli przegra, będzie musiał zapłacić podwójnie. W Sowę można też grać z większą ilością kostek dublujących. Każdy gracz z drużyny posiada wtedy własną kostk. Box może zaproponować dubla każdemu z graczy osobno i każdy z graczy może indywidualnie podjąć decyzję, kiedy zaproponować podwojenie Boxowi. Przy większej ilości kostek dublujących możliwe są sytuacje, gdzie Box wygrywa przeciw niektórym graczom, a przegrywa z innymi. Pojawia się pytanie, kiedy Box traci swoją pozycję? Naturalnie tylko wtedy, gdy przegra z Kapitanem. Każdy klub lub stowarzyszenie opracowuje swoje własne szczegółowe zasady gry w Sowę. Przy planowaniu rozgrywek Sowy, można m.in. skorzystać z zasad opracowanych przez Stowarzyszenie Backagammona z Atlanty (Atlanta Backgammon Association).

    Kawałek po kawałku - drugi album muzyczny grupy Goya z roku 2003. Promowały go trzy single: Będę się starać, Jeśli będę taka oraz piosenka tytułowa Kawałek po kawałku. Player versus player (PvP; ang. gracz kontra gracz, gracz na gracza, GnG) – rodzaj interakcji w grach typu MMORPG, MUD, RPG pozwalającej na rywalizację pomiędzy dwoma lub więcej graczami. PvP niekoniecznie polega na zabiciu postaci innego gracza. Są różne rodzaje PvP, np. urozmaicające rozgrywkę i nadanie klimatu gry (World of Warcraft, Lineage itp.) oraz na większą skalę, gdzie rywalizuje ze sobą wielu graczy o różne nagrody (Guild Wars, World of Warcraft).

    Czwórki (en. Connect Four) – planszowa gra logiczna dla dwóch osób, w której wykorzystuje się planszę o wymiarach 7 x 6 pól. Pierwszy gracz wrzuca swój żeton do wybranej przez niego kolumny. Żeton zajmuje najniższą pozycję. Gracze wrzucają swoje żetony na przemian, aż jeden z nich ułoży cztery żetony w poziomie, pionie lub ukosie. Wygrywa ten gracz, który zrobi to jako pierwszy. Jeżeli natomiast plansza się zapełni, a nie utworzy się żadna czwórka, jest remis. Gra jest też znana jako 4 wygrywa, four. Kolekcjonerskie gry karciane (pot. karcianki, z ang. collectible card games (CCG) lub trading card games (TCG)) – gry, w których każdy z graczy korzysta z osobistej talii specjalnie przeznaczonych dla danej gry kart. Gra jest dwu- lub wieloosobowa.

    Gry bitewne – odmiana standardowych gier planszowych. Gracze dysponują określoną liczbą różnych jednostek. Rozgrywka dzieli się na tury, w trakcie których gracze w ustalonej kolejności wykonują ruchy. Każdy rodzaj jednostki dysponuje odmiennymi atrybutami, takimi jak szybkość poruszania się (zależy od niej zazwyczaj odległość ruchu), szansa obrony, szansa na atak oraz obrażenia. Kwestie losowe rozstrzygane są za pomocą przypisanego do danej gry rodzaju kostek. W niektórych grach poszczególne postacie tego samego rodzaju różnią się umiejętnościami, zdobywanymi w trakcie walki.

    Handicap w golfie amatorskim (HCP) to wyrównanie szans, polegające na dodaniu określonej liczby uderzeń (liczba całkowita) w rozgrywce, wynikających z parametrów pola oraz handicapu dokładnego gracza (podawanego z dokładnością do 0,1).

    Postać gracza lub bohater gracza – osoba lub istota, w którą wciela się gracz podczas sesji gry fabularnej lub komputerowej. W grze fabularnej bohater od początku jest tworzony przez kierującego nim gracza – dotyczy to wyglądu, stylu ubierania, mówienia, a często także samej przeszłości i znajomości. W trakcie gry gracz steruje poczynaniami bohatera, podejmuje za niego wszystkie decyzje i kreuje jego osobowość. Zazwyczaj postać gracza, o ile nie ginie w trakcie sesji, jest przez długi czas odgrywana przez danego gracza, czasami w różnych kampaniach i u różnych mistrzów gry. Pozostałe postacie, w które wciela się mistrz gry nazywane są bohaterami niezależnymi. Podczas terenówek i LARP-ów gracze stosują charakteryzację, aby zewnętrznie przypominać odgrywaną postać i przez to pełniej ją wyrażać, a także by lepiej wczuwać się w rolę lub też ułatwiać to innym.

    Dodano: 16.06.2009. 22:50  


    Najnowsze