Newsgroup: it.hobby.enigmi
Titolo: La mosca e i ragni

Dall'ultimo numero di Archimede, un quesito che non sono ancora riuscito
a risolvere.
Due ragni si trovano in un vertice R di un cubo, mentre una mosca sta in
un vertice M, opposto rispetto a R in una faccia del cubo (cioè M e R
sono vertici opposti di una stessa faccia). I due ragni e la mosca si
possono muovere lungo gli spigoli del cubo con velocità unitaria. In
ogni istante ogni essere è consapevole della posizione degli altri.
Riusciranno i due ragni, coordinando opportunamente i propri movimenti,
a catturare la mosca? (La mosca si considera catturata quando si trova
nella stessa posizione di uno dei due ragni).
Maurizio
-- 
Per rispondermi via e-mail togli l'ovvio.


A primo acchito, direi che si crei una situazione analoga allo stallo 
negli scacchi. Ma ragioniamo.
Per poter catturare la mosca, sarebbe necessario che i ragni possano 
"attaccare" contemporaneamente tutti i vertici del cubo. I vertici sono 
otto; ciascuno dei due ragni ne occupa uno e, se sono su vertici opposti 
(rispetto al cubo) ne controllano altri tre ciascuno. Quindi direi che, 
se i ragni si mettono su vertici opposti controllano tutti i vertici, e 
dovrebbero catturare la mosca. Però non riesco a vedere come i ragni 
possano trovarsi contemporaneamente sui vertici opposti del cubo...


Ma mosca e ragni si muovono sempre contemporaneamente?
Perché se la mosca può aspettare che i ragni si muovano e poi agire di 
conseguenza, e anche considerando che i ragni possano muoversi appena dopo 
la mosca, avendo tutti e 3 la stessa velocità, a me vien da dire che è 
impossibile che la mosca e un ragno si trovino contemporaneamente nello 
stesso vertice, sarà sempre possibile per la mosca muoversi prima che un 
ragno arrivi, e ovunque si muoverà arriverà prima di uno dei ragni.
Bho.

 Bho.
Certo, perché una mosca può muovere sempre su tre vertici, e se due sono 
occupati dai ragni, può sempre fuggire vero il terzo vertice...


Non so, a me era chiaro che hanno velocità uguale, ma non che ci fosse una 
sorta di clock che tutti e 3 seguissero.
E uno può decidere di non fare nulla e rimanere dove si trova? Oppure tutti 
e 3 si devono spostare per forza?

Maurizio Frigeni ha scritto:

le varie bestie possono invertire istantaneamente la direzione del moto 
quando gli pare?
-- 
Ma io non centro niente, io spiego solo come funziona la
matematica del futuro.

 possono muovere lungo gli spigoli del cubo con velocità unitaria.
Cioè possono in ogni momento scegliere se muoversi a velocità unitaria
in una direzione a scelta o rimanere fermi per il tempo che vogliono?

Il 04-07-2010, Maurizio Frigeni dice:

Per indicare gli otto vertici uso le solite coordinate
cartesiane, quindi sono: 000;100;010;...111.
Diciamo che i due ragni: r ed s, sono inizialmente
entrambi in 000 ed allora la mosca m sara' in 110.
Indico il movimento semplicemente coi soliti versori i,j,k
cioe': r000+i vuol dire che il ragno r muove da 000 a 100,
m110-i vuol dire che la mosca muove da 110 a 010.
Ecco la prima mossa mia:
1. r000+k; s000+i
spoiler
e la mosca puo':
1a) star ferma -> r001; s100; m110
1b) m110-i     -> r001; s100; m010
1c) m110+k     -> r001; s100; m111.
SEGUITO di 1a)
2.  r=fermo; s100+j
2a) m110-i  ->  r001+j e vince
2b) m110+k  ->  r=fermo e vince
SEGUITO di 1b)
2.  r001+j e vince
SEGUITO di 1c)
2. r=fermo; s100+j  e vince.
Il tutto SE&O, anzi: un'omissione almeno c'e', perche' adesso
bisogna pero' vedere cosa succede se la mosca a un certo punto
mentre scappa inverte la marcia per esempio, infatti cosi' mi
sembra troppo facile/ovvio per essere su Archimede.
-- 
Saluti, Dalet

