Newsgroup: it.hobby.enigmi
Titolo: Diabolik

Sul pannello anteriore della nuova cassaforte ci sono N pulsanti luminosi, 
numerati da 1 ad N.
Ogni volta che un pulsante viene premuto, si illumina.
Quando la giusta combinazione dei pulsanti spenti-accesi e' ottenuta (non 
importa in quale ordine siano stati premuti), lo sportello immediatamente 
si apre.
Su un lato della cassaforte c'e' il pulsante di azzeramento che spegne 
tutte le lampadine.
Diabolik, che ha a disposizione poco tempo per compiere le sue imprese, ci 
chiede qual e' il minor numero di pressioni occorrenti, compreso il 
pulsante di reset, per garantire l'apertura della cassaforte, sapendo che 
all'inizio le luci sono tutte spente.

 N!-1-(N-1)
Non può andar bene. Prendi N=2, la cui soluzione è 4 (basta scrivere i 
tentativi: 1,12,reset,2)
invece:
N!-N=2!-2=0
:(
Per tentativi ho trovato che per N=4 la soluzione è 33 (se sono stato 
abbastanza diaboliko...)
I possibili sottoinsiemi di N elementi sono 2^N, quindi la soluzione 
minima deve essere almeno 2^N-1, assumendo che con tutti i tasti spenti 
(insieme vuoto) la cassaforte non sia aperta (anche se Diabolik potrebbe 
essere particolarmente fortunato...)
Dade :)

 writes:

Il numero di combinazioni possibili e` 2^N:
  1  con tutto spento
  N  con 1 luce accesa
  ...
  N!/(k!(N-k)!)  con k luci accese
  ...
  N  con N-1 luci accese
  1  con tutte le luci accese
E` necessario fare 1 sequenza di N pulsanti "normali" (per avere la
combinazione tuttoacceso), N sequenze di almeno N-1 pulsanti, ...
Ovviamente per la sequanza da N non ri riparte da 0, ma si "ricicla"
una sequanza da N-1.
Le varie sequenze sono separate dal pulsante di reset.
Esempio: N = 4:
  1 comb. tutto spento
  4 comb. da 1
  6 comb. da 2
  4 comb. da 3
  1 comb. da 4
E` necessario fare aleno 6 sequenze per ottenere le 6 combinazioni da
2, 4 sequenze saranno prolungate fino a 3, e una di queste sara`
prolungata a 4. 
Le combinazioni da 1 si ottengono gratis come sottoprodotto delle
sequenze piu` lunghe.
Il numero totale di pressioni e`:
  6 * 2   per le 6 sequenze da 2
  4       per i prolungamenti da 3 
  1       per il prolungamento a 4
  6 - 1   pulsanti di reset per separare le sequenze
Totale: 12 + 4 + 1 + 5 = 22
Una possibile soluzione e`: (1-4: pulsanti normali, r: reset)
  1234 r 134 r 142 r 324 r 24 r 43
Caso generale con N pari
------------------------
Il massimo delle combinazioni si ha per N/2 luci accese ed e` pari a
  N! / ((N/2)!)^2
Per ottenerle servono N/2 *  N! / ((N/2)!)^2 pressioni.
Le combinazioni da 1, ..., N/2-1 luci si ottengono gratis.
Per le combinazioni da k luci (con k = N/2+1, ..., N) servono altre
N!/(k!(N-k)!) pressioni per prolungare le sequenze.
Per separare le sequenze servono  N! / ((N/2)!)^2 - 1  reset.
Totale: 
  N/2 * N!/((N/2)!)^2  +                seq. N/2
  sum_{k=N/2+1..N}  N!/(k!(N-k)!) +      prolungamenti
  N! / ((N/2)!)^2 - 1                   reset
Raccogliendo un po':
  N/2 * N!/((N/2)!)^2  +  sum_{k=1..N/2}  N!/(k!(N-k)!)
