Delta mi!

Rozważamy tutaj gry z udziałem dwóch graczy, którzy podczas rozgrywki mają pełną informację na temat tego, co dzieje się na planszy. Każda gra ma ściśle określone reguły, w tym cel. Gracz, który jako pierwszy go osiągnie, wygrywa, a jego przeciwnik przegrywa, przy czym nie musi być to ten sam cel dla obu graczy.

W pewnym zakładzie karnym przebywa stu skazanych, ponumerowanych liczbami od 1 do 100: Strażnik zaproponował im następującą grę: sto kartek z ich numerami umieszcza w stu skrytkach, po jednej kartce w każdej skrytce. Sposób rozmieszczenia kartek nie jest znany więźniom. Następnie strażnik pozwala każdemu z więźniów sprawdzić dokładnie połowę skrytek. Sprawdzający wchodzi do pokoju ze skrytkami sam, a po swojej turze musi zostawić pokój w stanie nienaruszonym i jedynie poinformować nadzorcę, czy odnalazł swój numer, czy też nie. Nie komunikuje się później z pozostałymi więźniami. Osadzeni wygrywają wyjście na wolność wtedy i tylko wtedy, gdy każdy z nich zdoła odnaleźć swój numer. Jaka jest szansa na to, że im się to uda?

Poprzez triangulację będziemy rozumieć podział figury na trójkąty (Rys. 1). W dalszej części artykułu będziemy zajmować się kolorowaniem wierzchołków triangulacji pewnego trójkąta...

W dniach 9-21 września 2018 r. odbyła się trzecia edycja międzynarodowego obozu Maths Beyond Limits . 60 uczestników z Białorusi, Belgii, Czech, Danii, Estonii, Norwegii, Polski, Rumunii, Słowacji, Szwecji, Ukrainy i Węgier wzięło udział w warsztatach matematycznych prowadzonych przez studentów i pracowników naukowych polskich i zagranicznych uczelni. Mieli oni także okazję do zaprezentowania własnych referatów oraz do uczestnictwa w ogólnorozwojowych zajęciach wieczornych. Ponadto, w czasie obozu odbyły się: mecz matematyczny, zawody Relays (oparte na konkursie Náboj), Puzzle Hunt, a także zajęcia sportowe i integracyjne.

Conway's Soldiers to jednoosobowa łamigłówka, w której żołnierze (pionki) przedostają się na terytorium wroga i chcą wkroczyć jak najdalej. Na nieskończonej szachownicy, z zaznaczoną "na środku" poziomą granicą, pionki przeskakują jeden nad drugim. Dokładniej: ruch polega na przeskoczeniu pionkiem nad innym znajdującym się na sąsiadującym polu - tylko poziomo lub pionowo - i zdjęciu pionka, który został przeskoczony.

Czy można ograć kasyno? Nałogowi gracze zastanawiają się nad tym problemem od dawna. Wszystkie gry w kasynie mają ujemną wartość oczekiwaną dla klienta. Przynajmniej tak się ludziom wydawało aż do lat 60., kiedy ukazało się kilka książek o tym, jak można, stosując odpowiednią strategię, uzyskać dodatnią wartość oczekiwaną w grze Blackjack. To ogromnie spopularyzowało grę i paradoksalnie okazało się korzystne dla branży hazardowej. Mechanizm został przedstawiony w filmie "21", jednak bez żadnych szczegółów. W tym artykule przedstawię dokładniej, jak ta strategia działa.

W wielu grach dla któregoś z graczy istnieje strategia wygrywająca, czyli taka "recepta" na grę, która pozwala zawsze zwyciężyć, niezależnie od ruchów przeciwnika. Jednak strategię taką, nawet jeśli istnieje, nie zawsze łatwo wskazać. Na szczęście często można. Czasem wystarczą do tego proste pomysły typu symetria, czasem zaś potrzebne są metody bardziej wyrafinowane. W niektórych grach nawet bez żadnej strategii wynik jest z góry przesądzony. Ilustrują to poniższe przykłady...

Gra Black rozgrywana jest przez dwóch graczy (I - rozpoczynającego i II) na prostokątnej planszy podzielonej na kwadratowe pola jednostkowe; każdy z wymiarów planszy jest większy od 2...

Czy Czytelnik zna grę w przeciąganie liny? Dwie drużyny ciągną dwa końce liny w przeciwne strony, a wygrywa ta, której uda się przeciągnąć linę na swoją stronę. Ściślej, gra kończy się w momencie wyjścia środka liny (zazwyczaj oznaczonego wstążką) z umówionego pola gry. Matematycy przypisują tę samą nazwę podobnej grze rozgrywającej się w dwóch (i więcej) wymiarach, w której to środek liny może poruszać się w wielu kierunkach, a nie tylko lewo-prawo. Trudno sobie jednak takie przeciąganie wyobrazić, dlatego przyjąłem termin gra w sumo.

Jedna z rzeczy, które trudno wytłumaczyć niematematykom, to dowody niekonstruktywne. W takim dowodzie autorzy dochodzą do wniosku, iż pewien obiekt matematyczny istnieje, często wiedząc o nim bardzo mało. Dzieje się tak dlatego, że stwierdzamy istnienie takiego obiektu, nie próbując go skonstruować, tylko powołując się na inne fakty. Jednym z najprostszych przykładów jest dowód przez "kradzież strategii", który pokażę na przykładzie prostej gry.

