Due problemi sulle scacchiere

[Composition86]

Vi posto un paio di problemi carini e non troppo complicati trovati sull'Engel:

1) Ci sono 5 scatole disposte come nell'immagine a sinistra e si vuole allinearle, raggiungendo così la configurazione finale (immagine a destra). Le T indicano il lato superiore di ciascuna scatola. Gli unici movimenti concessi alle scatole sono di rotolamento lungo uno spigolo. Si vuole trovare quale fra le 5 scatole della configurazione finale era al centro della configurazione iniziale.


2) (Questo lo posto perchè vorrei capire dove sta l'errore nella mia soluzione).

Si ha una scacchiera 9x9 e su ogni casella c'è uno scarafaggio (purtroppo ho tradurre il "beetle" inglese sulla traccia originale ). Ad un segnale, ogni scarafaggio trasla diagonalmente su una vicina casella, perciò può succedere che qualche casella rimanga vuota.
Trovare il minimo numero possibile di caselle che possono rimanere vuote.

Mia soluzione sbagliata (metto in piccolo per non dare hint):

Si colorano le caselle della scacchiera come quelle di una comune scacchiera: in particolare le diagonali maggiori avranno tutte caselle nere; si possono contare un totale di 41 caselle nere e 40 bianche.
Ogni traslazione diagonale implica il passaggio sempre fra caselle dello stesso colore.
Stando a ciò, si può pensare che gli scaraggi sulle caselle bianche si scambino a due a due (quindi A va sulla casella B e B va sulla A) e poichè il numero di tali caselle è pari, rimagono tutte occupate: viene quindi conservata la situazione iniziale.
Stesso procedimento per le caselle nere, che essendo però dispari, non vengono tutte riempite.
Quindi rimane una sola casella vuota e questa è nera. La cosa strana è che così non indico il numero minimo di caselle vuote, ma il massimo.

[MindFlyer]

La cosa strana è che così non indico il numero minimo di caselle vuote, ma il massimo.

No, così non indichi né il minimo né il massimo.
E non hai nemmeno dimostrato che il minimo è al più 1, perché non hai esibito un modo per scambiare gli scarafaggi nelle caselle nere come dici.
Insomma, non hai dimostrato niente.

[Composition86]

Ok, ho capito.
Però, almeno per le bianche, il ragionamento mi sembra valido, gli scarafaggi hanno tutti la possibilità di scambiarsi senza problemi e nessuna casella bianca rimane vuota: l'inghippo mi sembra stare sulle nere.
Quindi potrei riconsiderare solo le diagonali nere e con lo stesso ragionamento colorare le caselle di ciascuna diagonale nera alternativamente di nero e di verde (questo non influenza in alcun modo gli spostamenti degli scarafaggi sulle bianche), in modo che ad ogni traslazione uno scarafaggio possa o passare su una casella di colore diverso, o occuparne una già occupata, o andare fuori dalla scacchiera.
Come risulatato, se si scambiano a coppie, c'è sempre uno scarafaggio per ognuna delle 9 diagonali bicolori (le quali hanno tutte un numero dispari di caselle) che o va fuori dalla scacchiera o deve condividere la casella con un altro, quindi in tutto rimarrebbero esattamente 9 caselle vuote, che poi è anche lo stesso risultato riportato nel libro.
Però non ho molta dimestichezza con queste dimostrazioni e mi sembra che manchi ancora qualcosa.

[MateCa]

1) Direi che la scatola in questione è la seconda partendo da destra...

In effetti per la dimostrazione non saprei proprio da dove partire, comunque sicuramente la scatola che nella configurazione iniziale ha il lato superiore a destra (scusate il gioco di parole), quindi la seconda da destra - per intenderci - è sicuramente quella che originariamente era al centro in alto.
Da cui si deduce che la scatola più a sinistra nella configurazione finale era quella al centro in basso all'inizio.
Ergo le tre scatole dalla parte destra erano le tre sulla stessa riga della configurazione iniziale. Quindi quella al centro non può che essere la seconda da destra.

PS: temo che questa non sia proprio una DIMOSTRAZIONE. Quindi inviterei chiunque la sapesse fare come si deve a postarla...

[Anlem]

Anch'io avrei detto la seconda da destra, ma MateCa mi ha battuto sul tempo. Il mio ragionamento è stato molto simile al suo, quindi non vale la pena postarlo.

[Composition86]

PS: temo che questa non sia proprio una DIMOSTRAZIONE.

In effetti non lo è, anche se la soluzione è giusta.
Il titolo della discussione non è casuale, può dare un'idea su come procedere...

[jim]

Provo col 2, posto in bianco:

Numero ordinatamente le colonne della mia scacchiera da 1 a 9. Sia P il numero totale di scarafaggi(che chiameremo"scarafaggi pari") sulle colonne pari e D il numero totale di scarafaggi (che chiameremo "scarafaggi dispari") sulle colonne dispari.
Abbiamo che, inizialmente, P=9*4=36, D=9*5=45
Dopo il movimento degli scarafaggi avremo che per ogni scarafaggio cambierà la parità della sua colonna di appartenenza: quindi:
- Tutti i 45 scarafaggi "dispari" vanno su colonne pari
- Tutti i 36 scarafaggi "pari" vanno su colonne dispari

Allora è chiaro che ci saranno sulle colonne dispari esattamente nove caselle vuote. Vediamo ora se 9 è il minimo assoluto: cioè se è possibile trovare un movimento tale che ogni casella appartenente a una colonna pari, al termine di esso ospiti almeno uno scarafaggio "dispari".

