Newsgroup: it.hobby.enigmi
Titolo: Riduttori

Da quando si parla di giochi a scommessa, ed in particolar modo per il
SEL, in questo ed in altri NG sono apparsi messaggi, rimasti tutti senza
risposta, riguardanti l'aspetto dei riduttori. In pratica il giocatore
chiede: Pronostico 20 numeri. Per essere sicuro, a pronostico esatto, di
totalizzare 6 punti,  dovrei giocarmi qualcosa come C(20,6) schedine.
Troppe! Se mi accontento di totalizzare 5 punti, qual e' il minor numero
di giocate che devo fare ??
Questi problemi di Block Design sembrano difficili e non credo siano
state trovate strategie generali.
Problemi simili sono diventati famosi. Ad es. il problema delle
scolarette di Kirkman ha fatto impazzire piu' di una persona.
A quanto ho capito, per generare questi riduttori per il momento non
c'e' di meglio che scrivere tutte le n-tuple possibili, sceglierne una a
caso poi cancellare tutte quelle che differiscono di un solo simbolo.
Scegliere una delle restanti... ecc. Pero' questo metodo non garantisce
il numero minimo dette n-tuple scelte.
Dopo questa premessa vi dico cosa mi e' venuto in mente per un possibile
approccio.
Cominciamo con un esempio semplicissimo. Ci sono nell'urna 6 simboli e
ne vengono estratti 3. 
Esistono cosi' C(6,3)=20 terne in tutto, quante ne devo giocare per
essere sicuro di totalizzare almeno 2 punti?
Mettiamo i nostri simboli A,B,C,D,E,F equidistanti su una circonferenza:
       A
   F       B
 
   E       C
       D
A questo punto vi occorre carta e matita per proseguire. 
Cominciamo col segnare un triangolo coi vertici ABC, ed immaginiamo il
triangolo disegnato su un cerchio di cartoncino imperniato al centro e
libero di ruotare,  le lettere invece restano fisse.
Se ruoto il cerchio nelle 6 posizioni, intercetto le 6 triple
ABC,BCD,CDE,DEF,EFA,FAB.
Questa famiglia o gruppo la etichetto con 1,1,2  che sono le lunghezze
minime dei 3 archi che dividono i 3 simboli.
(AB e BC distano 1, AC distano 2) 
Se disegno ora il triangolo ABD, e ruoto il mio cerchio intercetto
ABD,BCE,CDF,DEA,EFB,FAC. Che idantifico con 1,2,3.
Proseguendo con i 2 triangoli restanti possibili, ABE ed ACE, divido le
20 triple in 4 famiglie:
a) 1,1,2   (6 triple)
b) 1,2,3   (6 triple)
c) 1,3,2   (6 triple)
d) 2,2,2   (2 triple)
Data la simmetria 2,2,2 puo' assumere solo 2 posizioni distinte.
Ora una volta scelta una di queste famiglie come riduttore, posso
eliminare tutte quelle che hanno un numero in comune a questa, difatti
se hanno un arco in comune devono avere anche 2 vertici e percio' 2
simboli. Per totalizzare 2 punti su 3 e' sufficiente giocare le due
triple ACE, FBD del gruppo d) perche' tutti gli altri hanno un'arco
lungo 2.
Se notiamo che 1,1,4  1,2,3  1,3,2   2,2,2 sono le distinte partizioni
di 6 (considerate come anelli). Possiamo subito passare ad un caso piu'
complesso senza bisogno di diagrammi o disegni.
----------------------------------------------
Proviamo con 8 simboli, si vince con il 4 e con il 3.
In tutto ci sono C(8,4)=70 quaterne. Quante ne devo giocare per essere
sicuro di totalizzare 3 punti ?
Le partizioni di 8 sono: 
a) 1,1,1,5
b) 1,1,2,4
c) 1,1,3,3
d) 1,1,4,2
e) 1,2,1,4
f) 1,2,2,3
g) 1,2,3,2
h) 1,3,1,3
i) 1,3,2,2
l) 2,2,2,2
Tutte generano 8 quaterne tranne la h) con un asse di simmetria che ne
produce 4, e la l) 2 assi di simmetria ne produce solo 2. Tot 8*8 + 4 +
2 = 70.
Per essere sicuro che ci siano 3 simboli in comune tra 2 famiglie,
devono combaciare  2 archi.
In questo caso se tenessi buona la l), potrei eliminare solo f) ed i),
le uniche che hanno due 2 vicini, percio' non e' una buona scelta.
Molto piu' conveniente giocare le quaterne presenti nella f) che:
con gli archi 1,2 elimina b),e),g)
 "        "   2,2   "     i),l)
 "        "   3,1   "     a),c),h)   
Praticamente se gioco le 8 quaterne generate dalla rotazione del
quadrilatero 1,2,2,3 posso coprire ben 62 quaterne.
Restano escluse le 16 quaterne di a) ed d)
Osservo subito che mi basta giocare 4 sole quaterne appartenenti ad a) 
ruotando di 2 passi, per coprire le 8 di d) e le 4 non giocate di a).
Con la semplice osservazione di queste partizioni, ho scelto cosi' 12
quaterne fra  70, sicuro che qualunque sia quella estratta, fra le mie
c'e' un bel 3!
Sperando di essere stato abbastanza chiaro, spero che questa idea possa
avere un seguito.
Per combinazioni piu' grosse, il numero di famiglie cresce rapidamente.
Generare le varie famiglie dovrebbe essere abbastanza semplice, piu'
difficile e' selezionare quelle giuste.
Trovare ad es. un riduttore ottimale per C(20,6) che mi garantisce il 5,
non e' cosi' semplice.
Occorre generare tutte le partizioni utili e selezionare quelle che
eguagliano le altre per almeno 4 archi.
Se qualche volontario vuole approfondire... aspetto sviluppi.
:)dario



 :)dario
Sia la generazione delle famiglie che il controllo delle relazioni di
"coincidenza N-1" non mi sembrano difficilissime da implementare in un
programma. Appena ho tempo provo ad applicare l'algoritmo al caso C(20,6)
Ciao, Silv:o)

318 giocate.
Nel nostro caso avremmo:
             quaterne con 4 punti        =1
c(4,3)*c(4,1)quaterne per 3 punti        =16
L'insieme teorico minimo per fare almeno un 3 è 70/17=5 giocate...
infatti una soluzione ottima (trovata usando il simplesso (ho questo a
disposizione :( ) è:
1478
1567
1568
2345
2346
2378
Cioè sei elementi.... gli 8 di Silvio sono buoni, ma credo che l'errore sia
troppo per l'esempio portato (uno scarto del genere è costoso...nel
superenalotto :)
Il problema penso che sia proprio nel rilevare la relazione di equivalenza.
La migliore (che dà la distribuzione più equilibrata degli elementi nelle
calssi) è appunto considerare gli insiemi che hanno quella caratteristica.
Mi spiego, considerando una quartina, la classe sono tutte le quartine che
hanno la distanza 1 (o un numero a piacere o ancora meglio una serie di
nuemeri a piacere).
E' la migliore tant'è che ci serve per calcolare il minimo teorico, ma il
problema è che il set-covering (o analoghi) su questi insiemi è alquanto
voluminoso....
Se non ho capito male (considerate le frasi precedenti come pensieri ad alta
voce) quindi cerchiamo funzioni che non danno l'ottimo, ma che tendono ad
avvicinarsi più semplicemente...
E' cosi?
P.S.
Non faccio che meravigliarmi delle centinaia di sfaccettature che VOI
riucite a trovare su un singolo problema...e c'è chi dice che non c'è
bisogno di fantasia!!
Walter