probabilmete si puo` semplificare ancora e cacciare via qualche
fattoriale, ma per ora non ho trovato niente di meglio.
Caso con N dispari
------------------
E abbastanza simile.
Il massimo si ha sia per (N-1)/2 che per (N+1)/2, e vale 
  N! / ( ((N-1)/2)! ((N+1)/2)! )
Le combinazioni da (N-1)/2 direi che si ottengono gratis insieme a
quelle da (N+1)/2, anche se non l'ho dimostrato.
I prolungamenti da (N+1)/2+1 a N sono gli stessi del caso pari.
I reset sono sempre uno in meno delle sequenze.
Totale:
 (N+1)/2 * N!/(((N-1)/2)!((N+1)/2)!) + sum_{k=1..(N-1)/2} N!/(k!(N-k)!)
Come prevedibile, l'andamento ha un aspetto esponenziale, e si
mantiene un po' sopra a 2^N.  Anche se la formula e` piu` lunga, i
risultati dei dispari sono migliori.
   N    pressioni
   0            0
   1            1
   2            4
   3            9
   4           22
   5           45
   6          101
   7          203
   8          442
   9          885
  10         1897
  11         3795
  12         8053
  13        16107
  14        33931
  15        67863
  16       142162
  17       284325
  18       592961
  19      1185923
  20      2464225
  21      4928451
  22     10209619
  23     20419239
  24     42190557
  25     84381115
  26    173962531
  27    347925063
  28    715908427
  29   1431816855
  30   2941192471
  31   
5882384943
  32  
12065310082
  33  24130620165
  34  49428043441
  35  98856086883
        Mauro

   1234 r 134 r 142 r 324 r 24 r 43
Mi dispiace rompere le uova nel paniere, specie quando non ho niente di
propositivo, ma...
12132423123424 r 4
sono solo 16 pressioni. Non ci sono mai due combinazioni ripetute, e c'è un
solo reset.
1234  Hex
--------
1000 - 8
1100 - C
0100 - 4
0110 - 6
0010 - 2
0011 - 3
0111 - 7
0101 - 5
1101 - D
1001 - 9
1011 - B
1010 - A
1110 - E
1111 - F
0000 - 0
0001 - 1
--
Ciao, Silv:o)

 0001 - 1
Mi dispiace rompere le uova nel paniere di chi le rompe nel paniere di 
qualcun altro, ma Dario non ha detto che spingendo un pulsante 2 volte 
questo ritorna allo stato iniziale (spento -> acceso -> spento).
Altrimenti il tasto reset sarebbe abbastanza superfluo...
Dade :)

 Altrimenti il tasto reset sarebbe abbastanza superfluo...
Non ne sono sicuro. Se non si riuscisse a trovare una sequenza di
configurazioni con un solo pulsante di differenza tra un elemento ed il
successivo, piuttosto che tornare indietro potrebbe tornar comodo resettare
e ripartire.
Ma il presupposto era sbagliato, quindi batto in ritirata e appena posso
vedo di lavorare sull'analisi di Mauro.
--
ciao, Silv:o(

 solo reset.
Hai usato una cassaforte diversa.
Nella mia i pulsanti normali possono solo accendere le luci, premendo
il pulsante di una luce gia` accesa non succede niente.  L'unico modo
per spegnere le luci e` il pulsante di reset.
Con la cassaforte "moderna", quella con i pulsanti che possono sia
accendere che spegnere le luci, e` sempre possibile aprirla in 2^N-1
pressioni (sfruttando lo 0 iniziale, altrimenti 2^N), e senza usare il
pulsante di reset.
Il modo piu` semplice e`:
1 luce   1
2 luci   1 2 1
3 luci   121 3 121
4 luci   1213121 4 1213121
5 luci   121312141213121 5 121312141213121
ecc.
In pratica con N pulsanti si preme la combinazione per N-1, poi si
preme l'N-esimo pulsante, poi ri ripete la combinazione di N-1.
        Mauro

 ha scritto nel messaggio
news:3DBC360F...@uriland.it...

s
p
o
i
l
e
r
Esattamente 2^N .
Le disposizioni (con ripetizione) degli N pulsanti di classe 2
(acceso/spento) rappresentano un codice binario.
Con il codice di Gray è possibile scorrere tutti i numeri binari da 0 a 2^N
semplicemente cambiando un solo bit (nel ns. caso un solo pulsante alla
volta). Se si parte dalla combinazione "tutti spenti" è evidente che per
scorrere tutte le 2^N possibilità attivando un pulsante alla volta si
premeranno in tutto 2^N pulsanti.
Esempio di codice di Gray con 3 pulsanti:
000
001
011
010
110
111
101
100
si veda ad esempio 
http://www.nist.gov/dads/HTML/graycode.html
saluti
N! Xau

 premeranno in tutto 2^N pulsanti.
Leggiti i post precedenti: scoprirai di aver risolto il problema per un 
altro tipo di cassaforte :(
Dade :)

 potrebbe tornar comodo resettare e ripartire.
Ne puoi star certo. Si chiama codice Gray. Per qualunque N
puoi passare da tutte le combinazioni possibili e ritornare alla
combinazione di partenza cambiando un bit solo alla volta,
in un totale di 2^N passaggi.
Peccato che il problema non era questo, se no avevo la
risposta pronta.  :o(
Ciao!!!  ((^__^))'
Livio
PS.
Meno noto e' il codice Giannini che permette di fare la stessa
cosa sul codice BCD (binar coded decimal). Nessuno, neppure
google sembra ricordarsi di questo connazionale il cui codice
ebbe solo qualche anno di fortuna nella costruzione di trasduttori
di posizione, prima che l'elettronica rendesse facile la conversione
tra codice binario puro e codice decimale.
Ovviamente sono OT, ma se qualcuno mi confermasse 'sta
notizia che ho recitato a memoria, gliene sarei grato.