nella stessa posizione di uno dei due ragni).
Si', con questa strategia: mentre un ragno si dirige su M, l'altro fa le
mosse a specchio della mosca, dove lo specchio e' il piano assiale di RM.
Ciao

 mosse a specchio della mosca, dove lo specchio e' il piano assiale di RM.
Hai ragione! In questo modo la mosca è confinata su mezzo cubo e non può
scappare... Bellissima soluzione!



Ma questo funziona solo se la mosca muove prima, altrimenti come fa il 
ragno a fare le mosse a specchio?
Se invece si muove per ultima, non la acchiapperanno mai...

 ragno a fare le mosse a specchio?
Non ci sono "mosse": i tre animali si possono muovere contemporaneamente
a loro piacimento ed ognuno vede istantaneamente che cosa fanno gli
altri, quindi la cosa funziona.


ragno a fare le mosse a specchio?
Se la mosca non si muove, pure il ragno "specchio" sta fermo. In effetti,
si puo' pensare che tutti i movimenti siano discretizzati con intervalli di
tempo e di spazio piccolissimi; in questa ottica, il ragno ripete le mosse
della mosca: pero', per la precisione, la cattura avviene non se si trovano
esattamente nello stesso punto, ma se il ragno riesce a raggiungere
l'istante dopo la posizione della mosca. Insomma, questo problema ricorda
un po' quello del cane attorno al lago. Ciao


Ok, allora è diverso da quel che avevo capito.
Io immaginavo che, ad ogni ciclo di clock, entrambi i ragni e la mosca 
si muovessero.


Bho, in non ho capito, come dice fm2766 se i 3 si muovono 
contemporaneamente, come fa a sapere il ragno dove muoversi per fare il 
movimento a specchio? A parte che non ho capito comunque la dinamica...
Invece, se ai due ragni diamo due walkietakie per farli mettere d'accordo su 
come risucire a raggiungere 2 vertici opposti del cubo (come diceva fm2766), 
poi una volta in posizione (e mentre ci arrivano se ne fregano della mosca) 
al successivo colpo di clock, quello che ha la mosca intercettabile va verso 
di lei, l'altro ragno a caso sceglie una delle due possibili vie di fuga 
della mosca, la mosca scappa su uno dei due vertici che può raggiungere. Al 
50% la mosca schiatta.
Se è stata fortunata si riparte da capo.

 fm2766),
Oppure, anche senza radioline.
I due ragni si mettono d'accordo all'inizio perché uno rimanga fermo fin 
tanto che l'altro non ha raggiunto il vertice opposto del cubo.
Poi parte l'attacco come descritto, se va male, si riparte da capo.

si muovessero.
se il ciclo di clock e' brevissimo e nel corso del (n+1)-esimo ciclo il
ragno "specchio" decide di imitare il movimento che ha visto fare alla
mosca durante il n-esimo ciclo (reagendo cosi' rapidissimamente), sembrera'
proprio che i due si muovano a specchio. Pero', come ho gia' detto,
sussiste il problema "zenoniano" che il ragno non raggiungera' mai
esattamente la stessa posizione della mosca. 

 nella stessa posizione di uno dei due ragni).
No
program mosca
do
	if ragno in uno spigolo convergente sul vertice della tua posizione then
		muoviti in un vertice adiacente nei cui spigoli convergenti non c'è un
ragno
	endif
loop

loop
Cosicche' dopo che i tre hanno percorso un spigolo di cubo e i ragni hanno
seguito la mia strategia, program mosca alla linea
muoviti in un vertice adiacente nei cui spigoli convergenti non c'è un
ragno
ritorna: 
"PANIC: such vertex does not exist"
Ciao

 Ciao
