Era un po' che non aprivo un nuovo topic...troppo!
Solerte come sempre,ho deciso di proprovi una serie di interessanti problemuzzi (non miei) trovati qua e là per la rete.Ecco un problema molto interessante:i soldati imbranati.
In una caserma dell'esercito é appena arrivata un'infornata di giovani reclute,ancora terribilmente spiazzate per l'ingresso nell'Arma militare.
Il Generalissimo,per passarle in rassegna,ha ordinato loro di disporsi in fila ordinatamente,orientati in un'unica direzione.I poveri soldatini hanno immediatamente eseguito l'ordine di mettersi in fila,ma naturalmente sono finiti orientati tutti a casaccio:chi a destra e chi a sinistra,in maniera casuale.Il Generalissimo arrabbiato urla loro di mettersi in un'unica direzione(il Generalissimo é molto tonto e non pensa di dirgli una direzione per troncare il caos crescente,ma lascia che ci pensino loro):le reclute allora cercano,restando in fila,di mettersi in ordine,secondo la semplice regola che se due soldati si trovano a guardarsi in faccia,entrambi pensano di essersi voltati dalla parte sbagliata e cambiano istantaneamente direzione,finendo così per darsi le spalle.Tutti gli scambi sono simultanei;se dopo uno scambio due soldati finiscono per guardarsi in faccia ovviamente si girano entrambi.Man mano che il tempo passa il Generalissimo diventa più furioso,ma la sorte é dalla parte dei soldatini:in breve tempo tutti i soldati si trovano voltati dalla stessa parte.
Il primo problema riguarda il famoso detto,mille volte ripetuto in fisica ed in chimica,che la Natura odia gli squilibri:viene da pensare,ad un attento ragionamento,che prima o poi i soldati finiscono in una situazione stabile,ossia in uno stato che non obblighi nessun soldato a voltarsi per seguire le regole precedenti(non necessariamente i soldati sono girati dalla stessa parte,potrebbero essere divisi in due tronconi voltati uno a destra e uno a sinistra).La domanda é:se il numero di soldati é finito,potete dimostrare che prima o poi tutti i soldatini finiranno in una situazione di equilibrio?
E se fossero disposti a griglia?
Immaginate una griglia regolare di soldatini,che possono essere voltati a Nord,Sud,Est,Ovest:se seguono le regole precedenti(se due soldati si trovano a guardarsi in faccia,entrambi pensano di essersi voltati dalla parte sbagliata e cambiano istantaneamente direzione girando di 180°,finendo così per darsi le spalle-se nel voltarsi un soldato incrocia altri sguardi non ci fa caso essendo sempre più preoccupato dalle urla del generalissimo),potete dimostrare che prima o poi i soldati finiranno in una situazione di equilibrio(sempreché il numero di soldati non sia infinito)?Qui l'idea di posizione di equilibrio mi sembra più complessa:quali tipi di "situazione di equlibrio" esistono?Nel caso di prima,se diamo per buona l'ipotesi del raggiungimento dell'equilibrio,la probabilità che una fila di N soldati finisca non solo in equilibrio,ma anche voltata completamente in una direzione,soddisfacendo il terribile Generalissimo, é di 2/(N+1);qui quant'é?Immagino che lo schema assunto dai soldati cambi di molto le carte in tavola,quindi limitiamoci a metterli in quadrati regolari o al più in rettangoli.E dunque?
Mi interessa l'idea di quello che potrebbe accadere se i tapini militari si girassero solo di novanta anziché di centottanta gradi:come andrebbe a finire?
Esiste un algoritmo per capire rapidamente se una fila o una griglia si ordinerà correttamente secondo le regole elencate?Spero in ZioGiò quando si libererà per un programma capace di trovare,a partire da uno scheme dato,il risultato finale:sarebbe molto utile alla comprensione del problema.
E infine il domandone terribile:se passiamo alle 3,4,...N dimensioni che succede?Considerate che per N dimensioni i soldati possono guardare in $\displaystyle 2^N$direzioni.Anche a molte dimensioni l'equilibrio verrà raggiunto?
Bon,ora é davvero tardi...invito come al solito tutto il forum a scrivere copiosamente soluzioni,domande ed estensioni,saluto con affetto e me ne vado a nanna.
Ciao bella gente!
Zerinf

