Quante lampadine!
Quante lampadine!
Ho due numeri $n$ e $k$ con $n\geq k$.
Ho $n$ lampadine in cerchio, inizialmente spente. L'unica mossa consentita è scegliere $k$ lampadine consecutive e cambiare il loro stato (gli stati sono due: spento e acceso). Trovare in funzione di $n$ e $k$ il numero di tutte le possibili configurazioni, fra le $2^n$ possibili, che si possono ottenere partendo da quella iniziale data, applicando una certa sequenza di mosse.
Ho $n$ lampadine in cerchio, inizialmente spente. L'unica mossa consentita è scegliere $k$ lampadine consecutive e cambiare il loro stato (gli stati sono due: spento e acceso). Trovare in funzione di $n$ e $k$ il numero di tutte le possibili configurazioni, fra le $2^n$ possibili, che si possono ottenere partendo da quella iniziale data, applicando una certa sequenza di mosse.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Quante lampadine!
Penso che la risposta sia $ 2^{ n-k+1 } $.
Immaginiamo di avere $ n $ lampadine in cerchio, tutte spente. Per la prima lampadina $ L_1 $, posso decidere se far sì che sia accesa o spenta: ciò che succede alle lampadine seguenti, per ora non mi interessa. Poi passo alla seconda $ L_2 $, e decido se accenderla o spegnerla, non curandomi di ciò che succede alle lampadine seguenti. Arrivato alla lampadina $ L_{ n-k+1 } $, la decisione che prendo influenza tutte le lampadine seguenti fino all'ultima, poichè tra la lampadina $ L_{ n-k+1 } $ e la lampadina $ L_n $, estremi compresi, vi sono $ [n-(n-k+1)+1]=[n-n+k-1+1]=k $ lampadine. Dunque non posso decidere circa lo stato delle lampadine seguenti.
Non so, aspetto risposte, non sono convintissimo della mia soluzione. Ho provato con un paio di casi semplici, e i conti tornano. Ad esempio, se $ n=k $, le possibilità sono $ 2^{ n-k+1 }=2^{ n-n+1 }=2 $, ovvero o tutte accese o tutte spente.
Immaginiamo di avere $ n $ lampadine in cerchio, tutte spente. Per la prima lampadina $ L_1 $, posso decidere se far sì che sia accesa o spenta: ciò che succede alle lampadine seguenti, per ora non mi interessa. Poi passo alla seconda $ L_2 $, e decido se accenderla o spegnerla, non curandomi di ciò che succede alle lampadine seguenti. Arrivato alla lampadina $ L_{ n-k+1 } $, la decisione che prendo influenza tutte le lampadine seguenti fino all'ultima, poichè tra la lampadina $ L_{ n-k+1 } $ e la lampadina $ L_n $, estremi compresi, vi sono $ [n-(n-k+1)+1]=[n-n+k-1+1]=k $ lampadine. Dunque non posso decidere circa lo stato delle lampadine seguenti.
Non so, aspetto risposte, non sono convintissimo della mia soluzione. Ho provato con un paio di casi semplici, e i conti tornano. Ad esempio, se $ n=k $, le possibilità sono $ 2^{ n-k+1 }=2^{ n-n+1 }=2 $, ovvero o tutte accese o tutte spente.
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Quante lampadine!
EDIT: sono pochissimo convinto della mia soluzione XD
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Quante lampadine!
Io sono invece convinto che la tua sia un'ottima idea.
This is it. This is your story. It all begins here.
Re: Quante lampadine!
Dici? Boh, a me non convince XD
Attendo soluzioni altrui...
Attendo soluzioni altrui...
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Quante lampadine!
Edit. La soluzione non è sicuramente quella descritta sopra. Ci sono alcuni casi in cui si possono ottenere tutte le combinazioni possibili... ci penso un po'.
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Quante lampadine!
Quali casi? fammi un esempio di un caso con n e k che permettono di raggiungere tutte le $2^n$ combinazioni.
This is it. This is your story. It all begins here.
Re: Quante lampadine!
E' vero, n=4 k=3 permette tutte le combinazioni..... forse ll'unico problema è che se k è pari allora il numero di lampadine accese non può essere dispari? Ho paura che sia molto più complicato di quanto sembri.
This is it. This is your story. It all begins here.
Re: Quante lampadine!
Anche io ho la stessa paura... comunque penso che $ 2^n $si possa ottenere con tutte le coppie $ (n,k) $ con $ mcd(n,k)=1 $. Sono convinto che il $ mcd $ sia un elemento fondamentale per risolvere questo problema.
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Re: Quante lampadine!
No, ad esempio n=2a+1 e k =2 puoi ottenere al massimo la metà delle configurazioni (quelle in cui le lampadine accese sono in numero pari).
This is it. This is your story. It all begins here.
Re: Quante lampadine!
C'è da pensarci, è molto piu difficile di quel che sembra.
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25