27. Giuro che questa non è spam penetra la staffetta.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

27. Giuro che questa non è spam penetra la staffetta.

Messaggio da Troleito br00tal »

Siano date $n$ lampadine, eventualmente accese o spente, disposte in cerchio. Vi sono due
mosse possibili:
-$a$) scegliere una qualsiasi tra le $2^n$ congurazioni possibili;
-$b$) accendere o mantenere accesa ogni lampadina le cui vicine sono nello stesso stato e
spegnere o mantenere spenta ogni altra lampadina.
Si determini, in funzione di $n$, il numero minimo di mosse $a$ che bisogna applicare, iniziando
da una configurazione a propria scelta, per ottenere esattamente una volta ognuna
delle $2^n$ configurazioni.
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Ho un dubbio: applicando la mossa b) la configurazione si aggiorna solo dopo aver sistemato lo stato di tutte le lampadine? Oppure si aggiorna ogni volta che una lampadina cambia stato? Se ho interpretato bene (prima interpretazione) dovrebbe venire $3\cdot 2^{n-2}$ con $n$ pari e $2^{n-1}$ con $n$ dispari. Se è giusto metto la dimostrazione.
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da kalu »

xXStephXx ha scritto:Ho un dubbio: applicando la mossa b) la configurazione si aggiorna solo dopo aver sistemato lo stato di tutte le lampadine? Oppure si aggiorna ogni volta che una lampadina cambia stato?
Prima interpretazione.
xXStephXx ha scritto:Se ho interpretato bene (prima interpretazione) dovrebbe venire $3\cdot 2^{n-2}$ con $n$ pari e $2^{n-1}$ con $n$ dispari. Se è giusto metto la dimostrazione.
Yep. Mettila pure :)
Pota gnari!
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Ok, me l'ero preparata da prima :D

Cerco di trovare quante sono le configurazioni di lamapadine generabili da altre configurazioni.

-$n$ dispari: $n=2x+1$.
Dimostro che in questo caso le configurazioni generabili da altre configurazioni sono $2^{n-1}$.
Numero le lampadine a seconda della loro posizione dalla $0-esima$ fino alla $2x-esima$. Voglio ottenere una configurazione generabile da un'altra configurazione. Fisso a piacimento lo stato di tutte le lampadine eccetto la $0-esima$ e dimostro che se voglio fare in modo che tale configurazione sia generabile allora lo stato della $0-esima$ lampadina è univocamente determinato. Infatti se la lampadina $1$ è accesa, allora nella configurazione generatrice la lampadina $0$ e la lampadina $2$ devono essere dello stesso stato. (Suppongo che dabbano essere dello stato A). Viceversa se la lampadina $1$ è spenta allora nella configurazione generatrice lo stato della lampadina $0$ sarà $A$ mentre lo stato della lampadina $2$ sarà $B$ (wlog). Ora che ho ottenuto lo stato della $0$ e della $2$ ripeto lo stesso ragionamento con la terza lampadina fissando lo stato che deve avere la quarta lampadina nella configurazione generatrice. Ripeto lo stesso procedimento per induzione fino a fissare lo stato che deve avere la $2x-esima$ lampadina nella configurazione generatrice. Dopodichè ricomincio il giro ma stavolta ragionando sullo stato delle lampadine di posto pari. Quindi fisso lo stato di tutte le lampadine di posto dispari nella configurazione generatrice. Ora ho fissato univocamente (A o B) lo stato delle lampadine di posto $2x$ e $1$ nella configurazione generatrice. Di conseguenza affinchè la configurazione sia generabile è fissato anche lo stato della lampadina di posto $0$ univocamente. (Se nella configurazione generatrice la $2x$ e la $1$ hanno lo stesso stato, allora si genera una configurazione in cui la $0$ è accesa, altrimenti sarà spenta).
Dunque affinchè la configurazione sia generabile posso porre a piacimento lo stato di tutte le lampadine tranne una, quindi le configurazioni generabili sono $2^{2x}$ ovvero $2^{n-1}$. Di conseguenza le configurazioni non generabili sono $2^n-2^{n-1}=2^{n-1}$. Perciò come minimo devo applicare la mossa $a)$ per ognuna delle $2^{n-1}$ configurazioni non generabili.

$n$ pari:
Senza ripetere il ragionamento di prima, in modo del tutto analogo, ho che se voglio costruirmi una configurazione generabile posso fissare a piacimento lo stato di tutte le lampadine tranne $2$, il cui stato sarà unicovamente determinato. Quindi stavolta le configurazioni generabili da altre sono $2^{n-2}$. Quelle non generabili sono $3\cdot 2^{n-2}$.