alla mattina presto non vado oltre al caso minimale: due soldati.
Credo si debba presumere che ogni singola recluta possa assumere due e solo due "stati", ovvero direzioni, altrimenti, con infinite possibilità di sguardo, la cosa diventa ingestibile, con grave rischio per le coronarie del generale (qui ci sarebbe qualcosa da dire sul fatto di un generale che si occupa in prima persona delle reclute...lo sostituirei con un sergente maggiore o anche solo un caporale)
Due soldati = quattro possibili situazioni di partenza.
tre stabili da subito
Est-Est
Ovest-Ovest
Ovest-Est
solo la disposizione
Est-Ovest comporta che i militi si vedono in faccia, e porta quindi in un solo passaggio a
Ovest-Est

Con due soli soldati, dunque, si giunge, se non ci è da subito, ad una situazione di equilibrio molto rapidamente: nel 50% dei casi in modo soddisfacente (per il sergente), nel 50% in modo "irritante"

passaimo a quattro reclute
abbiamo 16 disposizioni di partenza, di cui 5 già in equilibrio
E-E-E-E
O-O-O-O
soddisfacenti per il sergente, e
O-E-E-E
O-O-E-E
O-O-O-E
mica tanto

le altre posizioni di partenza, conducono (massimo in tre passaggi) ad una di queste ultime tre

anche a occhio credo di poter estrapolare due concetti:
1) prima o poi i soldati si fermano
2) se non sono in fila subito, non lo diventano certo con questo algoritmo

qui *non* e' la mattina presto, anche se nella speranza di reggere ancora un po', ho appena preso il caffe' (che tuttavia non mi fa alcun effetto, se non lievemente soporifero). Ricordo ai solutori/programmatori che se si va oltre le 5dim le solite funzioni generatrici di numeri casuali producono numeretti bellamente allineati lungo iperpiani.
d.

Daniela ha scritto:qui *non* e' la mattina presto, anche se nella speranza di reggere ancora un po', ho appena preso il caffe' (che tuttavia non mi fa alcun effetto, se non lievemente soporifero). Ricordo ai solutori/programmatori che se si va oltre le 5dim le solite funzioni generatrici di numeri casuali producono numeretti bellamente allineati lungo iperpiani.
d.

Si consiglia la lettura di http://www.library.cornell.edu/nr/cbookcpdf.html, capitolo 7 - Random Numbers

panurgo ha scritto:Si consiglia la lettura di http://www.library.cornell.edu/nr/cbookcpdf.html, capitolo 7 - Random Numbers

Il libro in questione è x me un mito assoluto. Io avevo quello in Fortran, perso in un trasloco assieme al mio adorato William Blake con illustrazioni di Dorè

mathmum ha scritto:[...] perso in un trasloco assieme al mio adorato William Blake con illustrazioni di Dorè

P.S.: quanto al NR in Fortran, lo scarichi gratis allo stesso sito

Ciao Zerinf, ciao a tutti!
vi saluto con affetto e chiedo scusa per la lunga assenza dovuta a impegni di lavoro pressantissimi.

Questo problema mi è piaciuto e azzardo una spiegazione elementare... ma sono molto arrugginito.

Chiamo:
F=fronte
R=retro

Rappresento un soldato così:
FR oppure RF, a seconda di come è orientato.

Una fila di soldati potrebbe essere questa:

FR-FR-RF-FR-FR-RF-RF-RF-FR

Passo ad una rappresentazione numerica ed elimino i trattini:
FR=2
RF=1

Esempi:
RF-FR = 12
FR-RF = 21

La fila diventa:
221221112

Posso leggere la fila come se fosse un grande numero intero costituito soltanto dalle cifre 1 e 2.

Operando i dietrofront come detto nel problema, in questa lista, ad ogni passaggio OGNI 12 DIVENTA 21.

Esempio:
221221112
222121121