Eh si, se si trascura il gap temporale fra il movimento della mosca e
quello dei ragni.

 un po' quello del cane attorno al lago. Ciao
Un'alternativa stocastica è che un ragno "segue" sempre la mosca, un
altro invece sta fermo fin quando l'altro ragno non si troverà sul
vertice opposto del cubo, il che avverrà certamente dopo tre lati
percorsi.  Prima che l'altro ragno giunga in quel vertice stabilisce a
caso, su quale dei due spigoli della faccia ortogonale alla direzione
della mosca e dell'inseguitore. Se il ragno si troverà in direzione
della mosca la mosca potrà anche decidere di tornare indietro ma
questo le costerà una diminuzione di vantaggio rispetto all'altro
ragno inseguitore, una volta raggiunto il vertice successivo il ragno
"stocastico" si ferma fino a quando la configurazione non sia ancora
tale che la mosca si trova sulla faccia ortogonale alla direzione
mosca-inseguitore ed il ragno stocastico sta sul vertice opposto di
questa faccia, se invece il ragno stocastico sbaglia direzione una
volta percorso il suo spigolo sta fermo due lati e poi ripete il
tentativo. Ogni volta che il ragno stocastico azzecca il vantaggio
della mosca rispetto al ragno inseguitore diminuisce di una quantità
costante proporzionale al suo tempo di reazione.
Una variante deterministica che non sono sicuro di avere esaminato in
modo completo è quella in cui il tempo di reazione dei ragni sia più
piccolo del tempo di reazione della mosca, superficialmente dalla
casistica che ho valutato mentalmente mi sembra che non ci sia una
differenza sostanziale, per gli algoritmi deterministici, rispetto al
caso che i tempi di reazione siano uguali.
Una strategia stocastica molto più efficiente combina inizialmente la
strategia deterministica che dicevi, e che fa in modo da giungere ad
una posizione di vantaggio ridottissimo per la mosca, con la strategia
stocastica  che ho pensato, per le mosse seguenti.

 Se è stata fortunata si riparte da capo.
L'idea non è sviluppata fino in fondo perché la mosca può sempre
decidere di tornare indietro e cambiare via di fuga non appena vede il
ragno che sceglie a caso sta andando nella direzione dello stesso
vertice che sta puntando lei.


Si ma quando torna indietro trova l'altro ragno che era partito all'attacco 
certo, quindi si trova intrappolata.
Un ragno la attacca, lei scappa su uno dei due vertici liberi, se di sfiga � 
lo stesso scelto dall'altro ragno non ha proprio scampo.

 sfiga è lo stesso scelto dall'altro ragno non ha proprio scampo.
... e la mosca volò via. ;-p
-- 
Bye, Lem
Ceterum censeo ISLAM esse delendum
____________________________________________________________________________
Non sprecare i cicli idle della tua CPU: 
http://boinc.berkeley.edu/index.php

 "Tetis" ha scritto nel messaggionews:60b22ffb-f2f6-4bcc...@w12g2000yqj.googlegroups.com...

Trova l'altro ragno sul cammino solo nel caso che la distanza di
questo dalla mosca fosse meno dello spazio percorso da entrambi nel
tempo di reazione, altrimenti fa in tempo a raggiungere il vertice e
cambiare strada prima che il ragno inseguitore la raggiunga e
considera che inizialmente la distanza è di un intero lato ed a meno
che la mosca non sia sciocca non tenderà a diminuire, ma piuttosto ad
aumentare, a meno che i ragni non si muovano parimenti ed in tal caso
rimane costante.


E vabbe', allora sta mosca non può essere mai presa, no?

 E vabbe', allora sta mosca non può essere mai presa, no?