Questo è possibile: lo dimostro, descrivendo il movimento degli scarafaggi "dispari" --> sulle caselle pari in questo modo:
(a,b)-->(c,d) vuol dire che, numerando ordinatamente anche le righe, uno scarafaggio "dispari" che sta sulla casella (a,b) (intersezione dell'a-esima riga e della b-esima colonna) va sulla casella (c,d).
Il movimento è questo:

-Per ogni a appartenente a {1...8}, (a,1)-->(a+1,2),
poi:
(2,3)-->(1,2)
(1,3)-->(2,4)
(2,5)-->(1,4)
(1,5)-->(2,6)
(2,7)-->(1,6)
(1,7)-->(2,8 )
(2,9)-->(1,8 )
-Per ogni a appartenente a {4...9}, (a,3)-->(a-1,4)
poi:
-per ogni a appartenente a {3...7}, (a,5)-->(a+1,6)
poi:
(8,5)-->(9,4)
(4,7)-->(3,6)
(8,7)-->(9,6)
(6,7)-->(7,8 )
(9,7)-->(8,8 )
(8,9)-->(9,8 )

e per finire, per ogni a appartenente a {4...7}, (a,9)-->(a+1,8 )

C.V.D.

[Composition86]

E' bello vedere come un problema di questo tipo lasci molta libertà di interpretazione. Però, anche se è giusta, mi sembra un po' macchinosa questa. L'Engel ne riporta una più intuitiva. Aspetto altri interventi prima di postarla.

A proposito Jim, ti sembra giusta quella che ho scritto io (quella scritta in piccolo nel terzo messaggio della pagina)? Ho usato un metodo simile a quello del libro, leggermente più intricato, ma non so se mi sono perso qualcosa.

[MindFlyer]

La soluzione di Jim mi pare la più semplice possibile, non capisco come l'Engel possa fare di meglio (magari la postate?). L'unico errore di Jim è dire "esattamente" anziché "almeno", ma per il resto è ineccepibile.

Composition, la tua non è ancora una dimostrazione perché fai vedere soltanto che se scambi gli scarafaggi a coppie, allora devi lasciare almeno 9 caselle vuote. Ma in generale non hai detto nulla.

[jim]

Allora:
Con quello che hai scritto tu, trovi un modo per lasciare nove caselle vuote. Però il problema chiedeva un'altra cosa: ossia determinare il numero minimo di caselle vuote che si può ottenere. Quindi la tua è una parte della soluzione. Ora devi dimostrare che nove caselle (che hai dimostrato potersi ottenere) sono proprio il minimo cercato, ossia che non esistano altri movimenti, diversi dal tuo "scambio a coppie" che lascino un numero di pedine vuote inferiore a nove.
Okay?
Buon divertimento!

P.S. son curioso di conoscere quella dell'Engel... Magari se hai voglia posta solo in piccolo una traccia...

[jim]

L'unico errore di Jim è dire "esattamente" anziché "almeno", ma per il resto è ineccepibile.

Giusto... Nulla vieta a due scarafaggi "Pari" di andare su una stessa casella appartenente a una colonna dispari, in tal caso sarebbero più di nove...
Grazie, Mind.

[Composition86]

Ok sulla mia "soluzione".
Ecco, mi sfuggiva questa faccenda del minimo, allora. Devo fare ancora molta pratica.

La soluzione dell'Engel, tradotta parola per parola, a voi l'interpretazione.
Coloriamo le colonne alternativamente di bianco e di nero. Otteniamo 45 caselle nere e 36 bianche. Ogni scarafaggio cambia colore della casella con una traslazione. Quindi almeno nove caselle nere rimangono vuote. E' facile vedere che esattamente nove caselle possono rimanere libere.
L'ultima frase, per come la vedo io, fa appello a qualcosa di lampante, immediatamente visibile.

[MindFlyer]

La soluzione dell'Engel, tradotta parola per parola, a voi l'interpretazione.

..Che è la soluzione di jim. Solo che quello che tu chiami "lampante", è descritto dall'Engel con un "è facile vedere che", mentre jim l'ha descritto esplicitamente. Non mi sembra il caso di dire che quella di jim è più macchinosa solo per questo motivo.

[Composition86]

Ok, forse mi era sembrata più immediata, quando magari non lo era. Beh, sta di fatto che il problema 2 ha trovato pace, finalmente.

Nessuno si cimenta con l'1?

[rand]

Per quanto riguarda il primo forse la seguente è la strada per risolverlo:
immaginiamo le cinque tessere disposte in una scacchiera di dimensione infinita con caselle bianche e nere.
L'osservazione di fondo è che se dopo una serie di mosse una tessera non si trova piu' in una casella dello stesso colore allora ha cambiato orientamento.

Ora chiamiamo 'centro' la tessera centrale nella configuarazione iniziale e assumiamo che inizialmente esso è su una casella bianca e le altre quattro sono su caselle nere. Nella configurazione finale abbiamo due possibili scenari:

1. La prima casella a sinistra è nera. Dunque il centro deve trovarsi in una delle due caselle bianche, perchè le caselle nere contengono tessere a T, quindi con lo stesso orientamento del centro. Dunque il centro puo' stare o nella seconda o nella quarta casella da sinistra. Ma se stesse nella seconda la quarta non avrebbe orientamento a T.

2. La prima casella a sinistra è bianca. Questo non può essere perchè altrimenti tra le caselle bianche almeno due non conterrebero tessere a T, quindi non siamo in realtà nella configurazione finale.

Chiarissimo, no?