Problema di lampadine

[Maioc92]

Sperando che non sia già comparso sul forum, volevo proporre una generalizzazione che mi sembra interessante di un problema di tipo standard. Premetto che ancora non ho la soluzione, per cui il problema è aperto a tutti i tipi di intervento.

$ n $ lampadine sono disposte lungo una circonferenza, collegate a $ n $ interruttori. Ciascun interruttore controlla una terna di lampadine consecutive (cioè quella a cui è collegato e le due che seguono in senso orario). Quando un interruttore viene attivato cambia lo stato delle 3 lampadine che controlla. Gli unici stati possibili per le lampadine sono 2, ovvero ogni lampadina può essere accesa o spenta. Nell'ipotesi che inizialmente le lampadine siano tutte spente, determinare per quali valori di $ n $ è possibile,azionando opportunamente gli interruttori, ottenere qualsiasi configurazione di lampadine accese o spente.

EDIT:scusate, mi sono appena accorto che il problema era già stato postato, ma che comunque è rimasto senza soluzione. Se i mod lo ritengono opportuno possono eliminare o chiudere questo topic, però sarebbe lo stesso interessante ripescare il topic originale e discutere li' del problema

[Maioc92]

ok, visto che nessuno ha risposto immagino che questo topic rimanga aperto.
Allora inizio a autorispondermi (e magari cosi invoglio qualcuno a provare a completare la soluzione).
Sono riuscito a dimostrare che se n non è multiplo di 3 la tesi è verificata.
Lemma:
E' chiaro che se si riesce a trovare una sequenza di mosse (che definisco sequenza base) che permetta di cambiare lo stato di una sola lampadina e lasciare invariate le altre, allora si può ottenere qualsiasi configurazione applicando la sequenza base ad una lampadina per volta e portarla allo stato desiderato.

Distinguo ora 2 casi:
CASO 1:$ n\equiv 1\pmod 3 $
In questo caso la sequenza base esiste, ed è la seguente:
-cambio lo stato di tutte le lampadine tranne 1(questo è possibile perchè n=3k+1).Chiamiamo questa lampadina A
-fisso una delle due lampadine adiacenti ad A (che chiamo B) e come nella mossa precedente cambio lo stato di tutte le altre lampadine
-Ora ho due lampadine (A e B) con stato cambiato e tutte le altre lampadine allo stato originale
-Cambio lo stato di una di delle due terne di lampadine consecutive contenenti A e B
-Ho ottenuto cosi una lampadina con stato opposto a quello iniziale e tutte le altre lampadine allo stato iniziale.

Ho cosi terminato in virtù del lemma iniziale

CASO 2:$ n\equiv 2\pmod 3 $
Di nuovo la sequenza base esiste:
-Cambio lo stato di tutte le lampadine tranne 2 consecutive (che chiamo A e B)
-Cambio lo stato di una delle due terne che contengono A e B:in questo modo ottengo una lampadina allo stato originale e tutte le altre cambiate di stato (se n=3k+2, allora il numero di queste lampadine sarà 3k+1)
-Cambio lo stato di tutte le lampadine che non sono allo stato originale. Poichè ve ne sono 3k+1, alla fine rimarrà 1 lampadina cambiata di stato e tutte le altre saranno state riportate allo stato iniziale.

Sempre per il lemma iniziale, anche questo caso è concluso.

Ora però viene il difficile del problema, che è determinare cosa succede se n è multiplo di 3. Io ho congetturato che in questo caso sia impossibile ottenere qualsiasi configurazione, però non sono riuscito a dimostrarlo per cui potrebbe anche essere falso.
Quindi fatevi pure avanti se avete idee di qualche tipo!!!

[dario2994]

Ci ho pensato tutto ieri, tutto oggi... e alla fine tornando da scuola mi è venuto in mente xD
Scelgo una lampadina che sarà $ a_1 $ e da lì le numero in senso orario tutte fino all'ultima che sarà $ a_{3k} $. Se la lampadina i-esima è accesa allora $ a_i=1 $ altrimenti 0.
Noto che per ogni configurazione ottenibile vale:
$ \displaystyle \sum_{i=1}^k a_{3i}\equiv \sum_{i=1}^k a_{3i+1}\equiv \sum_{i=1}^k a_{3i+2}\pmod{2} $
Si dimostra per induzione.
Da qui è ovvio che non si potrà mai arrivare alla configurazione con una sola lampadina accesa.
Come al solito spero di non aver scritto boiate.

p.s. questo problema era bellissimo

EDIT: Rilancio:
Su una circonferenza sono disposte n lampadine a ognuna di queste è collegato un interruttore che modifica lo stato della lampadina corrispondente e delle successive m-1 (in senso orario).
Per quali m,n si possono ottenenere tutte le configurazioni?

[fph]

