Newsgroup: it.hobby.enigmi
Titolo: Vecchio enigma di Dario

Prima di pranzo mi sono imbattuto in un vecchio enigma pubblicato da Dario qualche annetto fa.
 
Il gatto Miagolone sta cercando di catturare il topo Furbino che vive in
una di 17 cavita'. Le cavita' sono unite da un'unica galleria rettilinea
che le collega tutte.
Miagolone sa che Furbino ogni giorno si sposta in una cavita' adiacente
a suo piacimento, se ad es. un dato giorno sta nella cavita' num 10, il
giorno dopo si sposta nella 9 o nella 11.
Miagolone ogni giorno riesce a controllare solo 2 cavita', e' evidente
che visitando le cavita'  (1,2) ( 2,3) (3,4)......(16,17)  gli riuscira'
di localizzare il topo in un massimo di 16 giorni, ma questa non e' la
strategia migliore.
Mettiti nei panni di  Miagolone, in quanti giorni riusciresti
nell'impresa ??
 
Non mi pare ci sia più in giro la soluzione, ma anche ci fosse vi invito a non cercarla in rete. Mangiando il panino ci ho pensato un po' ed ho trovato una soluzione in 14. Sapete fare di meglio?
 

"Silvio Sergio"  ha scritto nel messaggio 
news:2a027a9e-c87a-40a2...@googlegroups.com...

Questo di Dario non me lo ricordavo proprio (e non sono andato a cercarlo in 
giro). Una soluzione da 14 penso di averla trovata anch'io. La scrivo ma non 
garantisco, ho un po' di febbre e ho fatto anche troppo...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 
(2,4) (2,4) (4,6) (4,6) (6,8) (6,8) (8,10) (8,10) (10,12) (10,12) (12,14) 
(12,14) (14,16) (14,16)
 
Ciao
 
Giorgio
 


Ne ho trovata una con 10, ma non so se e` l'ottimo.
 
.
.
.
.
 
S
 
P
 
O
 
I
 
L
 
E
 
R
 
.
.
.
.
.
.
.
.
.
.
 
Da come e` descritto il problema, il topo non puo` stare fermo (due 
giorni nella stessa cavita`). Quindi una soluzione e`
 
[2,4],[5,7],[8,10],[11,13],[14,16],[14,16],[11,13],[8,10],[5,7],[2,4]

 [2,4],[5,7],[8,10],[11,13],[14,16],[14,16],[11,13],[8,10],[5,7],[2,4]
 
Bellissima. Come l'hai trovata?

 (12,14) (14,16) (14,16)
 
Era anche la mia. Ma Marco Gavanelli ha fatto MOLTO meglio.

 Ne ho trovata una con 10, ma non so se e` l'ottimo.
 
Guarda, appena letto il posto ero partito a scrivere la risposta: "con un gatto così i topi ballano, gli basta ..." ma non riuscivo a trovare a mano un controesempio. Poi ho notato chi lo aveva propposto ed ho fatto subito marcia indietro!
PS. Siccome poi fidarsi è bene ma controllare è meglio ho buttato giù al volo un programmillo ricorsivo e non ha stampato neanche mezza soluzione.


Beh, io sono un fan della programmazione logica, ho scritto anch'io un 
programma ricorsivo, in Prolog. In sostanza, risolve un gioco a due 
giocatori:
- prima gioca il gatto, dicendo tutta la strategia
- poi gioca il topo.
 
In realta` il programma era troppo lento per arrivare alla dimensione 
17, per cui l'ho eseguito su istanze piu` piccole ed ho visto che la 
soluzione che generavano seguiva sempre questa struttura. Allora l'ho 
estesa alla dimensione 17, ho visto che non c'erano strategie valide per 
il topo e ve l'ho mandata.
 
Ma il mio programma e` troppo lento per dimostrare che non esistono 
soluzioni migliori.
 
Ciao,
Marco

"Silvio Sergio"  ha scritto nel messaggio 
news:76f971d1-cf53-4499...@googlegroups.com...

Sì sì, ho visto. Molto bella!
 
Direi che si spiega con la "solita" questione della parità. All'andata il 
gatto controlla alternativamente due caselle pari, poi due dispari, ecc. Se 
il topo inizialmente è in una casella pari, prima o poi nel viaggio di 
andata il gatto lo troverà. Mi spiego: controllare 2-4 sapendo che il topo è 
in una casella pari equivale a controllare la 1, la 2, la 3 e la 4. 
Successivamente controllare la 5 e la 7 nel momento in cui il topo si è 
dovuto spostare in una casella dispari equivale a dire che il gatto 
controlla la 5. la 6 e la 7, con la certezza che nel frattempo il topo non 
ha potuto passare dalla 5 alla 4, perché poteva muovere solo da pari a 
dispari. Quindi in sostanza le sta passando in rassegna tutte finché non lo 
trova.
 
Se invece il topo era inizialmente in una casella dispari, il gatto lo 
troverà al ritorno. La ripetizione della mossa (14,16) ha anche lo scopo di 
interrompere la sequenza pari/dispari per il gatto (ma non per il topo), 
quindi se il topo si era salvato all'andata perché in casella dispari quando 
il gatto controllava le caselle pari e viceversa, adesso il gatto 
controllerà le caselle pari quando il topo si trova in una pari e stesso 
discorso per le dispari, quindi prima o poi lo troverà (stesso discorso 
iniziale, andando indietro).
 
Proprio bello!
 
Giorgio 
 

 Giorgio
 
Esatto.
Guarda che bel crivello! (fixed font)
 
.M.M.............
....M.M..........
.......M.M.......
..........M.M....
.............M.M.
.............M.M.
..........M.M....
.......M.M.......
....M.M..........
.M.M.............
 
le diagonali pari si schiantano sulla parte alta, le dispari sulla bassa.
 
Questa è un tentativo dispari (parte dalla cavità 3)
 
.MfM.............
...fM.M..........
....f..M.M.......
.....f....M.M....
....f........M.M.
...f.........M.M.
....f.....M.M....
.....f.M.M.......
....M.M..........
.M.M.............
 
Questi due tentativi pari, uno dei quali ipotetico (parte dal giorno 2)
 
.M.M.........f...
f...M.M.......f..
.f.....M.M.....f.
..f.......M.M...f
.f...........M.M.
f............M.M.
.f........M.M....
..f....M.M.......
...fM.M..........
.M.Mf.............
 
Il meglio che f può fare per sopravvivere almeno 9 giorni è un percorso qualsiasi che porti nella cavità 1 dopo nove giorni, per esempio 987654321 o 121212121
 
fM.M....f........
.f..M.Mf.........
f.....fM.M.......
.f...f....M.M....
f...f........M.M.
.f.f.........M.M.
f.f.......M.M....
.f.....M.M.......
f...M.M..........
.M.M.............
 
Ciao, Silv:o)

 iniziale, andando indietro).
 
Funziona anche ripetendo lo schema senza ribaltarlo.
I topi che partono da casa pari vengono intercettati al primo giro. Gli altri arrivano salvi al sesto giorno ma su casa pari e al secondo giro non si salvano.
 
Ciao, Silv:o)