Newsgroup: it.hobby.enigmi
Titolo: Le lampadine

No, no, no.
Non è la solita domanda delle FAQ.
Stavolta niente peregrinazioni tra una stanza e l'altra per vedere quali 
lampadine sono rimaste accese.
La situazione è la seguente:
In una stanza ci sono 2n lampadine, di n colori diversi (accoppiate a 
due a due).
In un'altra stanza ci sono 2n pulsanti, numerati da 1 a 2n.
Ogni pulsante accende una sola lampadina.
C'è una campanella che suona quando tutte le lampadine sono accese.
A ogni "turno" possiamo premere solo un pulsante.
Al primo turno non accade nulla, si accende la lampadina selezionata e 
basta.
Ai turni successivi si hanno le seguenti situazioni:
	1) la lampadina appena accesa è dello stesso colore di quella accesa al 
turno precedente. in questo caso le due lampadine rimangono accese 
entrambe e si ricomincia come se ci fosse una coppia di lampadine in meno.
	2) la lampadina accesa è diversa da quella accesa al turno precedente. 
in questo caso si spegne la lampadina precedente e rimane accesa solo 
quella nuova.
	3) la lampadina che si tenta di accendere era già accesa (era stata 
accesa la coppia di lampadine): non accade nulla e si prosegue come se 
nulla fosse.
quanti turni servono per sentire il "ding!" con assoluta certezza?
vediamo un esempio, per chiarire.
mettiamo che ci siano 5 coppie A,a,B,b,C,c,D,d,E,e
mettiamo che siano messe in corrispondenza dei seguenti pulsanti:
0 1 2 3 4 5 6 7 8 9
A,E,b,d,C,e,D,a,B,c
premendo 0 si accende A
premendo 1 si accende E e si spegne A
premendo 5 si accende e e rimangono accese E,e
premendo 6 si accende D
premendo 5 non accade nulla
premendo 2 si accende b e si spegne D
premendo 8 si accende B e rimangono accese B,b
etc
pazqo
ps: per n = 1 ho una soluzione con 7 turni. non penso si possa fare di 
meglio. però, eventualmente, si può tentare di ottimizzare la sequenza 
in modo da abbassare il numero medio di tentativi.

 in modo da abbassare il numero medio di tentativi.
Scusa, Paz, devo essere particolarmente tonta, ma non ho capito questo 
esempio. Ma 'n' non è il numero di coppie? perchè 7 turni?
:(
  manfredo


hai ragione. intendevo n = 2.
curioso: pensavo a 2 coppie. quindi ho diviso 2 per 2... :-P
con n = 1 basta premere 2 tasti.
ho una congettura per stimare dall'alto il numero di turni necessari nel 
caso generale. ma non ne son certo e prima di darvela vorrei fare degli 
altri conti :-)
pazqo
ps: tra l'altro, cara manfredo, questo potrebbe benissimo essere un 
enigma da avventura grafica, no? :-)

con n = 1 basta premere 2 tasti.
Non si capisce lo stesso.. e perche', con n=2 chi mi
impedisce di accenderle con 4 tentativi?  8-]
Cos'e`, Gastone Paperone e` interdetto?
-- 
Ciao, rez	||  -- GNU/Linux 2.4.25 su Slackware 9.1  ||

 Cos'e`, Gastone Paperone e` interdetto?
ma se la sequenza è ABAB non hai acceso nulla, con 4 turni.
devi trovare una sequenza che vada bene in qualsiasi caso e che 
eventualmente termina prima. ma comunque deve coprire tutti i casi 
possibili nel minor numero di tentativi...
rileggiti il tread delle tre chiavi. ecco, voglio evitare una situazione 
simile.
il discorso che fai tu va bene se andiamo a considerare il caso medio. 
allora pesiamo ogni numero di turni con la probabilità che ha di capitare...
pazqo

allora pesiamo ogni numero di turni con la probabilità che ha di capitare...
In quel thread si dicono cose strane.. ma tu sei
matematico e non ti e` concesso far casino:-))
Tanto per chiarire cos'ho capito:
TASTO	LUCI	BELL
a	a
A	aA
b	aAb
B	aAbB	Ding!
dunque le accendo tutte, il che e` - come ho gia` detto -
ovviamente impensabile come quiz. Quindi?
Dici: "Numero minimo per aver certezza", be' non c'e`
perche' AAAAAAAAA.. non accende che A.
CHI sceglie la sequenza? se scelgo io le ho gia`
accese in 4 tempi qui su, se sceglie il caso devi dare
le regole.. ma "regole" non come hai scritto piu` su:)
Cos'e` che non ho capito?
[..ma IMHO stai tirando qualche colpo;-)]