EDIT: Rilancio:
Su una circonferenza sono disposte n lampadine a ognuna di queste è collegato un interruttore che modifica lo stato della lampadina corrispondente e delle successive m-1 (in senso orario).
Per quali m,n si possono ottenenere tutte le configurazioni?

Era nel preIMO di quest'anno, diviso in tre step più dannosi che utili.
Anzi, la domanda era "quante sono le configurazioni ottenibili".
Ne ho parlato anche nella mia lezione "advanced" di algebra lineare all'ultimo stage senior, non so se si trovano già i video online.
Detto questo... beh, fatelo, è un bel problema di combinatoria (e anche l'algebra lineare è più dannosa che utile).

[dario2994]

Fph quand'è che considero due combinazioni diverse? Se esiste una rotazione che manda l'una nell'altra sono considerate uguali?

[fph]

Fph quand'è che considero due combinazioni diverse? Se esiste una rotazione che manda l'una nell'altra sono considerate uguali?

No, sono considerate diverse. Immagina che le lampadine siano numerate da 1 a n.

[Maioc92]

$ \displaystyle \sum_{i=1}^k a_{3i}\equiv \sum_{i=1}^k a_{3i+1}\equiv \sum_{i=1}^k a_{3i+2}\pmod{2} $
Si dimostra per induzione.
Da qui è ovvio che non si potrà mai arrivare alla configurazione con una sola lampadina accesa.
Come al solito spero di non aver scritto boiate.

non mi sembra che tu abbia scritto boiate
Complimenti per la soluzione!!!Precisa, rapida e dritta al punto
Era proprio un invariante di questo tipo che stavo cercando.

Ora provo ad addentrarmi nella super generalizzazione del problema, anche se il testo fa un po' paura

[dario2994]

Bene :)
Guarda che alla fin fine è abbastanza banale la generalizzazione.
Ah beh Fph allora è fattibile il problema del preimo(le ultime parole famose xD).

p.s. Fph non è che potresti mostrare (sempre che sia elementare e nulla di assurdo) la dimostrazione che sfrutta l'algebra lineare... così magari inizio a conoscere qualche nuovo metodo :)

EDIT: Ok dovrei essere riuscito a dimostrare che il numero di combinazioni possibili è:
$ \displaystyle 2^{n-(m,n)+1} $
Non so se è giusta comunque la mia dimostrazione è una delle più belle che abbia mai fatto. Comunque il problema, senza avere degli step (come è capitato casualmente in questo post, cioè prima con 3 poi con m e poi contare le combinazioni), penso sia davvero tostissimo :| Non ci sarei mai arrivato...

[fph]

p.s. Fph non è che potresti mostrare (sempre che sia elementare e nulla di assurdo) la dimostrazione che sfrutta l'algebra lineare... così magari inizio a conoscere qualche nuovo metodo

Uhm, no, è decisamente non elementare e abbastanza assurda. Appena vanno online i video del senior puoi provare a guardartela da lì.

EDIT: Ok dovrei essere riuscito a dimostrare che il numero di combinazioni possibili è:
$ \displaystyle 2^{n-(m,n)+1} $

Quasi. Se non mi sbaglio quel +1 c'è solo quando una certa quantità è pari...

[dario2994]

Uhm ho trovato la pecca nella mia dimostrazione mi rimane da dimostrare un lemmino (che non sono certo sia vero):
Definito b=MCD(m,n) e c=n/b allora
$ $\upsilon_2(m)>\upsilon_2(n)\Rightarrow 2|\sum_{i=1}^ca_{bi+1} $
Che sarebbe un po come dire che non riesco ad accenderle tutte se m ha più fattori 2 di n... Dimostrato questo ho finito (ed anche rimediato a quell'1 di troppo a volte).

Questo problema si rivela sempre più bello :)

EDIT: Appena ho inviato ho dimostrato mentalmente (e questo significa che si sono ottime possibilità di errore) il lemma xD Bueno ho concluso. Quel +1 c'è solo se m ha più fattori 2 di n... spero di non aver sparato cazzate :roll:

[dario2994]

Provo a mettere la dimostrazione (sono stato conciso all'inizio ma forse troppo prolisso nel lemma 6).
Al solito spero di non aver scritto boiate (quasi quasi me la metto in firma questa frase xD)

Chiamo $ $f(m,n) $ il numero di configurazioni se ci sono n lampadine e ogni interruttore cambia lo stato di m lampadine.
Scelgo una lampadina e la chiamo $ $a_1 $ e da quella le numero tutte in senso orario fino ad $ $a_n $. Se la lampadina i-esima è accesa allora $ $a_i=1 $ altrimenti $ $a_i=0 $. Inotre per ogni k intero vale $ $ a_{kn+i}=a_i $
Definisco l'azione $ $I(i) $ premere l'interruttore corrispondente ad $ $a_i $
Definisco l'azione $ $D(i) $ l'unione di I(i) e I(i+1).
Definisco l'azione $ $G(i) $ l'unione di $ $I(1),I(1+m),I(1+2m) $ fino a $ $I(1+im) $.
Chiamo $ $b=MCD(m,n) $.
Chiamo $ $c=\frac{n}{b} $
Chiamo $ $d=\frac{m}{b} $

Lemma 1) $ $ \forall (x,y)\in\mathbb{Z}^2\ \ \sum_{i=1}^ca_{ib+x}\equiv \sum_{i=1}^ca_{ib+y}\pmod{2} $
Si dimostra per induzione.

