Lampadine

[axpgn]

Disponiamo in cerchio $n$ lampadine (due come minimo), inizialmente tutte accese.
Procedendo in senso orario e partendo da una lampadina qualsiasi, operiamo come segue:
- se la lampadina è accesa, osserviamo quella successiva; se è accesa la spegniamo, se è spenta la accendiamo.
- se la lampadina è spenta non facciamo niente.
In entrambi i casi passiamo alla lampadina successiva e ripetiamo la stessa procedura, e così via ...
Dimostrare che prima o poi le lampadine saranno di nuovo tutte accese.

Cordialmente, Alex

[andomito]

Ci provo, ma più con considerazioni generali che con formule.

La legge data ammette anche una legge inversa, applicabile per vedere come era lo stato delle lampadine al tempo t-1:
- procediamo in senso antiorario, se la lampadina precedente è accesa, sposto l'interruttore della mia lampadina e passo alla lampadina precedente.
- se la lampadina precedente è spenta lascio l'interruttore com'è e passo alla lampadina precedente.
Sia la legge data, sia quella inversa, sono univoche, nel senso che individuano una e una sola configurazione risultante.
Pertanto la corrispondenza tra due configurazioni è biunivoca.
Essendo n un numero finito, sono finite le possibili combinazioni della serie di configurazioni risultanti, e non è possibile che si instaurino loop che escludono una delle configurazioni effettivamente ricorse (per la biunivocità della relazione). Ergo, data una qualunque configurazione di partenza, si svilupperà un loop di configurazioni ricorsivo.
I loop sono sicuramente più di uno (almeno c'è il caso di configurazione di partenza "tutte spente" che si chiude immediatamente) ma sono tutti necessariamente ricorsivi.

[axpgn]

Sì, sostanzialmente è OK

Preliminarmente si può notare che le lampadine non saranno mai tutte spente, questo perché per spegnere l'ultima ne occorre un'altra accesa; non è un aspetto necessario alla risoluzione del problema ma è rassicurante .
Per inciso, la situazione "tutte spente" non è "immediatamente" finita, in quanto lo stato del sistema non dipende solo dalla configurazione acceso/spento delle lampadine ma anche dalla posizione della lampadina di "riferimento", se così si può dire.
Difatti il numero degli stati è $n2^n$, grandino ma finito .
Questo, unito al fatto che ogni stato è raggiungibile solo da un unico altro ben definito stato, implica che ci sia un circuito chiuso (di stati), che non vuol dire che tutti gli stati siano compresi nel circuito ma che quelli che ci sono, ci saranno sempre e sempre nello stesso ordine.
Per cui, sicuramente, ci sarà lo stato iniziale, che nel nostro caso è "tutte accese (e partenza da $p$)", anzi sarà il primo ad essere ripetuto.

Cordialmente, Alex

[andomito]

"axpgn":
...Per inciso, la situazione "tutte spente" non è "immediatamente" finita, in quanto lo stato del sistema non dipende solo dalla configurazione acceso/spento delle lampadine ma anche dalla posizione della lampadina di "riferimento"...

Dipende dal sistema di riferimento scelto.
Se invece di un riferimento fisso adotto un sistema di riferimento che si sposta di un passo per ogni controllo, ho che la situazione "tutte spente, controlliamo la lampadina numero 1" si ripropone immediatamente.
Il cambio di riferimento è senz'altro ammissibile poiché per la soluzione cercata (tutte accese) è irrilevante a che punto sto con il controllo.

[axpgn]

Eh, no, c'è un problema con il tuo ragionamento …

Se è vero che l'obiettivo richiesto ("tutte accese") è meno "rigido" rispetto alla richiesta di avere esattamente la stessa configurazione ("tutte e accese e stessa lampadina di partenza"), gli stati però si differenziano sempre anche per la posizione della lampadina di riferimento, altrimenti, se così non fosse, cadrebbe uno dei punti su cui si basa la risoluzione ovvero l'unicità dello stato di provenienza. In tal caso, ti bastano due lampadine per notare che si arriva a "tutte accese" senza tornare allo stato di partenza ma questo non garantisce affatto che per un $n$ qualsiasi non si finisca in un loop senza uscita
Peraltro avere un sistema di riferimento "mobile" significa risolvere un problema diverso ... IMHO

Cordialmente, Alex

[andomito]

Sia la legge data, sia quella inversa, possono essere trasformate nel sistema mobile rimanendo comunque univoche.
La corrispondenza fra stati è dunque biunivoca anche nel sistema mobile.
Ciò (per diversi assetti di partenza) potrebbe comportare che i loop si chiudano prima (con assetti omologhi a quello di partenza, ma spostati di un certo numero di posizioni, che risulterebbero indistinguibili da quello di partenza con il sistema mobile e che in linea teorica andando avanti potrebbero chiudersi nel sistema assoluto in un sottoloop che taglia fuori la serie di posizioni iniziale), ma comunque nel sistema mobile il loop ci sarebbe.
L'indeterminatezza che individui nel sistema mobile ci potrebbe essere solo se la configurazione di partenza fosse un'altra (e quindi il riproporsi della soluzione spostata di n posizioni non mi soddisfa con certezza).

[axpgn]

"andomito":Sia la legge data, sia quella inversa, possono essere trasformate nel sistema mobile rimanendo comunque univoche.
La corrispondenza fra stati è dunque biunivoca anche nel sistema mobile.

Non ne sono del tutto convinto ... con ciò non voglio dire che sia sbagliato ciò che dici ma che andrebbe dimostrato.
In pratica tu dici che invece di "far girare" la lampadina di riferimento in senso orario, fai girare l'intero cerchio in senso opposto; questo vuol dire che la lampadina 2 diventa la 1, la 3 diventa la 2, ecc.
Apparentemente uguale ma in realtà potrebbe essere diverso; per esempio nel caso delle lampadine tutte accese non ha importanza che la sequenza sia 5, 6, 7, ..., invece che 1, ,2, 3, ... ma se la sequenza di partenza e di arrivo fosse diversa e meno simmetrica non è detto che si riesca a raggiungere, tipo 1 e 2 accese e 3 spenta, 4 e 5 accese e 6 spenta, ecc.
Potresti giungere a una situazione come: la "nuova" 1 accesa, la "nuova" 2 spenta, la 3 e la 4 accese, la 5 spenta, ecc.
IMHO

Cordialmente, Alex