Bitwa, czyli problem zgranego w czasie ataku

[cardemon]

Bardzo, bardzo dawno temu, kiedy jeszcze Aleksander Wielki walczyl z Persami,
doszlo do takiego zdarzenia: Dwie armie Grekow zajęły skrycie pozycje po
przeciwnych stronach pewnego wzgórza, jakie okupowali Persowie. Obie armie
greckie tak byly wzajemnie ulokowane, ze nie miały ze sobą zadnego kontaktu
(ani wzrokowego ani słuchowego). Grecy pod wodzą Aleksandra Wielkiego
zamierzali następnego dnia zdobyć te wzgórze i zmieść z jej powierzchni armię
perską. By ten plan się powiódł, niezbędne było zgrać dokładnie w czasie
jednoczesny atak na wzgórze z obu stron. Aleksander Wielki postanowił
przesłać swojemu drugiemu wielotysięcznemu oddziałowi po przeciwnej stronie
góry rozkaz, ze atak ma być rozpoczęty następnego dnia o wschodzie słońca.
Jedynym sposobem komunikacji w tamtych czasach byli posłańcy, ktorzy czasami
niestety nie docierali do punktu docelowego z ważną wiadomoscią, jako ze
nieprzyjaciel też nie był w ciemię bity. Aleksander Wielki pchnął więc
posłańca z tą wiadomością: "Atak jutro o wschodzie, potwierdźcie otrzymanie
wiadomości." Wódz drugiej armii greckiej z przeciwnej strony góry otrzymawszy
wiadomość dokładnie wiedział, ze nie moze zaatakować, zanim oddział pierwszy
(Aleksandra Wielkiego) nie uzyska od niego potwierdzenia otrzymania rozkazu.
Natychmiast więc pchnął posłańca w drogę powrotną z wiadomością
treści: "Zrozumiano. Atak jutro o wschodzie słońca, potwierdźcie otrzymanie
wiadomości." Oddział pierwszy otrzymawszy wiadomość od oddziału drugiego znów
pchnął posłańca z wiadomością, że potwierdzają odbiór, atak jak zaplanowano,
wszystko bez zmian i czekają na potwierdzenie przyjęcia wiadomości. Na to
odział drugi wysłał posłańca, ze wiadomość została przyjęta, prosimy o
potwierdzenie wiadomości.... itd., itd.

Czy jest jakiś sposób na to, by obie armie wybrnęły z tego błędnego koła i
rozpoczęły precyzyjnie zgrany w czasie atak na nieprzyjacielskie fortyfikacje
na wzgórzu nazajutrz o wschodzie słońca?

Pozdrowienia dla wszystkich łamigłówkowiczów,

CdM

Pytanie

[grzk]

cardemon napisał:

> Jedynym sposobem komunikacji w tamtych czasach byli posłańcy, ktorzy czasami
> niestety nie docierali do punktu docelowego z ważną wiadomoscią, jako ze

Rozumiem, że rozwiązanie musi spełniać powyższy warunek, czyli nie wchodzi w
rachubę przekazanie informacji w inny sposób niż przez posłańca?

pozdrawiam
grzk

[cardemon]

grzk napisał:

> cardemon napisał:
>
> > Jedynym sposobem komunikacji w tamtych czasach byli posłańcy, ktorzy czasa
> > mi niestety nie docierali do punktu docelowego z ważną wiadomoscią, jako ze

> Rozumiem, że rozwiązanie musi spełniać powyższy warunek, czyli nie wchodzi w
> rachubę przekazanie informacji w inny sposób niż przez posłańca?

Hmm, nie wiem, co odpowiedziec. Z jednej strony chce sztywno trzymac sie tego
poslanca, bo jest on bardzo istotnym elementem tej zagadki, a w szczegolnosci
mozliwosc, ze zostanie pojmany lub zabity przez wroga, z drugiej strony jednak
bardzo ciekawi mnie jak bys wybrnal z sytuacji bez poslanca.

pzdr. CdM

[Gość: johndoe]