Mimo licznych działań skierowanych na zwalczanie terroryzmu wiele organizacji terrorystycznych wciąż się powiększa. Aby poradzić sobie z tym problemem, agencje bezpieczeństwa poszukują nowych sposobów analizy pozwalających lepiej zrozumieć strukturę tych organizacji. Jednym z problemów jest zidentyfikowanie kluczowych członków organizacji terrorystycznej przy użyciu informacji jedynie o tym, jak wygląda sieć terrorystyczna - dzięki temu agencje bezpieczeństwa mogłyby skupić swoje ograniczone zasoby na tych jednostkach. W tym artykule omówimy nowe podejście do tego problemu oparte na teorii gier.

Zamiast analizować, czy gra jest sprawiedliwa, czy nie, zamiast szukać najlepszych strategii graczy, można stworzyć pewną maszynę, która część tej pracy wykona za nas. Trzeba jej objaśnić zasady, a potem z nią grać, niekoniecznie najlepiej - w końcu jeszcze nie przeanalizowaliśmy gry. Maszyna, grając, zapamiętując i wyciągając wnioski z przegranych oraz wygranych (co śmiało można zakwalifikować jako uczenie się), prędzej czy później zorientuje się, jak grać możliwie najlepiej, a więc ogrywać nas, o ile to tylko możliwe.

Na stole leżą, ułożone w losowej kolejności koszulkami do góry, trzy karty: As, Król i Dama. Jeżeli gracz odgadnie prawidłowo położenie Asa, wygrywa dużą nagrodę. Gracz wskazał kartę, nie obejrzał jej, i wtedy prowadzący grę mówi: Chwileczkę. Odkryję jedną z dwóch pozostałych kart, a ty się zastanów, czy chcesz zmienić swoją kartę na kartę, która pozostała nieodkryta.

Zwykła moneta często okazuje się doskonałym narzędziem do rozstrzygania konfliktów. Zapewne każdemu zdarzyło się usłyszeć magiczną formułkę "orzeł to, reszka tamto", z reguły będąc przychylnym dokładnie jednemu ze zdarzeń "to" lub "tamto". Takie rozwiązanie jest jednak mało widowiskowe - o ile wzajemne obrzucanie się inwektywami (w celu wytłumaczenia, w jak wielkim błędzie jest strona przeciwna, prezentując zdanie odmienne od naszego) szybko przyciąga publiczność, tak zakończenie sporu przy użyciu jednego rzutu monetą może pozostawić ją z odczuciem niedosytu.

Dylemat społeczny to sytuacja grupy ludzi, w której interes jednostki nie jest zbieżny z interesem grupy - występuje konflikt między interesem prywatnym a zbiorowym. Charakteryzuje się tym, że jeżeli członkowie grupy postąpią zgodnie ze swoimi indywidualnymi interesami, to zyskają mniej, niż gdyby brali przede wszystkim pod uwagę w swoich działaniach interes grupy. Jeżeli jednak wszyscy mieliby postąpić zgodnie z interesem grupy, to osoba, która jako jedyna zmieni decyzję i postąpi zgodnie ze swoim indywidualnym interesem, zyska więcej, niż gdyby działała zgodnie z interesem grupy.

Stado lwic gdzie oraz myśliwy (rozważani jako punkty płaszczyzny euklidesowej) poruszają się z równymi maksymalnymi prędkościami. Kiedy myśliwy ma skuteczną strategię ucieczki przed grupą lwic? Kiedy lwice mają skuteczną strategię pochwycenia myśliwego w skończonym czasie?

Król Chimeryk zaniemógł. Wezwał do swojego łoża trzech synów. „Czas mój się wypełnia, bo choroba moja straszna i lekarstwa na nią nie znam. Jedna jeszcze nadzieja została. Za siedmioma górami i siedmioma lasami mieszka stary pustelnik, który ma wiedzę wielką o wszelakich chorobach i sam rozmaite medykamenty przygotowuje sobie tylko znanymi sposobami. Synowie moi! W waszych rękach moje życie i ostatnia nadzieja na jego przedłużenie.”

Pewnie część czytelników Delty zna grę Nim – zarówno jej zasady, jak i właściwą dla niej strategię wygrywającą. W tym artykule chcemy przedstawić inną grę grafową. Grę o prostych zasadach, ale trudniejszą niż Nim do dokładnego przeanalizowania. Tą grą jest – stworzony przez Jamie Peabody i Karen Willis – Grim. Podamy efektywny sposób orzekania, który gracz ma strategię wygrywającą. Co najciekawsze, można go zastosować do szerokiej klasy tego typu gier dwuosobowych, zawierającej Grima i Nima.

Gra Mastermind jest rozrywką głównie dla gracza odgadującego. Przypomnijmy: musi on ustalić, jaki kod (ciąg czterech kolorowych szpilek) ułożył przeciwnik, posiłkując się odpowiedziami otrzymywanymi na zadawane pytania. Pytania muszą mieć postać „Jak bardzo kod przypomina ciąg X?”, zaś odpowiedzią są dwie liczby: trafień właściwych kolorów na właściwych pozycjach oraz trafień kolorów na pozycjach niewłaściwych (odpowiednio: trafienia celne i niecelne; te pierwsze będziemy też nazywać po prostu trafieniami). Oczywiście chodzi o to, by odgadnąć kod jak najszybciej.

Rozważmy następujący problem, zwany problemem kapeluszy (ang. hat problem). Do pokoju wchodzi  osób i każdej z nich losowo zostaje nałożony niebieski lub czerwony kapelusz. Każdy widzi kapelusze pozostałych osób, ale nie widzi swojego. Żadna komunikacja nie jest dozwolona, z wyjątkiem ustalenia strategii przed rozpoczęciem gry...