Un modo c'è: i ragni seguono la strategia deterministica suggerita da
El Filibustero, ed indipendentemente da quello che la mosca decide di
fare dopo esattamente due lati c'è un ragno a distanza di un clock
dalla mosca, dopo di che si può applicare la strategia stocastica.
Nota bene che se invece di ragionare in termini di tempi di clock si
ragiona in termini di tempo di reazione, supponendo cioè istantanee le
decisioni (inclusa quella di invertire la marcia) ma un tempo di
inerzia dello stato di moto presente al tempo della decisione, le cose
cambiano ulteriormente se può essere differente il tempo d'inerzia per
la mosca e per i ragni, ma se questi tempi sono uguali tutto rimane
come schematizzato da El Filibustero.


Non ho capito, puoi usare altre parole? :-)
Scusa, ma se la mosca può andare avanti e indietro, appena si muove da un 
vertice può sentire subito se almeno uno dei due ragni si stanno dirigendo 
sul vertice da lei scelto oppure sul vertice da lei lasciato, e quindi 
tornare indietro, fare in tempo a ritornare al vertice abbandonato e 
scappare verso il terzo che è libero.
Non capisco come possa essere presa.

 Non capisco come possa essere presa.
supponiamo che la mosca decida di tornare indietro
la mosca proviene dallo spigolo a e si trova nel vertice N contiguo ad
M in cui convergono anche gli spigoli b e c.
clock 1 la mosca muove lungo lo spigolo b dal vertice N ad N+1 ed il
ragno è fermo in N' (vertice simmetrico ad N rispetto al piano mediano
di N ed R)
clock 2 il ragno inizia ad andare lungo a' da N' ad N'+1, mentre la
mosca torna indietro da N+1 ad N
clock 3 il ragno torna da N'+1 ad N' e la mosca va da N ad N+1 lungo
lo spigolo c
clock 4 il ragno va da N' ad N'+1 lungo c' ...
la mosca verrà raggiunta ad un clock di distanza quando avrà
completato il lato c
occorre però tenere presente che nel frattempo l'altro ragno procede,
quindi la mosca non ha motivo per continuare a fare avanti ed
indietro, anzi la sua strategia ideale è proseguire lungo il lato a
fino a che giunge nel vertice N, dove il ragno giunge al clock
successivo e da quel momento continua a starle ad un clock di
distanza.
A questo punto è sufficiente che si riproponga la situazione di cui
sopra cioè la mosca proviene dallo spigolo a e si trova nel vertice N
mentre un ragno si trova in N' e sceglie a caso che mossa farà al
prossimo clock. (può certamente trattarsi di una qualsiasi
configurazione equivalente a questa).
caso I: mosca costretta a volare:
clock 1 la mosca si muove in direzione b da N ad N+1 ed il ragno si
muove lungo b' da N' ad N'+1 mentre l'altro ragno che prima stava in
N' adesso si troverà in N e bloccherà la strada al ritorno indietro
della mosca.
caso II: la mosca è ancora salva il ragno ha imboccato la direzione c'
anziché b'...
La configurazione detta è sufficiente alla validità del metodo
stocastico, ma è vero che verrà raggiunta?
A questo scopo occorre fare una ulteriore distinzione:
Se il primo ragno inseguitore ha iniziato a muoversi insieme alla
mosca allora nel momento in cui la mosca giunge al vertice N (ON
essendo lo spigolo b) al clock successivo, mentre la mosca imboccherà
il nuovo spigolo seguita ad un passo dall'altro ragno,  esso tornerà
indietro venendosi a trovare nella condizione favorevole per
l'algoritmo stocastico.
Se invece il primo ragno inseguitore ha iniziato a muoversi dopo la
mosca: nel momento in cui la mosca imboccherà il nuovo spigolo dopo
esser giunto in N esso rimarrà fermo fino a quando la mosca avrà
percorso tutto lo spigolo, a quel punto la mosca ha una sola scelta
possibile, il primo ragno inseguitore lo sa e rimane ancora fermo
finché la mosca ha completato di percorrere anche il secondo spigolo e
verrà a trovarsi in R, a questo punto il primo ragno inseguitore si
muoverà verso il punto N dal vertice M dove sarà rimasto ad aspettare.
Ed in ogni caso, quando la mosca avrà completato il suo spigolo, si
troverà in una configurazione favorevole all'algoritmo stocastico e se
le va male non le resta che volare.