Lemma 2) $ $2|d\Rightarrow\ 2|\sum_{i=1}^ca_{ib+1} $
Anche questo per induzione.

Lemma 3) Riesco ad arrivare ad una configurazione con b lampadine consecutive in uno stato differente da tutte le altre.
Noto che G(i) rende differenti dalle altre le prime $ $ im \pmod{n} $ lampadine. Per il teorema di Bezout $ $ im\pmod{n} $ per qualche i assume il valore di b che è proprio ciò che volevo dimostrare.

Lemma 4) $ $ f(m,n)\le 2^{n-b+1} $
Per dimostrarlo divido le lampadine in base alle classi di equivalenza degli indici modulo b. Le lampadine congrue a 1 possono assumere qualsiasi configurazione quindi $ $2^c $ configurazioni. Quelle congrue a $ $2,3,4,...,n-1,n $ hanno la parità fissata per il lemma 1 perciò tutte le lampadine sono libere tranne l'ultima di ogni classe di equivalenza che deve rispettare la parità, perciò ogni classe ha $ $2^{c-1} $ configurazioni possibili. Quindi moltiplicando tutte le configurazioni parziali si ottiene:
$ $2^c\cdot 2^{c-1}\cdot 2^{c-1}\dots 2^{c-1}=2^c\cdot (2^{c-1})^{b-1}=2(2^{c-1})^b=2(2^{cb-b})=2^{n-b+1} $
Che è proprio il lemma

Lemma 5) $ $ 2|d \Rightarrow f(m,n)\le 2^{n-b} $
Per dimostrarlo sfrutto gli stessi identici metodi usati per il lemma 4 notando però che anche la prima classe di equivalenza ha parità fissata per il lemma 2.

Lemma 6) $ $ 2\not |d\Rightarrow f(m,n)= 2^{n-b+1} $
Noto che $ $G(mcm(m,n)) $ accende tutte le lampadine. Per dimostrare che non lascia tutto invariato devo dimostrare che $ $\frac{mcm(m,n)}{n} $ è dispari e ciò vuol dire che fa un numero dispari di giri (e perciò accende le lampadine). Per la condizione $ $2|d $ allora n ha più fattori 2 di m, in particolare ne ha lo stesso numero di $ $mcm(m,n) $ da cui la loro divisione da un numero senza fattori primi, quindi dispari. Unendo questo fatto al lemma 3 posso dire che riesco a cambiare lo stato di b lampadine consecutive.
Perciò sotto queste condizioni $ $f(m,n)=f(b,n) $.
Ora lavoro considerando $ $f(b,n) $ tanto è equivalente.
Dimostro che tutte le configurazioni evidenziate nel lemma 4 sono creabili. Scelgo una configurazione e la realizzo.
Divido sempre in classi di congruenza modulo b.
La classe modulo 1 la posso scegliere completamente: se $ $a_i=1 $ allora svolgo $ $I(i) $ che di quella classe di congruenza modifica ovviamente solo $ $a_i $.
Per le altre classi di congruenza ho la parità fissata, devo riuscire a modificarle senza cambiare nessun altra lampadina.
Scelgo una classe di congruenza (funziona per tutte).
Parto dalla prima $ $a_i $ appartenente a quella classe diversa da come deve essere. Svolgo $ $D(i) $ ora mi ritrovo $ $a_i $ giusta e $ $a_{i+b} $ cambiata. Ora ripeto il procedimento finchè non arrivo all'ultima lampadina di quella classe di congruenza che dovrà restare com'è per la parità.
In questo modo iterando il procedimento su tutte le classi di resto creo qualsiasi configurazione possibile.

Lemma 7) $ $2|d\Rightarrow f(m,n)=2^{n-b} $
Sfrutto argomentazioni molto simili a quella usate per il lemma 6, saltando però la prima parte e notando però che m è come se fosse n-b (al posto di b come nel lemma 6) e che perciò il procedimento sfruttato nella seconda parte del lemma è utilizzabile anche qui e va applicato anche alla classe di resto 1. Perciò si riescono a realizzare tutte le configurazione del lemma 5.