Quante lampadine!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Quante lampadine!

Messaggio da bĕlcōlŏn »

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.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

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.
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

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.
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Quante lampadine!

Messaggio da auron95 »

Io sono invece convinto che la tua sia un'ottima idea.
This is it. This is your story. It all begins here.
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

Dici? Boh, a me non convince XD

Attendo soluzioni altrui...
Se uno nasce quadrato, non può morire tondo.
Beh, in effetti la quadratura del cerchio è un problema ancora irrisolto.
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

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.
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Quante lampadine!

Messaggio da auron95 »

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.
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Quante lampadine!

Messaggio da auron95 »

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.
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

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.
Avatar utente
auron95
Messaggi: 233
Iscritto il: 08 lug 2012, 12:20

Re: Quante lampadine!

Messaggio da auron95 »

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.
Iceman93
Messaggi: 32
Iscritto il: 27 ago 2012, 14:47

Re: Quante lampadine!

Messaggio da Iceman93 »

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.
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: Quante lampadine!

Messaggio da Troleito br00tal »

Testo nascosto:
Definito $j=(n,k); r=\frac{n}{j}$, dimostriamo che le configurazioni sono $2^{n-j+1}$

Prima di tutto sicuramente il numero di configurazioni è $\le\ 2^{n-j+1}$, per questa simpatica invariante:
numeriamo le lampadine da $1$ a $j$. Le lampadine con il numero $i_1$ accese hanno la stessa parità delle lampadine accese con il numero $i_2$.

Dimostriamo ora che possiamo ottenere tutte quelle configurazioni, con questi algoritmi:
1) posso cambiare di stato $j$ lampadine consecutive: se accendo infatti $k$ lampadine "consecutivamente" prima o poi otterrò che rimarranno accese $j$ lampadine consecutive (per il fatto che l'ordine additivo di $k$ ha come minimo il gcd)
2) posso cambiare di stato 2 qualsiasi lampadine con lo stesso numero $i$ CONSECUTIVE: grazie a 1) questo segue se iteriamo il processo anche per le lampadine da $i$ a $i+j-1$ e da $i+1$ a $i+j$: avrò alla fine un cambio di $i$ e di $i+j$
3) posso cambiare di stato 2 qualsiasi lampadine con lo stesso numero $i$: reitero 2) ogni volta spostandomi di $j$
E ora ho vinto, perché se le lampadine sono pari segue subito, se invece sono dispari mi basta invertire una volta (ma proprio brutalmente e viene) $j$ lampadine consecutive e poi aggiustare.
Rispondi