Bugs

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

Bugs

Messaggio da Catraga »

Un problemino che nasce da un articolo dal Mathematical Intelligencer:

Abbiamo delle scatolette numerate da -1 a infinito. Ognuna ha il fondo di un colore: rosso o verde.
Nella scatoletta numero 1 mettiamo un Goldbug. I Goldbug hanno la seguente caratteristica: se si trovano in una scatoletta con il fondo verde, saltano nella scatoletta con il numero successivo, altrimenti saltano due scatolette indietro. Dopo aver saltato, il fondo della scatoletta di partenza cambia colore (da verde diventa rosso e di viceversa). Se un Goldbug capita nella scatoletta 0 o -1 (queste non hanno colore) muore. Ci sono almeno una scatola verde ed una scatola rossa.

Problema 1:
Dimostrare che un Goldbug non puo' avere un cammino periodico.

Problema 2:
Dimostrare che la vita di un Goldbug e' limitata.
Ultima modifica di Catraga il 31 mar 2005, 14:02, modificato 1 volta in totale.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

...mmmm... Se sono tutte verdi, il G.b. salta sempre in avanti... Manca un'ipotesi?
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

(Correzione testo)
Avatar utente
phi
Moderatore
Messaggi: 350
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi »

Se ho capito bene, dovrebbe succedere sempre qualcosa del genere. Prima o poi il Goldbug dovrà incontrare una scatola rossa, e allora il suo destino sarà “segnato”; se la 1 o la 2 sono rosse, è chiaro che finisce subito nella -1 o nella 0 e muore. Altrimenti tutte le scatole che precedono quella rossa (e seguono la numero 0) erano verdi, e il Goldbug è saltato dentro a ciascuna, visto che nelle verdi si sposta in avanti di un passo alla volta; quindi ora quelle scatole sono tutte rosse. Se la scatola in cui ora il Goldbug si trova (la prima rossa incontrata) è pari, allora salterà all'indietro in tutte quelle pari e finirà nella 0; se è dispari, finirà nella -1. La vita del Goldbug è quindi limitata, e il suo percorso non è periodico: si sposta in avanti di 1 finché non trova una rossa e poi indietreggia di 2 finché non cade nella 0 o nella -1.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

E brava Phi.

E visto che era facile, complichiamoci un po' la vita.

Allunghiamo la fila di scatolette e arriviamo fino a -2007.

EDIT 2: Supponiamo che esista almeno una scatoletta >1 con il fondo inizialmente rosso. Il Goldbug parte da 1.

Il Goldbug muore se cade prima della scatoletta -2005. Dimostrare che le tesi 1. e 2. del quesito iniziale sono ancora vere.

Ciao. M.
Ultima modifica di Marco il 04 apr 2005, 14:39, modificato 1 volta in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
phi
Moderatore
Messaggi: 350
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi »

Scusa, ma il Gb parte sempre dalla 1? Anche con l'edit, c'è qualcosa che non mi torna... Metti che la 1 è rossa e tutte le altre sono verdi. Immagino che anche la 0 e la -1 siano colorate, no? Il gb dovrebbe fare un percorso tipo 1 -1 0 1 (ora è verde) 2 3 4... e via così; e in questo modo si direbbe immortale... Non so, forse mi sfugge qualcosa di stupido. :?
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Eh, quando uno ha ragione, ha ragione...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
phi
Moderatore
Messaggi: 350
Iscritto il: 01 gen 1970, 01:00
Località: Bath, UK
Contatta:

Messaggio da phi »

Be', visto che oggi entro alla seconda ora perché manca la prof. di matematica :D , a costo di arrivare in ritardo a scuola, proviamoci...