nie wiem na ile to rozwiazanie spelnia zalozenia pana CdM, ale:) :
perwsza wiadomosc mglaby brzmiec:
"atak o swicie, jezeli nie otrzymamy potwierdzenia to robimy zwiad bojem na godzine przed switem"

halas przy zwiadzie bylby /sadze/ wystarczajacy, aby ostrzec druga grupe, jednak to rozwiazanie wyklucza atak z zaskoczenia w innym terminie i jest malo humanitarne:).
ps. poza tym brak mu finezji
pzr

[cardemon]

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

> perwsza wiadomosc mglaby brzmiec:
> "atak o swicie, jezeli nie otrzymamy potwierdzenia to robimy zwiad bojem na
> godzine przed switem"

Nie moge sie zgodzic z tym rozwiazaniem. Po pierwsze brak w nim elementu
zaskoczenia, po drugie jednak jeden z oddzialow atakuje pierwszy (niewazne, ze
tylko malym oddzialem zwiadowczym).

pzdr. CdM

[Gość: johndoe]

cardemon napisał:

> Gość portalu: johndoe napisał(a):
>
> > perwsza wiadomosc mglaby brzmiec:
> > "atak o swicie, jezeli nie otrzymamy potwierdzenia to robimy zwiad bojem n
> a
> > godzine przed switem"
>
> Nie moge sie zgodzic z tym rozwiazaniem. Po pierwsze brak w nim elementu
> zaskoczenia, po drugie jednak jeden z oddzialow atakuje pierwszy (niewazne, ze
> tylko malym oddzialem zwiadowczym).
>
> pzdr. CdM
po "zwiadzie bojem" atak juz nie nastapi; taki mial byc sens wiadomosic przekazanej przez poslanca, wiec albo poslaniec dotrze, bedzie odpowiedz i atak nastapi o siwcie, albo poslaniec lub drugi z odpowiedzia nie dotrze i nastapi tylko "zwiad bojem" /druga armia nie zaatakuje/. kosztuje to kilkadziesieciu zolnierzy, niemoznosc ataku z askoczenia itd...
co nie zmienia faktu, ze brak tu finezji:)

Jeszcze raz problem skoordynowanego ataku.

[cardemon]

Sprobuje jeszcze raz opisac caly problem, moze bedzie on tym razem bardziej
zrozumialy.
Dwa oddzialy duzej armii rozlokowaly sie po dwoch przeciwnych stronach pozycji
nieprzyjaciela. Sily wroga zostana tylko wtedy rozbite, jesli do bitwy
przystapia rownoczesnie z dwoch stron oba oddzialy. Jesli tylko jeden oddzial
zaatakuje zostanie on pokonany. Dlatego generalowie obu oddzialow musza
dokladnie skoorodynowac atak. Jedyna komunikacja miedzy obydwoma oddzialami
jest poslaniec, ktory moze byc zlapany lub zabity przez nieprzyjaciela.
Zalozmy, ze general oddzialu A wysyla poslanca do generala oddzialu B z
wiadomoscia "atak o swicie". Czy general B ma zaatakowac? Zauwazmy, ze general
A nie wie, ze wiadomosc dotarla do generala B. Musi wiec rozwazac mozliwosc, ze
wiadomosc nie dotarla, a wiec oddzial B na pewno nie przystapi do bitwy o
swicie. Zatem general A nie da rozkazu do ataku. Wiedzac o tym i nie chcac
ryzykowac samotnego ataku, general B nie moze zaatakowac opierajac sie tylko i
jedynie na wiadomosci dostarczonej przez poslanca. Wiec general B wysyla
poslanca do A z potwierdzeniem otrzymania wiadomosci o ataku o swicie. Tym
niemniej, nawet jesli poslaniec dotrze do A, to z podobnych co wyzej
przedstawionych powodow, ani general A ani general B nadal nie zdecyduja sie na
przypuszczenie ataku o swicie, itd. itd.
Czy jest jakis sposob, by wybrnac z tego blednego kola?

CdM

[reptar]

Intrygujące zagadnienie. Na razie nie wiem.

