Newsgroup: it.hobby.enigmi
Titolo: Miagolone e Furbino 2

Versione circolare del problema.
 
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 circolare 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' 17 il giorno dopo si sposta nella 1 o nella 16.
Mettiti nei panni di Miagolone, in quanti giorni riusciresti nell'impresa? 
 
Nota bene. Magari non c'è soluzione, non ci ho pensato molto.
 
Ciao, Silv:o)
 

 Nota bene. Magari non c'è soluzione, non ci ho pensato molto.
 
Ci ho pensato un po' e c'è soluzione per ogni N.
 
Per N=17 nella versione in linea il gatto di Marco ci mette 10 giorni, il mio  ce ne mette 15 per quella circolare. Il rapporto 2:3 vale per tutte le dimensioni.
 
Ciao, Silv:o)


Visto che non sono arrivate risposte metto la mia anche se vedo che non è ottimale, con la strategia proposta sotto ci si mettono infatti 16 giorni contro i 15 di Silvio
 
s
.
.
p
.
.
o
.
.
i
.
.
l
.
.
e
.
.
r
.
.
 
O--------------O-
-O------------O--
--O----------O---
---O--------O----
----O------O-----
-----O----O------
------O--O-------
-------OO--------
-------OO--------
------O--O-------
-----O----O------
----O------O-----
---O--------O----
--O----------O---
-O------------O--
O--------------O-
 
La soluzione può ovviamente essere adattata ad ogni numero dispari:
 - 2 gg per 3 cavità
 - 4 gg per 5 cavità
...
 - N-1 gg per N cavità
 
Ho difficoltà a vedere la soluzione di Silvio: nel caso lineare per 5 cavità bastano 2 giorni (-O-O- e  -O-O-), secondo quanto scritto da Silvio vorrebbe dire che nel caso circolare bastano 3 gg. 5 cavità per 3 gg si fa esaustivo a mano ma non l'ho trovata :-((
 
Ciao
GaS

 a mano ma non l'ho trovata :-((
 
per 7 o 8 però ci vogliono 4 giorni per il tunnel lineare
 
.o.o....
....o.o.
....o.o.
.o.o....
 
e 6 per quello circolare
 
..o.o...
.o...o..
o.....o.
o.....o.
.o...o..
..o.o...
 
Ciao, Silv:o)

 > Versione circolare del problema.
 
Il problema si trova in rete nella versione base, con un solo tentativo al giorno, di solito con principesse o gatti dietro le porte di stanze comunicanti. In quella variante un corridoio circolare rende impossibile la cattura, non è difficile da dimostrare. Le varianti con due tentativi al giorno, sia nella versione in linea presa da Dario che in quella circolare che ho proposto io, sono secondo me più interessanti dell'originale.
 
Altre varianti?
Aumentare il numero dei tentativi non aggiunge pepe, mi pare.
Magari altre topografie, o regole di ingaggio...
 
Ciao, Silv:o)
 
 


Io avevo cominciato a pensare ad una versione in 2D e quindi con stanze poste in una scacchiera NxN e tutte comunicanti tra loro ortogonalmente. Penso che in questa versione la domanda interessante sia: quante stanze deve visitare *al minimo* giornalmente Miagolone per rendere possibile la cattura?
 
Direi infatti che 2 visite giornaliere non bastino tranne che in una scacchiera 2x2, o almeno io non le vedo al momento
 
In una scacchiera 3x3 si fa facile con 4 visite giornaliere (in 2 giorni), ma 4 è il minimo o esiste una strategia con 3 visite giornaliere che, anche se in più di 2 giorni, permette a Miagolone di catturare Furbino?
 
Io comincio a pensarci
 
Ciao
GaS

Direi che si può sempre fare, per ogni N, visitando N celle al giorno.
Si riesce a fare di meglio?
 
Ciao
GaS


Si può fare con una doppia scansione da destra a sinistra e ritorno.
Solita tecnica, prima catturo i pari poi i dispari.
Una cosa così:
 
x....
.x...
x....
.x...
x....
 
.x...
..x..
.x...
..x..
.x...
 
..x..
...x.
..x..
...x.
..x..
 
...x.
....x
...x.
....x
...x.
 
...x.
....x
...x.
....x
...x.
 
..x..
...x.
..x..
...x.
..x..
 
.x...
..x..
.x...
..x..
.x...
 
x....
.x...
x....
.x...
x....
 
Totale: 40 visite, 8 giorni.
 
oppure con una doppia scansione a ventaglio, a visite variabili:
 