Visto che ogni 12 diventa 21, è evidente che ad ogni passaggio il numero che rappresenta la fila di soldati diventa sempre più grande.

Inoltre il processo va avanti fin che ci sono dei 12.

Il numero però non può crescere indefinitamente, ad un certo punto raggiungerà il massimo e il processo avrà termine.
Qual è il massimo?
Tutti i 2 all'inizio e tutti gli 1 alla fine.

Come volevasi?

Prosegue l'esempio:
221221112
222121121
222211211
222212111
222221111

Salvo errori & omissioni.

Gianfranco Bo

la mia notazione prendeva spunto da Est e Ovest, invece che F e R, ma la sostanza non cambia
Il fatto è che ci sono posizioni stabili che non sono dei "massimi", nel senso proposto da GF
A parte le serie
1111111111
e
2222222222
che devono essere tali dall'inizio,
abbiamo
2111111111
2211111111
2222222221
2222222211
eccetera
che sono stabili, e che possono essere raggiunte da molte posizioni prima che sia raggiunto il massimo previsto da GF
SE&O

P.S.
forse il problema risulta più completo se l'istruzione/algoritmo di comportamento viene modificata in
"se NON vedi una nuca, fai dietro-front"
ciò comporta che i due militi alle estremità, se rivolti all'esterno, fanno dietro-front, al contrario di come abbiamo previsto finora.
Si potrebbe anche dare l'istruzione di attuare un tale comportamento fino ad un numero n di volte (magari correlato al numero dei soldati presenti...)
Dico così, tanto per complicare un po' le cose....

Ciao Enrico,
prima di affrontare casi più complessi, vorrei capire bene le tue osservazioni.

a) la mia dimostrazione non esclude che esistano configurazioni stabili fin dall'inizio, nel qual caso nessuno fa dietro-front.

b) in particolare,

delfo52 ha scritto:2111111111
2211111111
2222222221
2222222211
eccetera
che sono stabili, e che possono essere raggiunte da molte posizioni prima che sia raggiunto il massimo previsto da GF
SE&O

Se hai tempo, potresti per favore spiegare meglio cosa intendi?

Gianfranco

La soluzione di Gianfranco(che onore vederlo su un mio topic!deve proprio esservi piaciuto,é un peccato che non sia una mia opera) mi sembra accettabile la soluzione di Bo,ma é valida solo se la fila di soldati ha un numero pari di elementi(ogni coppia viene sostituita con un numero).Ho pensato però,*beep* nasi lumine,che potremmo altri soldati immaginari ad una fila dispari per trasformarla in una maxifila pari e poi studiare le suddivisioni della maxifila,ma ripeto che é solo una pensata flash forse peregrina.
Riguardo alla probabilità P che una fila di N elementi non si modifichi(sembra proprio di poter dire che se una fila non é ordinata non lo diventerà seguendo questo algoritmo) penso di pter dire che é $P=\displaystyle \frac {N+1}{2^N}$.Sto studiando le catene di trasformazioni delle varie file di soldati(propongo d'ora in poi di definire 1 come Est e 0 come Ovest,per molte ragioni questo rende tutto più semplice).
Saludos barbudos a tutti e soprattutto a GB,é bello trovare dei messaggi dopo tanto tempo.
Ciao!
Zerinf

accetto la nomenclatura di Zerinf:
0 = ovest = sinistra = FR
1 = est = destra = RF

Quello che volevo mostrare è che tutte le configurazioni in cui non appare la coppia "1-0" (1-2 negli esempi di GFBo) sono ferme, ad es
0011111
0111111
0000011
a prescindere dal numero dei soldati, i ripetuti dietro-front portano sempre, prima o poi, a una situazione in cui tutti gli 0 stanno a sinistra e tutti gli 1 a destra, e il gioco si ferma

Ciao Zerinf, ciao Enrico,
sì, questo problema mi piace, e vorrei affrontare anche le parti più impegnative, ma devo dirvi -simpaticamente- una cosa:

a) o che io, in questi mesi di attività di basso livello, mi sono rinco.....ito più di quanto lo fossi già prima,

b) o che non mi sono spiegato bene...

