Newsgroup: it.hobby.enigmi
Titolo: Le lampadine di Pazqo - soluzione

richiediamo che sia la minima).
Naturalmente Pazqo chiedeva di determinare per ogni n la sequenza
minima necessaria e la sua lunghezza.
Il quesito posto da Pazquo aveva generato un breve thread nel quale
erano state date le soluzioni per i casi n = 2 e n = 3 (il caso n = 1
e' ovviamente banale), ma non era stata trovata alcuna soluzione
generale.
Il problema mi era sembrato subito interessante, ma il quel periodo i
miei impegni di lavoro erano pressanti e dopo una prima occhiata e
qualche riflessione con tentativi di forza bruta ho messo tutto da
parte.
Ora sono in pensione :-)))))))) e riordinando i miei archivi ho
ritrovato il problema.
Nel seguito del messaggio fornisco una possibile soluzione pertanto
chi vuole provare a risolverlo da solo e' opportuno che si fermi qui.
.
.
.
.
.
.
.
. 
.
.
.
.
.
.
.
.
E' molto facile generare una sequenza tale che, scelti due pulsanti su
un insieme di 2n, garantisca *almeno* l'accensione delle due lampadine
collegate ai due pulsanti. Ad esempio se i due pulsanti si chiamano x
e y e tutti gli altri ABCDEF.... la sequenza da realizzare e':
xyAxByCxDyExFy.x.y.x.y........ 
Si scrivono prima i due pulsanti da eliminare (xy) poi tutti gli altri
pulsanti seguiti alternativamente da x e y.
La sequenza risulta lunga 2*(2*n-1) e quando viene eseguita garantisce
che sicuramente *almeno* le lampadine collegate ai pulsanti x e y
siano accese.
In questo modo il problema di 2n lampadine e' ridotto a 2n-2
lampadine; a questo punto e' sufficiente applicare di nuovo la regola
con altri due pulsanti per ridurlo a 2n-4 e cosi via fino all'ultima
banale sequenza di due soli pulsanti.
La sequenza complessiva e' così composta da n sottosequenze di
lunghezza via via decrescente e la lunghezza complessiva risulta
essere pari a 2*n^2.
Ad esempio per n=3 si hanno le tre sottosequenze:
1231425162         accende le lampadine connesse a 1 e 2
345364             accende le lampadine connesse a 3 e 4 
56                 accende le lampadine connesse a 5 e 6
In questo modo si costruisce sempre una soluzione, ma naturalmente non
é affatto detto che sia la sequenza minima, infatti nell'esempio dato
é immediatamente evidente che l'ultima sottosequenza '56' é inutile;
meno evidente é invece che anche il '3' all'inizio della seconda
sottoquenza e il '64' alla fine della seconda sottosequenza sono
inutili. Eliminando questi 5 pulsanti la sequenza risultante é simile
a quella che era stata già determinata a suo tempo.
In generale da una sequenza costruita per il caso 2n, quanti pulsanti
possono essere eliminati?
Non via annoio come sono arrivato alla mia conclusione (ragionamenti e
forza bruta), ma alla fine il tutto si riassume nelle seguenti regole
elencate in ordine di importanza:
1- tutta la sequenza deve essere costruita in modo ordinato: si fissa
un ordine dei pulsanti, quindi si elimina la prima coppia indicando
tutti i tasti nell'ordine fissato, poi la seconda coppia con tutti i
pulsanti nell'ordine fissato, ecc...
2- la prima sottosequenza non deve mai essere toccata;
3- da tutte le altre sottosequenze si toglie il primo e l'ultimo
tasto;
4- nella penultima sottosequenza si toglie anche il penultimo tasto.
esempio per n = 4:
12314251627182         accende le lampadine connesse a 1 e 2
3453647384             accende le lampadine connesse a 3 e 4 
567586                 accende le lampadine connesse a 5 e 6
78                     accende le lampadine connesse a 7 e 8
applicando le regole 2-4 diviene:
12314251627182         accende le lampadine connesse a 1 e 2
.45364738.             accende le lampadine connesse a 3 e 4 
.675..                 accende le lampadine connesse a 5 e 6
..                     accende le lampadine connesse a 7 e 8
per un totale di 25 pulsanti premuti. 
In un insieme di 2n lampadine le sottosequenze sono in numero di n
pertanto, se n é maggiore di 2 (esiste una penultima sottosequenza
diversa dalla prima), i pulsanti che si possono eliminare sono
2*(n-1)+1 portando la lunghezza totale della sequenza a
L = 2*n^2 - 2*(n-1)+1 = n^2 + (n-1)^2.
Ho verificato questa soluzione fino a n = 10 (20 lampadine) con esito
positivo, poi mi sono fermato per eccessivi tempi di calcolo (per n =
10 il mio PC ha impiegato quasi 35 minuti per provare le circa 654
milioni di possibili configurazioni di lampadine); ho anche verificato
fino a n = 5 che non esistessero soluzioni con un numero di pressioni
di pulsanti inferiori a quanto indicato (per n = 6 ho dovuto fermare
il programma dopo alcuni giorni senza che avesse trovato possibili
soluzioni, ma la scansione non é stata completata).
Infine voglio precisare che possono esistere anche sequenze costruite
in modo diverso, ma, almeno per i casi che ho analizzato, nessuna é di
lunghezza inferiore a quanto indicato. 
Qualcuno vuole fornire un controesempio? 
-- 
Damiano

 (per n = 6 ho dovuto fermare il programma dopo alcuni giorni
meno sono e più tempo impiega? :) e con n = 2 ? ^___^


Forse non ho spiegato bene, sono due prove diverse:
Prova 1 - per un certo n genero la sequenza secondo le regole
enunciate (ad esempio per n = 10 la sequenza é composta da
10^2+9^2=181 pressioni di tasti) poi verifico che questa sequenza
accende tutte le lampadine per qualsiasi combinazione di colore delle
lampadine (con 2*10 lampadine le possibili combinazioni sono
(2*10-1)!! = 654.729.075). Per fare questa verifica impiego circa 35
minuti. per verificare in caso successivo credo sarebbero necessari
dei giorni.
Prova 2 - verifico che per un certo n non esista una soluzione di
lunghezza inferiore a quella che scaturisce dalle regole enunciate;
per fare questa verifica genero tutte le possibili sequenze con
lunghezza inferiore di uno e controllo che per ognuna di queste esiste
almeno una combinazione di lampadine che non viene soddisfatta. Ad
esempio per n=6 la lunghezza minima sarebbe di 6^2+5^2=61, quindi io
verifico che *nessuna* sequenza di 60 pressioni accenda tutte le
lampadine in tutte le configurazioni; per questo caso ho fermato
l'elaborazione dopo un paio di giorni.
-- 
Damiano