.x...
x....
.....
.....
.....
 
..x..
.x...
x....
.....
.....
 
...x.
..x..
.x...
x....
.....
 
....x
...x.
..x..
.x...
x....
 
.....
....x
...x.
..x..
.x...
 
.....
.....
....x
...x.
..x..
 
.....
.....
.....
....x
...x.
 
e ritorno.
 
Totale: 46 visite e 14 giorni. No, non è una buona idea
 
Silv:o)

 Si riesce a fare di meglio?
 
Io non ci sono riuscito, però mentre ci riprovo rilancio:
- toro
- 3D
 
Silv:o)

 Magari altre topografie
 
Ho visto che il problema è stato diffusamente analizzato, e si è scoperto che il più piccolo grafo che impedisce la cattura con una sola visita al giorno è il marchio mercedes di ordine tre. Questo:
 
0         
1         
2         
3 4 5 6   
7         
8         
9         
 
Faccio un esempio di un possibile tentativo [] che ha come isola una casella ():
 
 0        (0)      
[1]        1      
 2         2      
 3 4 5 6   3 4 5 6
 7         7      
 8         8      
 
Qualunque tentativo diverso da 1,5,7 al primo giorno è una mossa del tutto sprecata perché non isola nessuna casella.
 
Continuiamo per un paio di giorni con mosse più o meno obbligate
 
 0        (0)        0        (0)         
[1]        1        (1)        1         
 2        [2]        2        (2)         
 3 4 5 6   3 4 5 6  [3]4 5 6   3 4 5 6   
 7         7         7         7         
 8         8         8         8         
 
Al quarto giorno che casella attacchiamo?
 
Le più promettenti sembrano essere le due adiacenti la casella centrale, la 4 e la 7.
 
(0)        0       
 1        (1)      
(2)        2         
 3[4]5 6   3 4 5 6
 7         7         
 8         8         
 
La 4 è un buco nell'acqua, siamo addirittura tornati indietro alla situazione del terzo giorno!
 
Proviamo l'altra:
 
(0)        0       
 1        (1)      
(2)        2         
 3 4 5 6   3 4 5 6
[7]        7
 8        (8)
 
Bingo! Adesso attaccando la casella 3 possiamo isolare la 2 e la 7!
 
 0        (0)
(1)        1
 2        (2) 
[3]4 5 6   3 4 5 6
 7        (7)
(8)        8
 
Ora attaccando la 4 isoliamo la 3, poi la 5 e infine la 6. A quel punto rifacciamo la strada al contrario e catturiamo le prede che si erano salvate. La soluzione completa è
12373456-65437321
 
Dal tentativo fallimentare del quarto giorno si capisce che se non c'è almeno un ramo corto non si va da nessuna parte. La conclusione alla quale sono arrivati è che se il grafo ha un ciclo o almeno un sottografo isomorfo al logo mercedes di ordine tre, la caccia fallisce.
 
Dopo tutta questa fatica, finalmente la domanda:
Con DUE cacciatori, qual è il sottografo minimo che garantisce la salvezza alla preda?
 
Ciao, Silv:o)

 - 3D
 
N^2? Direi la stessa strategia del 2D
 
Ciao GaS
 
 
 

 N^2? Direi la stessa strategia del 2D
 
Direi di si. Immagina un cubo con le caselle di colori alternati.
Il primo giorno visito le bianche del primo e secondo piano.
Il secondo giorno le nere del secondo e terzo piano e così via.
Quando arrivo in cima ho catturato tutti i gatti che al primo giorno erano su caselle bianche. Scendendo catturo gli altri.
 
Ciao, Silv:o)
 

 Quando arrivo in cima ho catturato tutti i gatti che al primo giorno erano su caselle bianche. Scendendo catturo gli altri.
 
yes!
 
Ciao
GaS
 

 yes!
 
ovviamente vale per ogni numero di dimensioni, comprese 1D e 2D che abbiamo già analizzato, basta aggiungere il prefisso iper a piano e cubo.
 
Silv:o)

 bello così, molto bello.
 
il bello della scacchiera toroidale, sulla quale davvero si gioca una variante divertente di scacchi, è che anche le diagonali sono circolari, non solo file e colonne. Per mettere in stallo un pezzo che si muova di una casella alla volta ma solo in orizzontale o verticale, tipo una torre zoppa, bastano due alfieri.  E come abbiamo appena dimostrato bastano due alfieri ciechi per catturare una torre zoppa ma vedente in poche mosse.
 
Ciao Silv:o)