Ora dimostro che effettivamente è sufficiente applicare la mossa a) tante volte quante sono le configurazioni non generabili.
Comincio con la mossa $a)$ in modo che ho una configurazione non generabile da altre. Genero tutte le configurazioni che posso generare applicando in serie le mosse b) da quella. Quando si ripetono riapplico la mossa a) ottenendo un'altra configurazione non generabile e ripeto il procedimento applicando la mossa a) ogni volta che con una mossa b) uscirebbe una configurazione già uscita prima. Così ho applicato la mossa a) tante volte quante sono le configurazioni non generabili e ho la certezza che ogni configurazione non sia uscita più di una volta. Inoltre le configurazioni generabili ci sono tutte, in quanto supponendo per assurdo che ne manca una, allora manca anche la configurazione che la genera e a sua volta manca anche la configurazione che genera quest'ultima. Ma siccome le configurazioni generabili sono in numero finito prima o poi si arriva ad una configurazione non generabile che non può mancare in quanto le ho messe tutte con la mossa a). Assurdo, quindi escono sia tutte le configurazioni generabili sia tutte quelle non generabili che complessivamente sono tutte le $2^n$ configurazioni possibili.
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da kalu »

xXStephXx ha scritto:Inoltre le configurazioni generabili ci sono tutte, in quanto supponendo per assurdo che ne manca una, allora manca anche la configurazione che la genera e a sua volta manca anche la configurazione che genera quest'ultima. Ma siccome le configurazioni generabili sono in numero finito prima o poi si arriva ad una configurazione non generabile che non può mancare in quanto le ho messe tutte con la mossa a).
E cosa ti assicura che la generatrice della generatrice .... della generatrice di una certa funzione generabile X non sia ancora X, cioè che non si chiuda un ciclo?
Pota gnari!
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Potrebbe esserci un ciclo in effetti.. però dal momento che X essendo generabile non può essere alla base della catena, prima o poi salendo verso l'alto la configurazione che genera X non dovrebbe dipendere da X (altrimenti ci sarebbe sempre un ulteriore X ancora più in alto) o sbaglio?
Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da kalu »

xXStephXx ha scritto:Potrebbe esserci un ciclo in effetti.. però dal momento che X essendo generabile non può essere alla base della catena, prima o poi salendo verso l'alto la configurazione che genera X non dovrebbe dipendere da X (altrimenti ci sarebbe sempre un ulteriore X ancora più in alto) o sbaglio?
Che vuoi dire con "X generabile non può essere alla base della catena"?
Pota gnari!
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Intendevo che, dovendo generare X, la prima volta che viene generato non può essere generato da una configurazione che dipende da X. (la configurazione generatrice non è univoca). Quindi se manca X, manca anche la configurazione che genera X che a sua volta prima o poi non potrà dipendere da se stessa e così via.
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Allora provo a scrivere bene questa parte :D (le cose si fanno complicate :mrgreen: )
Anzitutto una configurazione generabile può essere generata anche da più configurazioni diverse (basta ad esempio invertire gli A con i B che ho usato prima).

Ora supponendo che ci sia un ciclo di configurazioni $(x_1,x_2,...,x_k)$, se tale ciclo può essere ottenuto applicando mosse b) da una mossa a) con cui prendo una configurazione non generabile, allora la prima configurazione di tale ciclo che compare facendo le mosse b) in successione, deve essere generata da una configurazione $C$ non appartente a quel ciclo e ciò è dovuto al fatto che altrimenti non sarebbe la prima configurazione del ciclo ad apparire unito al fatto che la configurazione ottenuta con la mossa a) (alla base di tutte) non apparterrà mai a nessun ciclo essendo non generabile.


Quindi supponendo che una configurazione di quel ciclo $x_i$ non compaia da nessuna configurazione generata partendo dalle mosse a), allora ne seguono due cose:
1) non compare nessun altro elemento di quel ciclo, altrimenti comparirebbe pure $x_i$
2) non compare nemmeno la configurazione $C$ NON appartenente a quel ciclo e che genera il primo elemento di quel ciclo.
Quindi siccome la mancanza di un ciclo implica anche la mancanza di un'altra configurazione non appartenente a quel ciclo e che le configurazioni non sono infinite, prima o poi si arriva ad una non generabile che invece non può mancare concludendo l'assurdo di prima.
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da Troleito br00tal »

Uppo e hinto: dove usi il fatto che ogni configurazione generabbbbile può essere generata da almeno due configurazioni?
xXStephXx
Messaggi: 472
Iscritto il: 22 giu 2011, 21:51

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da xXStephXx »

Non ricordo molto bene, però ad esempio lo uso nel fatto che c'è un elemento del ciclo $(x_1,x_2,...,x_n)$ che viene generato sia da un altro elemento dello stesso ciclo, sia da $C$ che non appartiene a quel ciclo. Ma di preciso cos'è che mi manca per completare la dimostrazione?
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: 27. Giuro che questa non è spam penetra la staffetta.

Messaggio da Troleito br00tal »

xXStephXx ha scritto:Non ricordo molto bene, però ad esempio lo uso nel fatto che c'è un elemento del ciclo $(x_1,x_2,...,x_n)$ che viene generato sia da un altro elemento dello stesso ciclo, sia da $C$ che non appartiene a quel ciclo. Ma di preciso cos'è che mi manca per completare la dimostrazione?
Nulla, semplicemente (probabilmente per colpa mia che sono dislessico con le dimostrazioni) non era emerso questo fatto che E' tutto il problema. Puoi andare :)
Rispondi