Vorrei dimostrare che, quando il g.b. si trova in una scatola verde, diciamo k, c'è almeno una scatola col fondo rosso > k.
In questa scatola verde può essere arrivato in due modi:
a) da una V in k-1;
b) da una R in k+2.
Se fosse (a) possiamo porci di nuovo la stessa domanda, e abbiamo le stesse due opzioni (chiaramente con i numeri delle scatole diminuiti di 1). Se continuiamo a risalire all'indietro scegliendo (a), fino ad arrivare alla scatola 1 di partenza, significa che il g.b. non ha ancora mai incontrato una scatola R (le scatole >=1 e <=k sono verdi); perciò, per l'ipotesi :wink: esiste una R > k.
Se prima o poi scegliamo (b), raggiungiamo una configurazione di questo tipo:
VVR*VV...V. La scatola seguita da asterisco è quella in cui si trova il g.b. Come è arrivato in R? Non andando avanti, sennò la scatola dietro ora sarebbe R (va scartata l'opzione (a)); rimane solo l'opzione (b). Dovremo continuare a scegliere (b) finché non “usciamo” dalla zona in cui abbiamo già stabilito le V, cioè finché non superiamo k. A questo punto, o ci troviamo in k+1 o in k+2; se siamo in k+1, stesso problema, la (a) non funziona, andiamo in k+3. La nostra scelta torna libera.
Se scegliamo (b) fino a tornare alla 1, sempre per ipotesi c'è una rossa maggiore di 1, e vuol dire k era minore di 1.
Se prima o poi scegliamo (a), una Rossa > k rimane “intoccata”. Il percorso del g.b. sarebbe: ...RXRXRXRV*R... ->...RXRXRXRRR*... -> ... RXRXRXR*RV.
Perciò, se il g.b. è in una scatola k verde, esiste una rossa >k.

Ora, a un percorso in avanti del g.b. lungo l, visto che prima o poi arriverà una rossa, corrisponde un percorso all'indietro lungo l+2 o l+1, comunque >l. Cioè:
XV*V...R -> XRV*...R -> XRR...R* -> XRR*...V -> X*RV...V
Questo significa che il g.b. tenderà sempre ad andare indietro e, prima o poi, morirà.
Inoltre, perché abbia un percorso periodico, dovrebbe compiere tanti passi in avanti quanti ne compie all'indietro, il che, come abbiamo appena visto, è impossibile.

:shock: Uffa, non credevo che sarebbe venuta così lunga! C'era modo di fare qualcosa tipo tre righe e via? E mi sa che è anche un tantino ingarbugliata, perché ho i goldbug che mi saltano su e giù nella testa... ehm, be', se qualcuno ha letto fin qui, complimenti! :)
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

Ok. Buona. Una piccola "lezione di stile"; ti dico come avresti potuto formulare la stessa idea, senza tanti giri di parole.

Ricordo il claim di Phi: se il G.b. si trova in k, esiste una scatola rossa >= k. Anzi, dimostro per induzione il seguente più forte:

Claim: se il G.b. si trova in k, esiste una scatola rossa >= k; inoltre se l'unica scatola così è la k, allora l'ultimo salto è stato in avanti.

All'inizio esiste una rossa >k per ipotesi.

Se esiste una scatola rossa >k, il G.b. va in k-2 o in k+1, ma in entrambi i casi il claim resta vero anche dopo il salto successivo.

Se invece non esiste tale scatola, l'unica scatola rossa >= del G.b. è la k, quindi il G.b. è arrivato per forza da un salto in avanti (ip. induttiva), e quindi k-1 è rossa. Dopo il salto, il G.b. si ritrova ora in k-2 e il claim è ancora vero. []

L'utlima parte del discorso ("va in avanti tot passi, torna indietro totaltri, si ritrova più indietro di dov'era partito") va bene.

Prossimamente, appena il tempo me lo permette, vi voglio fare vedere un'altra idea (un po' più contorta del discorso pulito di Phi), che però è radicalmente diversa e... che piacerà (spero) ai nostri amici fisici. Stay tuned.

M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

No. La mia wonderful idea non torna.

Funziona bene solo nel caso in cui il G.b. muore a zero, come all'inizio. Per il caso generale, si potrebbe fare qualcosa, ma si complica talmente che, considerando la sol. di Phi così semplice, diventa ridicolo.

Vi racconto comunque a grandi linee l'idea, perché è interessante. Si tratta del vecchio trucco del potenziale.

Avrei definito un'energia di stato del Goldbug, come una funzione non negativa della sua posizione.

Poi avrei definito un'energia di campo, ottenuta sommando i contributi delle sole scatole verdi (il Goldbug si energizza se va avanti, quindi quando le scatole transiscono da verdi a rosse, il campo sta cedendo energia al G.b.; viceversa se l'energia di stato decade a favore del campo)

Definendo bene le funzioni di energia di campo e stato si può fare in modo che l'energia totale si conservi nei salt'in avanti e diminuisca nei salt'indietro.

Questo mi sarebbe servito per mostrare che il cammino del G.b. è limitato dall'alto. Dato che è facile far vedere che il G.b. non può fare un cammino limitato, l'unica è che sia illimitato dal basso. E quindi, alla lunga va verso $ -\infty $.
Né, tanto meno, essere periodico.

Tutto molto bello. Peccato che, se leggete bene la dimostrazione per induzione del post precedente, è altrettanto facile far vedere che la prima scatola rossa > G.b alla partenza non può mai essere scavalcata. E quindi il cammino è limitato dall'alto senza tanti giri di parole.

Ok. Phi: 1 - Marco: 0.

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Rispondi