Pajaki na czworoscianie

[pulbek]

Bylo? To posluchajcie.

Po krawedziach czworoscianu foremnego chodza trzy pajaki i mucha. Pajaki,
wiadomo, gonia muche. Problem w tym, ze niedowidza - dostrzegaja muche
dopiero wtedy, kiedy ja zlapia. W dodatku mucha jest jasnowidzem i zawsze
wie, ktoredy beda szly pajaki. Pajaki maja tylko jedna przewage: chodza
_minimalnie_ szybciej od muchy.

Pytanie: jaka strategie powinny przyjac pajaki, zeby na pewno zlapac muche?

Pulbek.

[Gość: pafcio]

wg mnie pająki powinny wyjść z 1 wierzchołka w kierunku 3 innych i po ich
osiągnięciu rzucić monetą który z nich bedzie szedł spotkać się z drugim lub
trzecim. pewności nie ma ale po dość dużej liczbie prób można będzie prawie na
pewno powiedzieć, że mucha została złapana;)
pzdr

[pulbek]

Gość portalu: pafcio napisał(a):

> wg mnie pająki powinny wyjść z 1 wierzchołka w kierunku 3 innych i po ich
> osiągnięciu rzucić monetą

Nic z tego. Mucha zawsze wie, co wypadnie. Jasnowidz.

Pulbek.

Złapały!

[stomek]

Uff! Cieżko było. W sumie liczba kroków jest rzędu (3 * a / e) gdzie a to
długość krawędzi, a e to dystans, który pająk zyskuje nad muchą na odcinku a.
Na koniec mucha zostanie uwięziona na jednej krawędzi, z jednej strony bedzie
miała jednego pająka, a z drugiej dwa.
Na razie nie pisze szczegółów - pobawcie się sami.

pozdrawiam,
Tomek

[pulbek]

> Na razie nie pisze szczegółów - pobawcie się sami.

Slusznie, niech sie pobawia, a dla Ciebie, skoro rozwiazales, mam inny problem,
nad ktorym biedze sie juz dluzszy czas.

To zadanie, wyrazone w jezyku grafow, mowi o klice K4, co nie? Jezeli wezmiesz
dowolna klike Kn, to n pajakow wystarczy do zlapania muchy (nawet gdyby nie
chodzily szybciej). Pytanie: czy wystarczy n-1 pajakow? Nie umiem tego rozwiazac
juz dla n=5. Moze Ty dasz rade?

Pulbek.

[stomek]

Czy chodzi o to żeby pokazać:
1) że n-1 pająków nigdy nie wystarczy jeśli nie będą chodziły szybciej?
2) że n-1 pająków zawsze wystarczy jeśli będą chodziły szybciej?
Jeśli chodzi o pytanie 1 to wydaje się, że nie wystarczy. Już dla K4 to widać i
raczej dla większych będzie tak samo. Żeby to faktycznie udowodnić trzeba jednak
podać strategię muchy.
Jeśli chodzi o pytanie 2 to nie wiem, ale jest interesujące.

pozdrawiam,
Tomek

[pulbek]

> 2) że n-1 pająków zawsze wystarczy jeśli będą chodziły szybciej?

Chodzilo oczywiscie o to! :-)

[Gość: pafcio]

możesz pokazać jak to rozwiązać? dzieki...

[stomek]

Gość portalu: pafcio napisał(a):

> możesz pokazać jak to rozwiązać? dzieki...

Obiecuję, że przedstawię na forum pełne rozwiązanie,
ale niestety dopiero za pewien czas.
Teraz mam pełno roboty, a ponadto zaczyna się
na portalu Gazety konkurs "Pogromcy algorytmów",
w którym będę startował.
Napisanie rozwiązania dla pająków, które będzie
proste do zrozumienia to nie jest praca na 10 minut.

Tomek

[Gość: pafcio]

dzięki

[grzk]

W międzyczasie podam mój pomysł:
oznaczmy wierzchołki czworościanu 1,2,3,4. Można to zrobić w dowolny sposób, ja
przyjąłem, że wierzchołki 1,2,3 leżą na podstawie.
Trasy dla pająków:
A:3,4,2
B:3,1,4
C:4,1,2
Uzasadnienie jest takie, że przy jednakowej prędkości muchy i pająków mucha ma
tylko jedną możliwą drogę by będąc w dowolnym wierzchołku nie być złapaną w
kolejnym kroku.
Dowodu formalnego nie będzie ;)
pzdr
Grzegorz