Discussione:
Miagolone e Furbino 2
(troppo vecchio per rispondere)
Silvio Sergio
2018-02-07 10:00:26 UTC
Permalink
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)
Silvio Sergio
2018-02-07 20:31:14 UTC
Permalink
dicevo
Post by Silvio Sergio
Versione circolare del problema.
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)
GaS
2018-02-09 19:27:58 UTC
Permalink
Post by Silvio Sergio
dicevo
Post by Silvio Sergio
Versione circolare del problema.
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.
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
Silvio Sergio
2018-02-09 22:45:38 UTC
Permalink
Post by GaS
Post by Silvio Sergio
dicevo
Post by Silvio Sergio
Versione circolare del problema.
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.
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
Perdonami Gabriele, mi sono accorto che avevo scritto 15 invece di 16 quasi subito, ma visto che nessuno ci provava ho pensato non fosse neanche il caso di rettificare. La mia strategia è la stessa che hai trovato tu, solo che io uso <> invece di ><

Il rapporto 2:3 con la soluzione lineare è solo come ordini di grandezza.
I 10 giorni della soluzione di Marco bastano per N=15,16,17 così come con il tuo schema da 16 giorni si controllano 17 o 18 case. E' esattamente 2:3 per N=1,2 mod 6.
Post by GaS
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 :-((
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)
Silvio Sergio
2018-02-14 13:50:09 UTC
Permalink
Post by Silvio Sergio
dicevo
Post by Silvio Sergio
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)
GaS
2018-02-14 22:24:16 UTC
Permalink
Post by Silvio Sergio
Post by Silvio Sergio
dicevo
Post by Silvio Sergio
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...
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
GaS
2018-02-14 23:08:38 UTC
Permalink
Direi che si può sempre fare, per ogni N, visitando N celle al giorno.
Si riesce a fare di meglio?

Ciao
GaS
Silvio Sergio
2018-02-15 10:16:25 UTC
Permalink
Post by 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)
Silvio Sergio
2018-02-15 10:34:17 UTC
Permalink
Post by GaS
Direi che si può sempre fare, per ogni N, visitando N celle al giorno.
Si riesce a fare di meglio?
Io non ci sono riuscito, però mentre ci riprovo rilancio:
- toro
- 3D

Silv:o)
GaS
2018-02-17 20:39:38 UTC
Permalink
Post by Silvio Sergio
Post by GaS
Direi che si può sempre fare, per ogni N, visitando N celle al giorno.
Si riesce a fare di meglio?
- toro
2N? Questa mi convince per N pari ma ho dubbi per N dispari
Post by Silvio Sergio
- 3D
N^2? Direi la stessa strategia del 2D

Ciao GaS
Silvio Sergio
2018-02-19 16:39:02 UTC
Permalink
Post by GaS
2N? Questa mi convince per N pari ma ho dubbi per N dispari
Dipende da come imposti la scansione.
In effetti se generalizzi lo schema usato per il piano (basato su diagonali a zigzag) aumentando la distanza tra le diagonali, funziona solo per i pari.

.x#x...
xox....
.xox...
xox....
.xox...
xox....
.x#x...

Questo perché la gabbia formata dalle due zigzag non è ermetica, le due caselle segnate con "#" non sono circondate da "x" e potrebbero essere occupate il giorno dopo, al contrario delle "o".

Ma basta usare due normali diagonali per formare una gabbia senza buchi:

ox.....
xox....
.xox...
..xox..
...xox.
....xox
x....xo
Post by GaS
- 3D
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)
GaS
2018-02-19 22:14:21 UTC
Permalink
Post by Silvio Sergio
Post by GaS
2N? Questa mi convince per N pari ma ho dubbi per N dispari
Dipende da come imposti la scansione.
In effetti se generalizzi lo schema usato per il piano (basato su diagonali a zigzag) aumentando la distanza tra le diagonali, funziona solo per i pari.
.x#x...
xox....
.xox...
xox....
.xox...
xox....
.x#x...
Questo perché la gabbia formata dalle due zigzag non è ermetica, le due caselle segnate con "#" non sono circondate da "x" e potrebbero essere occupate il giorno dopo, al contrario delle "o".
Ed infatti sapevo che non andava bene per questo motivo ma non trovavo come bypassarlo anche se ero confidente che si potesse fare...
Post by Silvio Sergio
ox.....
xox....
.xox...
..xox..
...xox.
....xox
x....xo
bello così, molto bello.
Post by Silvio Sergio
Post by GaS
- 3D
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.
yes!

Ciao
GaS
Silvio Sergio
2018-02-20 00:32:10 UTC
Permalink
Post by Silvio Sergio
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.
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)
Silvio Sergio
2018-02-20 01:08:13 UTC
Permalink
Post by GaS
Post by Silvio Sergio
ox.....
xox....
.xox...
..xox..
...xox.
....xox
x....xo
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)

Silvio Sergio
2018-02-16 19:15:40 UTC
Permalink
Post by Silvio Sergio
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.
Altre varianti?
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)
Continua a leggere su narkive:
Loading...