Przeskocz do treści

Delta mi!

Wielkie granie

Matematyczne wyścigi

Zofia Miechowicz

o artykule ...

  • Publikacja w Delcie: styczeń 2011
  • Publikacja elektroniczna: 20-12-2010
  • Autor: Zofia Miechowicz
    Afiliacja: Wydział Matematyki, Informatyki i Ekonometrii, Uniwersytet Zielonogórski

Nie będzie chyba zbyt śmiałym stwierdzeniem, jeżeli napiszemy, że matematycy uwielbiają gry. Zarówno takie, które można badać pod kątem matematycznym, jak i takie, w które się po prostu przyjemnie gra.

obrazek

Jeżeli znajdziemy grę o prostych zasadach, w której rozgrywka stanowi prawdziwe wyzwanie intelektualne, a do tego, by w nią grać, wystarczy zwykła kartka papieru i coś do pisania, możemy śmiało powiedzieć, że mamy grę idealną. Martin Gardner w jednej ze swoich książek przedstawił grę spełniającą wszystkie powyższe wymagania (co więcej, dającą się badać matematycznie). Grę „przywiózł” z podróży do Szwajcarii znajomy Gardnera, Jurg Nievergelt, informatyk z Uniwersytetu Illinois. Jest to prosta w formie, a zupełnie niebanalna, jeżeli chodzi o rozgrywkę, symulacja wyścigów samochodowych, przez Gardnera nazywana RaceTrack. Planszę stanowi kartka w kratkę z wyrysowaną trasą dowolnego kształtu (zob. rysunek). Na początku gry samochody wszystkich graczy (punkty, najlepiej w różnych kolorach) ustawione są na linii startu. Gracze przemieszczają swoje pojazdy między punktami kratowymi naprzemiennie, według wcześniej ustalonej kolejności (na przykład przez losowanie), oraz stosując się bezwzględnie do trzech następujących zasad:

math
nowy punkt kratowy, w którym staje samochód, oraz odcinek łączący go z poprzednim muszą w całości leżeć na trasie,
math
w każdym momencie gry w każdym punkcie może stać co najwyżej jeden pojazd,
math
jeżeli w swoim poprzednim ruchu gracz przesunął się o  math kratek w pionie i  math  w poziomie, to w kolejnym ruchu każdą z tych liczb może zmniejszyć lub zwiększyć co najwyżej o jeden (w pierwszym ruchu można się przesunąć co najwyżej o jedną kratkę do góry i jedną w bok, gdyż uprzednio samochód stał w miejscu).

Jak to zwykle w przypadku wyścigów bywa, wygrywa ten z graczy, który pierwszy przekroczy linię mety. Kierowca, który wypadnie z trasy lub zderzy się z innym pojazdem, kończy wyścig. Szerokiej drogi!


Do czytania
1.
M. Gardner, Sim, Chomp, and RaceTrack, w: Knotted Doughnuts
and Other Mathematical Entertainments, W.H. Freeman and Company, New York, 1986, 56–57.
2.
M. Holzer, P. McKenzie, The Computational Complexity of RaceTrack, Fun with Algorithms, 2010.