Problem rozbieżności Erdősa

Wyobraźmy sobie, że mamy kierować armią robotów. Roboty są bardzo proste, ponieważ rozumieją tylko dwie komendy: na komendę „naprzód” robot robi krok do przodu, na komendę „wstecz” tej samej długości krok do tyłu. Każda nasza komenda dociera do wszystkich robotów, nie możemy więc kierować tylko pojedynczym. Roboty różnią się jednak „karnością”: tylko pierwszy z nich wykonuje posłusznie każdy otrzymany rozkaz. Drugi wykonuje tylko co drugi rozkaz, pozostałe ignoruje. Trzeci robot jest jeszcze bardziej leniwy i wykonuje tylko co trzecią komendę, ignorując pozostałe. I tak dalej, n-ty robot wykonuje co n-tą komendę. Ponadto roboty nie mogą się nadmiernie oddalać od linii startowej, jeżeli któryś odejdzie od niej o zbyt wiele kroków, niezależnie do przodu czy do tyłu, traci łączność i jest uważany za utraconego. Pytanie brzmi: jak mamy kierować robotami, jakie rozkazy wydawać, by żaden nie uciekł nam za daleko? Czy to się w ogóle da zrobić? A może odpowiedź zależy od tego, jak daleko pozwalamy robotom odejść? Continue reading „Problem rozbieżności Erdősa”

Reklamy