Continuo a non capire.
Se facciamo come dici che la mosca č intelligente e quindi non si muove a 
caso, e che il clock č inferiore al tempo per passare da un vertice 
all'altro, e che tutti e 3 aspettano il colpo di clock per valutare e 
decidere, per me la mosca puň:
- aspettare ferma su un vertice fin tanto che un ragno non le viene 
incontro;
- con ragno che le viene incontro valutare dove si trova l'altro ragno:
    - se si sta dirigendo su uno degli altri due vertici per lei liberi, 
sceglie il terzo vertice;
    - altrimenti ne sceglie a caso uno dei due.
- quando arriva sul nuovo vertice, il loop della mosca riparte.
Non capisco come in queste condizioni possa essere mangiata. 

 Non capisco come in queste condizioni possa essere mangiata.
Consideriamo due facce parallele del cubo, di vertici rispettivamente:
R-A-M-B
R'-A'-M'-B'
i ragni stanno inizialmente in R e la mosca in M. Facciamo come dici
che la mosca aspetta finché il ragno che si è mosso si trovi in AM,
mentre l'altro ragno rimane fermo in R. Ad un certo punto per non
essere mangiata dovrà muoversi verso M' o verso B.
Se va verso B al colpo di clock successivo il ragno 1 fermo in R
comincia a procedere verso B mentre il ragno 2 va a fermarsi in M.
Arrivando in B la mosca deve andare verso B' mentre il ragno 1 si
troverà a distanza di un clock. Questo impedisce, da qui in avanti,
alla mosca di fare un passo indietro come anche di restare ferma.
Quando la mosca arriva in B' il ragno 2 inizia simultaneamente a
muoversi da M ad A. Da B' la mosca ha due  possibilità andare verso M'
o verso R', ma appena sarà arrivata in uno di questi vertici, (poniamo
R') il ragno 2 si muoverà a caso da A verso uno dei vertici contigui
A' ed R ed anche la mosca trovandosi in R' dovrà scegliere a caso fra
uno di questi due vertici. A questo punto se sceglie lo stesso vertice
scelto da ragno 2 non le resta che tentare di usare tutte le energie
residue per staccarsi in volo dal cubo.
Nell'altro caso la mosca decide per la prima volta di muoversi  verso
M' ed il ragno 1 in R si muoverà subito dopo verso R' mentre il ragno
2 continua a inseguirla. Quando la mosca giunge in M' il ragno 2 si
trova in MM' e quindi la mosca non può tornare indietro e deve
scegliere fra A' e B'. Il ragno 1, al clock successivo si trova in R'
e si muove verso il vertice scelto dalla mosca allo step precedente.
Quando la mosca giunge, poniamo, in A' il ragno 1 le è ad un clock di
distanza lungo R'A', nel frattempo il ragno 2 avrà raggiunto M' dove
si sarà fermato, alla mosca non rimane che andare verso A inseguita
dal ragno 1 che si trova in A'A ad un clock di distanza. Quando la
mosca giunge in A il ragno 2 inizia a muoversi verso B' mentre la
mosca dovrà muoversi verso M o verso R ma in entrambi i casi nel
momento in cui giunge, poniamo, in M il ragno 2 sceglierà a caso fra i
due vertici che rimangono a disposizione della mosca.
Ed ancora una volta abbiamo due possibilità: o la mosca è costretta a
volare subito, oppure raggiunge, poniamo, M'  per poi proseguire per
A' o B'  mentre il ragno 2 raggiunge B,  per proseguire alla volta di
R da cui si muoverà a caso verso uno dei due soli vertici disponibili
alla mosca.
Etc...
In questo modo la roulette russa, con mezzo tamburo carico, si ripete
ogni volta che la mosca percorre due lati, consecutivi.