I sordatini
Un numero finito di soldati sono disposti su una linea che va da ovest verso est, con la faccia rivolta a nord. Il comandante grida :"FIANCO DINSTRO!". Un secondo dopo tutti si girano chi verso est, chi verso ovest non avendo capito bene il comando. L e coppie di soldati vicini che si ritrovano faccia a faccia realizzano di aver sentito male e si girano (entrambi). Un secondo dopo le coppie di soldati vicini che si ritrovano faccia a faccia realizzano di aver sentito male e si girano (entrambi)... e così via, il processo prosegue.
Provare che questo si conclude dopo un numero finito di passi.
Provare che questo si conclude dopo un numero finito di passi.
Risposte
Il motivo per cui il processo si arresta in un numero finito di passi è che non c'è ciclicità. Infatti se la fila fosse chiusa su se stessa andrebbero avanti all'infinito.
Dimostrazione rigorosa non mi viene, però penso che il discorso seguente fila (invece di est-ovest faccio destra-sinistra).
Il primo e l'ultimo si gireranno al più una volta: se guardano verso l'esterno della fila non si girano affatto, se guardano verso l'interno si gireranno una sola volta quando (e se) il secondo e il penultimo rispettivamente li guarderanno. D'ora in poi (da quando guardano entrambi verso l'esterno) non si gireranno più. A questo punto rappresentano una certezza per i soldatini secondo e penultimo che si fermeranno quando guarderanno le spalle di primo e ultimo rispettivamente. E così via verso l'interno.
Il risultato è che la fila è composta così: SSS...SSSDDD...DDD (S=girato verso sinistra,D=girato verso destra)
Penso che non saranno mai tutti girati dalla stessa parte a meno che non lo siano fin dall'inizio. Infatti, in un orientamento corretto di tutti, per esempio tutti girati a sinistra, l'ultimo soldatino guarderà verso l'interno. Per rimanere in questa posizione dovrà vedere le spalle del penultimo, che dovrà vedere le spalle del terzultimo e così via.. Quindi devono essere tutti già girati a destra.
Dimostrazione rigorosa non mi viene, però penso che il discorso seguente fila (invece di est-ovest faccio destra-sinistra).
Il primo e l'ultimo si gireranno al più una volta: se guardano verso l'esterno della fila non si girano affatto, se guardano verso l'interno si gireranno una sola volta quando (e se) il secondo e il penultimo rispettivamente li guarderanno. D'ora in poi (da quando guardano entrambi verso l'esterno) non si gireranno più. A questo punto rappresentano una certezza per i soldatini secondo e penultimo che si fermeranno quando guarderanno le spalle di primo e ultimo rispettivamente. E così via verso l'interno.
Il risultato è che la fila è composta così: SSS...SSSDDD...DDD (S=girato verso sinistra,D=girato verso destra)
Penso che non saranno mai tutti girati dalla stessa parte a meno che non lo siano fin dall'inizio. Infatti, in un orientamento corretto di tutti, per esempio tutti girati a sinistra, l'ultimo soldatino guarderà verso l'interno. Per rimanere in questa posizione dovrà vedere le spalle del penultimo, che dovrà vedere le spalle del terzultimo e così via.. Quindi devono essere tutti già girati a destra.
"Aster89":
Il motivo per cui il processo si arresta in un numero finito di passi è che non c'è ciclicità. Infatti se la fila fosse chiusa su se stessa andrebbero avanti all'infinito.
Dimostrazione rigorosa non mi viene, però penso che il discorso seguente fila (invece di est-ovest faccio destra-sinistra).
Il primo e l'ultimo si gireranno al più una volta: se guardano verso l'esterno della fila non si girano affatto, se guardano verso l'interno si gireranno una sola volta quando (e se) il secondo e il penultimo rispettivamente li guarderanno. D'ora in poi (da quando guardano entrambi verso l'esterno) non si gireranno più...
direi che fila, sì.
Ma non mi sembra completa: manca un argomento che provi che ad un certo punto (finito) gli estremi guarderanno verso l'esterno.
Il resto chiude la faccenda (la formalizzazione è un dettaglio "tecnico").
PS
Io, a suo tempo, ho trovato una dimostrazione diversa.
Hai ragione. Comunque se guardano verso l'esterno, così restano. Quindi sarebbe da dimostrare che se guardano verso l'interno, dopo un numero finito di step si girano.
Comunque sarei molto curioso del dettaglio tecnico, giuro. Ti espongo certi pensieri alla rinfusa che mi sono passati in mente.
SSS...SSSDDD...DDD è una condizione finale, mentre DDD...DDDSSS...SSS non lo è, ed infatti diventa proprio uguale alla prima, a seguito di "un'onda" che si propaga prima verso l'esterno (configurazione DSDS...DSDS), poi verso l'interno. Stabilità e instabilità delle configurazioni? (sono stabili solo quelle SSS...SSSDDD...DDD)
S=1 D=0. Quindi hai a che fare con numeri binari. Può servire?
Comunque sarei molto curioso del dettaglio tecnico, giuro. Ti espongo certi pensieri alla rinfusa che mi sono passati in mente.
SSS...SSSDDD...DDD è una condizione finale, mentre DDD...DDDSSS...SSS non lo è, ed infatti diventa proprio uguale alla prima, a seguito di "un'onda" che si propaga prima verso l'esterno (configurazione DSDS...DSDS), poi verso l'interno. Stabilità e instabilità delle configurazioni? (sono stabili solo quelle SSS...SSSDDD...DDD)
S=1 D=0. Quindi hai a che fare con numeri binari. Può servire?
Aspè, forse ci sono.
1) SSS...SSSDDD...DDD è l'unica (a meno della numerosità delle S e delle D) configurazione stabile (cioè alla quale non segue un movimento)
2) S....................D porta inevitabilmente alla configurazione stabile (penso che pure questo è dimostrato dal discorso che ho fatto alla mia prima risposta)
3) all'estremo sinistro (risp. destro) prima o poi ci sarà una S (risp. D) che rimarrà immutata. Questa era la dimostrazione mancante, giusto?
Alloooooora.
Devo dimostrare che DXXX....XXX... diventerà SXX....XXX...
Evidentemente questo vale per il caso DSX...XXX...
Per il caso DDD...DDDSXX...XXX... è evidente che la coppia DS si propagherà verso sinistra di un posto alla volta. Quindi in un numero finito di step (pari alla numerosità delle D consecutive che stanno al bordo sinistro) avremo la S sul bordo sinistro.
Similmente sul bordo destro
1) SSS...SSSDDD...DDD è l'unica (a meno della numerosità delle S e delle D) configurazione stabile (cioè alla quale non segue un movimento)
2) S....................D porta inevitabilmente alla configurazione stabile (penso che pure questo è dimostrato dal discorso che ho fatto alla mia prima risposta)
3) all'estremo sinistro (risp. destro) prima o poi ci sarà una S (risp. D) che rimarrà immutata. Questa era la dimostrazione mancante, giusto?
Alloooooora.
Devo dimostrare che DXXX....XXX... diventerà SXX....XXX...
Evidentemente questo vale per il caso DSX...XXX...
Per il caso DDD...DDDSXX...XXX... è evidente che la coppia DS si propagherà verso sinistra di un posto alla volta. Quindi in un numero finito di step (pari alla numerosità delle D consecutive che stanno al bordo sinistro) avremo la S sul bordo sinistro.
Similmente sul bordo destro
Perfetto. Hai pure formalizzato il "dettaglio "tecnico"" 
.
.
"Aster89":
...
Comunque sarei molto curioso del dettaglio tecnico, giuro. Ti espongo certi pensieri alla rinfusa che mi sono passati in mente.
...
S=1 D=0. Quindi hai a che fare con numeri binari. Può servire?
a suo tempo ho usato un formalismo esattamente di questo tipo
.Adesso creedo opterei per i simboli ">", "<".
passare da unasequenza tipo:
[size=150]<<<<><<<<>>><>>[/size]
a una tipo
[size=150]<<<<<><<<>><>>>[/size]
mi sembra più suggestivo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo