OliForum Matematico

Dopo aver stecchito dei poveri Goldbugs in delle scatolette colorate, i ricercatori dell' Universita' Bovina hanno condotto degli esperimenti ed hanno scoperto la seguente cosa: i Goldbugs sono timidi.

Abbiamo n Goldbugs in fila. Ogni Goldbug puo'
guardare a destra $ \geq $
guardare a sinistra $ \leq $.
Poiche' essi sono timidi, se due Goldbugs si fissano negli occhi
$ \geq\leq $
si voltano entrambi dall'altra parte
$ \leq\geq $.
Data una fila di n Golbugs questi scambi avvengono tutti contemporaneamente. Dimostrare che prima o poi tutti i GoldBugs raggiungono la pace interiore (ovvero non ci sono piu' coppie di Golbugs che si guardano in cagnesco).

Era un problema americano riportato in un vecchio giornalino con uno "wording" a mio avviso molto divertente:
I soldati di un esercito sono disposti in una lunga fila, fronte al generale. Il generale ordina ai soldati di girarsi verso sinistra; non tutti i soldati pero' hanno ben chiaro quale sia la destra e quale la sinistra, quindi alcuni di loro si voltano dalla parte sbagliata. Quando due soldati si trovano immediatamente uno di fronte all'altro, si accorgono che c'e' qualcosa che non va e, un secondo piu' tardi, contemporaneamente, tutti e due pensano di aver sbagliato direzione e si voltano dall'altro lato.
Dimostrare che dopo un tot di secondi i soldati sono voltati tutti dalla stessa parte (non necessariamente quella giusta)

Molto divertente (ma sostanzialmente isomorfo)
ciao,
--federico

Scusa fph, forse volevi dire che dopo un tot di secondi raggiungono una configurazione stabile, ma non necessariamente saranno tutti girati dalla stessa parte.
Wording fighissimo, però!

MindFlyer ha scritto:non necessariamente saranno tutti girati dalla stessa parte

Perché il primo e l'ultimo della serie possono anche essere voltati dalla parte opposta senza creare problemi, giusto?

perché, divisa la fila in due parti, se la parte a sinistra guarda a sinistra e quella a destra guarda a destra, allora non si girano più.

pps ha scritto:perché, divisa la fila in due parti, se la parte a sinistra guarda a sinistra e quella a destra guarda a destra, allora non si girano più.

Ah, sì, giusto, scusate...

dimpim ha scritto:Ah, sì, giusto, scusate...

Non ti scusare, era giusta anche la tua versione!
Nel senso che a qualunque configurazione stabile si possono aggiungere 2 soldati agli estremi girati in versi opposti senza destabilizzare la fila. Quella di pps era solo una caratterizzazione delle configurazioni stabili.

Ci sono due soluzioni, secondo me molto belle.
Una (matematica) prevede la creazione di un potenziale (vedere interventi di marco nel post Bugs di questa sezione).
L'altra (informatica) prevede l'equivalenza del problema all'algoritmo del BubbleSort.

Catraga ha scritto:L'altra (informatica) prevede l'equivalenza del problema all'algoritmo del BubbleSort.

Forse sono OT, ma cos'è l'"algoritmo del BubbleSort"?

Supponi di avee una sequenza di numeri da ordinare. L'algoritmo si basa sulla seguente procedura:
SUB test
Scorri la lista:
sono in ordine crescente?
RETURN -1
altrimenti
RETURN la posizione del primo elemento che viola la condizione di crescenza

SUB Bubblesort
T = test(lista)
DO UNTIL T = -1
swap(lista(T,T+1))
T= test(lista)
LOOP

Non siate pignoli, lo so che il codice non e' ne' in pseudocodice ne' in codice. ma penso che questo sia il metodo piu' rapido per descivere l'algoritmo. Se proprio insistete vi scrivo il codice in linguaggio macchina...

no, è chiaro, grazie

Up!

Ci sono due soluzioni, secondo me molto belle.
Una (matematica) prevede la creazione di un potenziale

Francamente non mi è molto chiara, c'è qualcuno disponibile a spiegarla bene per intero (risolvendo il bel quesito)?

Per "potenziale" credo Catraga intenda qualcosa del genere:

definiamo "potenziale di giramento" di un Goldbug i Goldbugs che lui vede e che sono girati verso di lui. Dopo che una coppia si è girata si vede facilmente che il "potenziale di giramento" degli altri goldbugs è rimasta invariata mentre il loro potenziale si è scambiato ed è diminuito di 1. Quindi il potenziale totale (somma di tutti i potenziali) è diminuito di 2. Per la discesa infinita il potenziale (che sarà sempre positivo) prima o poi sarà stabile e quindi anche la situazione rimarrà invariata.

Grazie, e aspettiamo le conferme di Catraga sulla sua soluzione molto bella!
Trovare in quanti passaggi i bugs arrivano ad una situazione stabile non sembra così facile e nemmeno ad es. dire per quali configurazioni arriveranno alla quiete in un numero pari di passaggi...

Confermo la soluzione di Simo!