Ale przychodzą mi do głowy różne takie quasi-rozwiązaniowe (a już na pewno nie
logiczne) pomysły:

1) posłaniec idzie, a w obozie zostaje jego bliźniak jednojajowy; czytałem
kiedyś - oczywiście obok wywiadu z dwugłową kobietą :)   - że niektóre
pary takich bliźniaków są tak mocno ze sobą związane emocjonalnie,
że nawet jak jeden mieszka w Kanadzie, a drugi w Australii, to i tak
nie porozumiewając się ze sobą żenią się tego samego dnia i o tej samej
godzinie, i jeszcze panny młode są do siebie łudząco podobne.

2) nitka Ariadny - przeciągnięta oczywiście przez posłańca.

[Gość: Andy]

reptar napisał:

> Intrygujące zagadnienie.
Zgadzam się, ale zanim się w nim pogrążę mam 2 pytania:

1. Czy autor zna rozwiązanie?
2. Czy ma być ono stuprocentowe - to znaczy dające pewność podjętych decyzji
niezależnie od prawdopodobieństwa powodzenia misji posłańca (-ów)?

Pozdr. A.

[cardemon]

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

> 1. Czy autor zna rozwiązanie?
> 2. Czy ma być ono stuprocentowe - to znaczy dające pewność podjętych decyzji
> niezależnie od prawdopodobieństwa powodzenia misji posłańca (-ów)?

Wydaje mi sie, ze wiem wszystko (no moze prawie wszystko) o tym zagadnieniu. Na
szczescie moge sie tez podeprzec poważną literatura naukową i będę slużył
odpowiednim odnosnikiem (angielskojęzycznym) na koncu tego watku. Cale
zagadnienie nie jest wcale banalne i przyznaję, ze jest to w pewnym sensie
perfidia z mojej strony, ze je zamiescilem na tym forum, bowiem zajmowali się
nią niejedni profesjonalisci z prawdziwego zdarzenia. Caly problem mozna bowiem
odniesc do komunikacji miedzy dwoma mikroprocesorami. Tym niemniej uznalem tę
zagadke za bardzo intrygujaca i mialem nadzieje, ze moze przynajmniej niektorzy
forumowicze tez tak beda sadzic... :)

pzdr. CdM

[reptar]

cardemon napisał:

> Wydaje mi sie, ze wiem wszystko (no moze prawie wszystko) o tym zagadnieniu.



Hm... czy można zatem prosić o podpowiedź?
Czy koncentrować się bardziej na wymyśleniu odpowiedniego komunikatu, czy na
sposobie poruszania się posłańców (o ile liczba mnoga jest tu dozwolona)?

[Gość: Andy]

Odpowiedż CdM jest nieco wymijająca. Oczekiwałem odpowiedzi TAK/NIE na
postawione 2 pytania.
W mikroprocesorach prawdopodobieństwo "niedotarcia posłańca" jest w
praktycznych systemach dość małe, stąd moje drugie pytanie.
Pozdr. A.

Przemyślenia weekendowe

[grzk]

Moim zdaniem porównanie do systemów mikroprocesorowych wszystko wyjaśnia.
Niech p oznacza prawdopodobieństwo tego, że posłaniec nie dojdzie. Wbrew temu
co pisał Andy prawdopodobienstwo to wcale nie musi być małe (wyobraźmy sobie
dwa systemy połączone linią satelitarną). W systemach telekomunikacyjnych
zwykle stosuje się w takim przypadku tzw retransmisję prewencyjną (oczywiście w
dużym skrócie - nie chcę wdawać się w dyskusję o kodach transmisyjnych itp),
czyli wysyłamy nie jednego, ale kilku posłańców.
W naszym zadaniu prawdopodobieństwo, że wiadomość nie dotrze do celu wynosi
wtedy p^(n) < p. Po dojściu pierwszego posłańca druga armia wysyła
potwierdzenie (również n-krotnie). Decyzji wodzów zostawiam określenie ilości
posłańców jaka da im satysfakcjonujące p-stwo przekazania informacji. Na tym
bym zakończył konwersację obu armii, gdyż dalsza wymiana posłańców już niczego
nie wnosi.
Uff, to tyle teraz trzeba ;)
popracować