>
Forse non ho capito, ma con n=2 (cioè 4 pulsanti) i tentativi per avere la
certezza di accendere tutte e 4 le lampadine dovrebbero essere 6, non 7.
Premo 1, e poi 2.
Se le 2 lampadine si accendono, ovviamente basterà poi premere 3 e 4 (t=4)
Se invece si spegne 1, provo a schiacciare 3. Se si accendono 2 e 3,
basterà poi premere 1 e 4 (t=5)
Se si spegne 2, vuol dire che 3 è abbinata a 1, che schiaccio e per forza
si accendono 1 e 3. Quindi tocca a 4 e 2 (t=6)
Nino

 B aAbB Ding!
Mi permetto di intervenire a nome di Pazqo per fornire alcuni chiarimenti 
(Pazqo mi ha proposto il problema in anteprima ieri sera...).
Allora: le lampadine stanno in un'altra stanza rispetto alla stanza dei 
pulsanti e quindi NON si vedono. Io quindi non so quali e quante sono accese 
se non quando riesco ad accenderle tutte perché a quel punto sento il suono 
della campanella e il problema è risolto.
Ogni pulsante è collegato a una ben precisa lampadina ma NON c'è alcuna 
indicazione su quale pulsante sia collegato a quale lampadina.
Per comodità si può pensare che le lampadine si chiamino A, A (quelle di un 
colore) e B, B (quelle dell'altro) e il pulsanti si chiamino 1, 2, 3, 4.
Bisogna trovare la sequenza minima di pressione dei pulsanti che garantisca 
in ogni caso di accendere tutte le lampadine sulla base delle tre regole 
esposte da Pazqo nel post originale.
Adesso spero che sia tutto chiaro... :-)
Ciao
Giorgio 

 Cos'e` che non ho capito?
diciamo meglio: cos'è che ho omesso ma che mi sembrava ovvio?
1) ho dimenticato di dire (ma pensavo fosse implicito, sennò il problema 
è banale) è che IGNORI a quale pulsante sia collegata quale lampadina... 
per il resto mi pare che la definizione della procedura sia data bene, 
in modo induttivo...
2) ho dimenticato di dire che voglio una soluzione minima.
sarò anche matematico, ma quando si propongono questi giochi in un 
newsgroup di veterani certe cose si possono benissimo sottointendere.:-)
pazqo


un paio di chiarimenti:
1) le due stanze sono isolate e non posso accedere alla stanza delle 
lampadine
2) non si conosce la corrispondenza pulsante-lampadina
3) il ding serve solo per studiare il caso medio. in realtà potrebbe 
benissimo non esserci il ding, o essere rotto. la sequenza ti deve dare 
la certezza che COMUNQUE tutte le lampadine sono accese (e ovviamente 
richiediamo che sia la minima).
spero di aver chiarito i punti oscuri
ciao! Stefano

 [cut]
Sarò duro... ma insisto.
Con 4 lampade (che chiamo 1-2-3-4) di due colori uguali a due a due si hanno
queste possibilità (o viceversa):
              1° colore               2° colore
              ---------               ---------
                1 - 2                   3 - 4            ( A )
                1 - 3                   2 - 4            ( B )
                1 - 4                   2 - 3            ( C )
Premo la sequenza:  1 - 2 - 3 - 1 - 4 - 2       (6 tentativi)
Caso ( A ): Premendo le prime 2 volte, rimangono accesi 1 e 2.
            Al terzo tentativo, si accende 3, che rimane acceso dopo il
            quarto tentativo, perchè 1 è già acceso. Al quinto
            tentativo, suona la campana
Caso ( B ): Dopo il quarto tentativo restano accesi 1 e 3 e dopo il
            sesto anche 2 e 4  e suona la campana
Caso ( C ): Dopo il terzo tentativo restano accesi 2 e 3 e dopo il
            quinto suona la campana.
Dove sta l'errore?
Nino


funziona! e, anzi, sfrutti molto meglio della mia il 3° caso!
la mia soluzione (e anche quella di Giorgio) era 1234213
la tua soluzione è perfetta:-)
pazqo


Mi associo! Del resto si sa, quando c'č di mezzo Nino i record non resistono 
molto! :-)
Ciao
Giorgio 