-------------
1) per Zerinf, dici:

mi sembra accettabile la soluzione di Bo, ma é valida solo se la fila di soldati ha un numero pari di elementi (ogni coppia viene sostituita con un numero).

Io ti rispondo: l'esempio che ho fatto è formato da 9 soldati, proprio un numero dispari!

Inoltre: non è vero che ogni coppia di soldati è sostituita da un numero; ogni soldato è sostituito da una coppia di lettere che ne indica l'orientamento (FR, RF), e ogni coppia di lettere è sostituita da un "digit".

Poi, nella sequenza, considero le coppie di "digit" che mi interessano, cioè quelle corrispondenti ai soldati che stanno l'uno di fonte all'altro. Pari o dispari che siano i soldati, è ininfluente sul ragionamento.
Esempi:
11222212211
si voltano le coppie tra parentesi:
1(12)222(12)211

111222122
si voltano le coppie tra parentesi:
11(12)22(12)2

Inoltre dici:

se una fila non é ordinata non lo diventerà seguendo questo algoritmo

E' verissimo, infatti l'algorimo CONSERVA il numero di 2 e di 1 ovvero CONSERVA il numero dei soldati rivolti in una certa direzione.
Cioè, se all'inizio ci sono n soldati rivolti a destra e m rivolti a sinistra, così sarà anche alla fine.
Questo è evidente, basta pensare che fanno dietro front a coppie.
E' come se avessi delle monete su un tavolo e le capovolgessi due alla volta, una TESTA e una CROCE: i numeri di teste e di croci rimarrebbero costanti.
-------------

2) per Enrico,
concordo con tutto quello che hai scritto ma non riesco ancora a vedere alcuna contraddizione con la mia dimostrazione.
Adottando la tua rappresentazione:
0 = ovest = sinistra = FR
1 = est = destra = RF

se all'inizio si forma, ad esempio una fila così:
(FR)-(FR)-(FR)-(FR)-(FR)-(RF)-(RF)
0000011
è stabile fin dall'inizio e nessuno si muove.

Con questa rappresentazione, la mia dimostrazione cambia così:
a) ogni 10=(RF)-(FR) diventa 01=(FR)-(RF)
b) quindi il numero che rappresentano la fila di soldati diventa sempre più piccolo fino a raggiungere il MINIMO e non il massimo, cioè tutti gli 0 a sinistra e tutti gli 1 a destra.
Siccome 0000011 è già il MINIMO numero che si può scrivere con cinque 0 e due 1, la configurazione stabile è raggiunta.

La prima domanda di Zerinf è:

La domanda é: se il numero di soldati é finito, potete dimostrare che prima o poi tutti i soldatini finiranno in una situazione di equilibrio?

Se la situazione è in equilibrio già all'inizio, è evidente che nessuno si muove.
---------------

Nuovamente per Enrico:
Invece, se i soldati:
a) fossero in cerchio, oppure
b) ai due estremi della fila ci fossero due specchi, oppure
c) la regola fosse "se NON vedi una nuca, fai dietro-front", come hai detto tu,

allora non si raggiungerebbe l'equilibrio statico, ma un "equilibrio cicliclo". Facile da trovare ma non immediato da dimostrare.
---------------

Ipotizzando una serie di governi di centro-destra e di centro-sinistra, qual è la configurazione migliore?

Ora è meglio che mi fermo...

Gianfranco

hai ragione !

Ciao Enrico,

mi permetto di citarti.

delfo52 ha scritto:hai ragione !

La tua risposta è giunta in 10 minuti!
E di nuovo non la capisco.

Intendi forse che ho ragione quando dico che:
a) "mi sono rinco.....ito più di quanto lo fossi già prima"
b) "non mi sono spiegato bene"
c) "Ora è meglio che mi fermo"

o cos'altro?

Ciao

Gianfranco

...

Wow... che bella esperienza vedere un bel ragionamento!
Gianfranco, grazie!
(Grazie anche ad Enrico e a 0-§.)

Bruno


PS - Ops... Naturalmente non mi riferisco al msg che vien subito prima
di questo