pozdrawiam grzk

[Gość: Andy]

Zgoda - stąd moje pytanie numer 2 do CdM.
Jeśli chcemy mieć PEWNOŚĆ synchronizacji (a tak chyba sugeruje treść zagadki),
to problem jest nadal otwarty.

Pozdr, A.

[reptar]

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

> Zgoda - stąd moje pytanie numer 2 do CdM.
> Jeśli chcemy mieć PEWNOŚĆ synchronizacji (a tak chyba sugeruje treść
> zagadki), to problem jest nadal otwarty.



No i wciąż ten brak finezji..., suche prawdopodobieństwo :(

[cardemon]

Niestety musze odrzucic pomysly z telepatią i nitką Adrianny. Nie moge tez sie
zgodzic na odpowiedz Grzk "dalsza wymiana posłańców już niczego nie wnosi", no
wlasnie wnosi, bo ktoras ze stron nie bedzie miala 100% pewnosci, co spostrzegl
rowniez Andy.

Chyba pomalu bede sie wycofywal z tej zagadki, a forumowiczom nie radze sie nad
nia wiecej głowić. Natomiast jak czas zezwoli, to napisze wiekszy komentarz do
tego zagadnienia pod koniec tygodnia.

Pozdrowienia dla wszystkich,
CdM

[Gość: Andy]

cardemon napisał:

> Niestety musze odrzucic pomysly z telepatią i nitką Adrianny.
Jeśli już idziemy w takich kierunkach to nasuwa mi się wykorzystanie splątania
kwantowego. Trochę o tym pisano ostatnio w publikacjach popularno-naukowych,
ale chyba daleko jeszcze do jakiejkolwiek praktyki "natychmiastowej
synchronizacji na odległość" chociaż laboratoryjnie podobno się udaje. Poza tym
trochę to nie pasuje do realiów antycznych i mam wątpliwości czy nie łamie
założenia, że jedyną formą komunikacji są posłańcy.
Bo teoretycznie wyglądałoby to tak (w moim wyobrażeniu laika, może niech fizycy
porawią):
Splątujemy jakąś chmurkę atomów i co jakiś czas wysyłamy posłańca z kawałkiem
takiej chmurki. Jeśli którykolwiek dotrze do celu to odbiorca nie musi nic
potwierdzać tylko zmienia stan odebranego kawałka (co oznacza atak o świcie) a
pozostała część chmurki (i inne pobrane kawałki) natychmiast(!?) zmieniają swój
stan, skąd nadawca wie, że też może zatakować o świcie.
Pozostaje odpowiedż na filozoficzne pytanie, czy komunikacja odbyła się jedynie
za pomocą posłańca, czy też jakąś inna tajemniczą fizyczną drogą, bo nie mam
wątpliwości,że gdyby to były np. fale radiowe to uznalibyśmy to za nielegalny
dodatkowy sposób komunikacji.
Pozdr. A.

[cardemon]

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

> Jeśli już idziemy w takich kierunkach to nasuwa mi się wykorzystanie
> splątania kwantowego. Trochę o tym pisano ostatnio w publikacjach popularno-
> naukowych, ale chyba daleko jeszcze do jakiejkolwiek
> praktyki "natychmiastowej synchronizacji na odległość" chociaż laboratoryjnie
> podobno się udaje. (...)

Dzieki Andy za ten komentarz jak i za Twoj poprzedni:

> Zgoda - stąd moje pytanie numer 2 do CdM. Jeśli chcemy mieć PEWNOŚĆ
> synchronizacji (a tak chyba sugeruje treść zagadki), to problem jest nadal
> otwarty.

I jeszcze dzieki za poprzedni z 04-10-2002 10:18 ... (wszystkie bardzo celne!)

We wszystkich komentarzach masz absolutna racje! Pozwol, ze odpowiem dzis, a
szerszy komentarz napisze jak czas pozwoli, czyli pewno dopiero w najblizszy
weekend.

Te zadanie NIE MA ROZWIAZANIA! Ot taki sobie "drobny paradoks"...

pzdr. CdM

Odpowiedz - Re: Bitwa, czyli problem ...

[cardemon]

Wiem, za bardzo zalegam z odpowiedzia na ten problem, ale z drugiej strony
zdaje sobie tez sprawe z tego, ze by moc dokladnie opisac calosc zagadnienia,
potrzebny jest przynajmniej drobny esej. Przypominam, ze zagadnienie nie ma
rozwiazania, a to na skutek braku PEWNOSCI w komunikacji obu stron. Pisalem tez
juz wczesniej o pewnej perfidii z mojej strony, polegajacej na tym, ze w ogole
przedstawilem te zagadnienie na tym forum, gdzie maja goscic przede wszystkim
zagadki łatwe i przyjemne (czyz nie tak?). Tym niemniej jak widzicie pozwolilem
sobie na zaprezentowanie tego problemu, bo uwazam, ze jest to bardzo ciekawy i
intrygujacy paradoks (w pewnym sensie zahaczajacy tez o zagadnienie ujete w
poscie Kopperka pt."Król, mędrcy, dziura w całym" -
www2.gazeta.pl/forum/794674,30353,794652.html?f=514&w=2529525 z 23-07-
2002 23:31). Obydwaj generalowie wiedza o czasie i miejscu planowanej akcji, a
tymczasem nie moga podjac zadnego dzialania, bo nie maja CALKOWITEJ pewnosci co
do dzialan sil sprzymierzonych. Historia tego problemu siega roku 1978, kiedy
J. Gray - pracownik firmy IBM - po raz pierwszy go sformulowal. Rozwiazanie, a
raczej indukcyjny dowod na brak takowego, przedstawili 12 lat pozniej dwaj
matematycy Halpern i Moses; jeden z Cornell University New York, drugi z
Instytitute of Haifa. Wszystkich ciekawych dowiedziec sie czegos wiecej z
przyjemnoscia odsylam do dostepnej w sieci publikacji tychze autorow, niestety
(lub raczej oczywiscie) w jęz. angielskim (i w formacie pdf - jak nie masz to
sciagnij sobie Adobe Acrobata z www.adobe.com):
www.almaden.ibm.com/cs/people/fagin/apal99.pdf.
Oczywiscie nie traktuje tego zagadnienia jako zamkniete i bardzo chetnie
podejme kazda dyskusje na ten temat.

CdM

PS. Jesli o Aleksandra Wielkiego i jego podboje chodzi, to ponoc zdawal on
sobie sprawe z tego problemu i mial na te okolicznosc opracowana przez
alchemikow chemiczna metode koordynacji ataku z kilku stron jednoczesnie.
Metoda ta polegala na reakcji dwoch okreslonych chemicznych skladnikow,
poprzez zanurzenie tkaniny nasiaknietej jednym skladnikiem w roztworze drugiego
skladnika. Po prostu wszyscy dowodcy spotykali sie w jednym
miejscu, "uaktywniali" swoje "chemiczne zegary", po czym ulokowywali sie ze
swoimi oddzialami na odpowiednich pozycjach i w koncu atakowali, jak zaszla
barwna reakcja.

Odpowiedz - Re: Bitwa, czyli problem ...

[cardemon]

cardemon napisał:

(...)
> www.almaden.ibm.com/cs/people/fagin/apal99.pdf.
(...)

Wlasnie zauwazylem, ze ten link nie dziala. Dlugo sie glowilem dlaczego (to tez
byla swego rodzaju łamigłówka!:)), az w koncu doszedlem do wniosku, ze
wszystkiemu winna ta kropka na koncu. Bierzcie wiec ten link:

www.almaden.ibm.com/cs/people/fagin/apal99.pdf

Bez kropki na koncu (tylko pamietajcie, ze musicie miec na kompie
zainstalowanego Adobe Acrobata, ktory jest za friko)!

Uff, Cdm :)