Golbugs 2

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Golbugs 2

Messaggio da Catraga »

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).
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Messaggio da fph »

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
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
MindFlyer

Messaggio da MindFlyer »

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ò! :D
Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim »

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?
pps
Messaggi: 104
Iscritto il: 01 gen 1970, 01:00
Località: un posto tranquillo

Messaggio da pps »

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ù.
Thanks to Joim
Avatar utente
dimpim
Messaggi: 300
Iscritto il: 01 gen 1970, 01:00

Messaggio da dimpim »

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... :oops: :P
MindFlyer

Messaggio da MindFlyer »

dimpim ha scritto:Ah, sì, giusto, scusate... :oops: :P
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.
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

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.
pps
Messaggi: 104
Iscritto il: 01 gen 1970, 01:00
Località: un posto tranquillo

Messaggio da pps »

Catraga ha scritto:L'altra (informatica) prevede l'equivalenza del problema all'algoritmo del BubbleSort.
Forse sono OT, ma cos'è l'"algoritmo del BubbleSort"?
Thanks to Joim
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

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...
:lol:
pps
Messaggi: 104
Iscritto il: 01 gen 1970, 01:00
Località: un posto tranquillo

Messaggio da pps »

no, è chiaro, grazie
Thanks to Joim
herbrand
Messaggi: 56
Iscritto il: 02 nov 2005, 19:58

Messaggio da herbrand »

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)?
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

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.
herbrand
Messaggi: 56
Iscritto il: 02 nov 2005, 19:58

Messaggio da herbrand »

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...
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

Confermo la soluzione di Simo! :D
Rispondi