newsgroup di veterani certe cose si possono benissimo sottointendere.:-)
Sottoscrivo, nonostante sia a mio danno:-(((
TNX neh:-) 


 ci provo un po':-))
beh, nino ha trovato una ottima soluzione per n = 2. rimangono aperti 
tutti gli altri casi :-)
buon lavoro!

buon lavoro!
Ho trovato brute force questa: 1234524635614, tredici
tempi.. ma facilmente magari e` migliorabile (e` per n=3).
Tra l'altro non ho dimostrato che sia valida, nel senso
che e` da vedere se le figure per n=3 sono 30 in tutto
soltanto.


 soltanto.
dovrebbero essere 15: 6!/3!2!2!2!
in generale, dovrebbe essere (2n)!/(n!2^n). (2n)! è il numero totale di 
permutazioni. in queste posso permutare i colori (n!) e le due caselle 
colorate (2!*2!*... n - volte).
praticamente risulta essere (2n-1)!! =(2n-1)*(2n-3)*(2n-5)*...*5*3
ora provo a vedere per quella soluzione. hai fatto le verifiche per 
tutte e "30" le disposizioni?
pazqo


Torno a casa solo adesso e trovo la tua soluzione...
mmmhh  a occhio mi sembra che l'1 non sia a posto
(c'è solo un laterale e un interno)
Forse manca  1-3   (1-4   5-6)
             1-4   (2-6   3-5)
Ciao, Nino
(se ho un po' di tempo proverò anch'io)

tutte e "30" le disposizioni?
Per le 30 che ora posto a Nino si` - sempre che non mi sia
distratto.


             1-4   (2-6   3-5)
Gia`, queste due figure tue: 13 24 56; 14 26 35, non
suonano (il DING).
Occorrerebbe aggiungere 3 per la prima e 26 per la
seconda e si andrebbe allora a 16 tempi.
Cmq ho visto che bisogna aggiungerne [forse molte?]
alle 30 che ho scritto io, cioe` queste:
12 34 56 
13 26 45 
14 25 36 
15 23 46 
16 24 35 
23 15 46 
24 16 35 
25 14 36 
26 13 45 
34 12 56 
35 16 24 
36 14 25 
45 13 26 
46 15 23 
56 12 34 
12 56 34 
13 45 26 
14 36 25 
15 46 23 
16 35 24 
23 46 15 
24 35 16 
25 36 14 
26 45 13 
34 56 12 
35 24 16 
36 25 14 
45 26 13 
46 23 15 
56 34 12 
Oppure bisogna anche sostituirne alcune.
Per il momento non ci vedo chiaro..
Queste cmq dovrebbero sonare tutte, la verifica
e` molto veloce, anche se l'ho fatta a mano.


alle 30 che ho scritto io, cioe` queste:
Ora mi sembrerebbe invece cosi`:
SEQUENZA: 12342531623514 di quattordici.
FIGURE: quindici in tutto.
12 34 56
12 35 46
12 36 45
13 24 56
13 25 46
13 26 45
14 23 56
14 25 36
14 26 35
15 23 46
15 24 36
15 26 34
16 23 45
16 24 35
16 25 34
Mi sembra cioe` che non sia essenziale la posizione dei
raggruppamenti, AKA si va con le combinazioni.


 14 25 36
[cut]
Mi sembra ti stai complicando la vita.
Non č meglio lasciar perdere l'ordine? In questo modo, le
sequenze sono solo 15:
1-2  3-4  5-6
1-2  3-5  4-6
1-2  3-6  4-5
1-3  2-4  5-6
1-3  2-5  4-6
1-3  2-6  4-5
1-4  2-3  5-6
1-4  2-5  3-6
1-4  2-6  3-5
1-5  2-3  4-6
1-5  2-4  3-6
1-5  2-6  3-4
1-6  2-3  4-5
1-6  2-4  3-5
1-6  2-5  3-4
Ciao, Nino 

 15 23 46
Vedo ora che abbiamo scritto lo stesso post :-)
Fra l'altro, ero arrivato anch'io a 14 sequenze
(ma sono certo si possa fare meglio)
Ciao, Nino

(ma sono certo si possa fare meglio)
Si`.. ho trovato questa: 123.142.615.243.6 di tredici.


 Si`.. ho trovato questa: 123.142.615.243.6 di tredici.
il fatto che ci sia un solo 5 mi lascia piacevolmente stupito!
non pensavo che fosse possibile... :-)
come hai trovato quella soluzione? brute force?
pazqo

come hai trovato quella soluzione? brute force?
Si`, ma e` velocissima.. uso queste notazioni:
	  125  6   4
12 34 56  Ac   AC  ACb'
13 26 45  c'   b'  c
poi prima di scegliere, anzi _per_ scegliere, metto
cosi`:
	  125
12 34 56  Ac 6
13 26 45  c' 4
se fosse:
12 34 56  AB
metterei:
12 34 56  AB 56
oppure guarda quest'altro:
12 34 56  B 1256
ad esempio dopo l'obbligato 123 ho introdotto l'1 al
posto del 4 perche' e` l'unico che fa passare ben tre
singoli: a' al chiuso doppio A=aa'.
Invece 4,5,6 ne farebbero passsare (tra loro son
simmetriche) soltanto due.
