Discussione:
Vecchio enigma di Dario
(troppo vecchio per rispondere)
Silvio Sergio
2018-02-05 13:14:03 UTC
Permalink
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?
Giorgio Vecchi
2018-02-05 16:00:00 UTC
Permalink
Post by Silvio Sergio
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?
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
Silvio Sergio
2018-02-06 11:11:34 UTC
Permalink
Post by Giorgio Vecchi
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)
Era anche la mia. Ma Marco Gavanelli ha fatto MOLTO meglio.
Giorgio Vecchi
2018-02-06 14:04:20 UTC
Permalink
Post by Giorgio Vecchi
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)
Era anche la mia. Ma Marco Gavanelli ha fatto MOLTO meglio.
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
Silvio Sergio
2018-02-06 17:41:04 UTC
Permalink
Post by Giorgio Vecchi
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
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)
Silvio Sergio
2018-02-07 09:29:42 UTC
Permalink
Post by Giorgio Vecchi
Direi che si spiega con la "solita" questione della parità.
[cut]
Se il topo inizialmente è in una casella pari, prima o poi nel viaggio di
andata il gatto lo troverà.
[cut]
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).
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)

Marco Gavanelli
2018-02-05 16:58:01 UTC
Permalink
Post by Silvio Sergio
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?
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]
Silvio Sergio
2018-02-06 11:09:35 UTC
Permalink
Post by Marco Gavanelli
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]
Bellissima. Come l'hai trovata?
Marco Gavanelli
2018-02-06 13:14:43 UTC
Permalink
Post by Silvio Sergio
Post by Marco Gavanelli
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]
Bellissima. Come l'hai trovata?
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
2018-02-06 11:32:53 UTC
Permalink
Post by Marco Gavanelli
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.
Continua a leggere su narkive:
Loading...