Newsgroup: it.hobby.enigmi
Titolo: [MAT] Coperture

Di cose analoghe se n'è già parlato in questo NG. Ricordo con nostalgia i 
tempi del Gino e della Gina per esempio. Però non so se ci sia mai stato un 
approfondimento sul tema che vorrei introdurre adesso. Si tratta dei famosi 
sistemi ridotti con copertura a garanzia. Premetto che non sono un esperto e 
che francamente non mi interessa l'ambito in cui questi sistemi vengono da 
alcuni utilizzati (lotto, totocalcio, ecc.) però mi incuriosisce l'aspetto 
matematico e vorrei riuscire a sviscerarne qualcuna delle caratteristiche 
che al momento mi risultano magicamente misteriose. Fine della premessa. 
Passo al problema.
 
Utilizzerò un esempio di gioco ad estrazione (tipo lotto) perché è 
sicuramente più chiaro per tutti.
Abbiamo N numeri interi consecutivi a partire da 1. Come esempio diciamo N = 
8.
Abbiamo un numero K < N che rappresenta il numero di numeri che verranno 
estratti, esempio K = 4. Le possibili diverse estrazioni saranno in numero 
di C(N, K), in questo caso 70. Queste estrazioni vengono spesso chiamate 
"colonne" anche se di solito si scrivono come righe, per non confonderci 
proporrei di chiamarle righe o sequenze, ad esempio 1 2 3 4, 1 2 5 8, 4 5 7 
8...
 
Per ogni possibile estrazione di una sequenza tra le 70 di cui sopra, io 
voglio avere la garanzia di indovinare almeno 3 dei 4 numeri (voglio avere 
la certezza di fare almeno un terno). Devo quindi giocare un sistema (di 
righe).
 
Un possibile sistema potrebbe essere questo:
 
1 2 3 4
1 5 6 7
2 3 5 8
4 6 7 8
1 2 3 8
2 3 4 5
1 2 3 6
1 2 4 5
 
Sono 8 sequenze che garantiscono la copertura con garanzia 3 di tutte le 70 
sequenze possibili, cioè per ogni possibile sequenza estratta (ad esempio la 
1 3 5 7) c'è almeno una riga del mio sistema che ha almeno 3 numeri in 
comune (in questo caso la riga 1 5 6 7).
 
Quello che per adesso vi propongo è di trovare una soluzione migliore, cioè 
un sistema formato da meno di 8 righe.
 
Ciao.
 
Giorgio 
 

 
 
01-02-03
01-07-08
02-04-07
02-06-08
03-05-08
03-06-07
04-05-06
 
 
fonte:
http://www.camelott.it/Varie/sistemi/8nx7t.htm
 
 
Francesco


opps... questo è a garanzia ambo...
Cerco meglio allora...

Il giorno martedì 16 gennaio 2018 10:27:18 UTC+1, Giorgio Vecchi ha scritto:
[cut]
 

S
.
.
.
P
.
.
.
O
.
.
.
I
.
.
.
L
.
.
.
E
.
.
.
R
.
.
.
?
 
Soluzione con 7 righe:
 
1 2 3 4
1 5 6 7
1 2 3 8
1 4 7 8
2 4 5 6
2 3 7 8
3 4 5 6
 
Non posso dimostrare che sia ottimale ma mi stupirei non poco se qualcuno presentasse soluzioni migliori.
Purtroppo nessun approccio "strutturato" che si possa ripetere per altri N/K.
Ho perso tantissimo tempo dando per scontato che nella soluzione ci dovessero essere le due righe "1 2 3 4" e "5 6 7 8" ma arrivavo solo a soluzioni con 8 righe. Continuo (persevero?) a pensare che la soluzione ottimale debba avere quelle due righe ma non la trovo, appena ho abbandonato questa ipotesi in pochi tentativi ho trovato la soluzione da sette righe. Non lo capisco ma è così... :-)
 
Ciao
GaS

 è così... :-)
 
Ciao Gabriele!
 
Complimenti per avere trovato a mano una soluzione in 7. Non è ancora 
l'ottimo però ti posso dire che ci sei andato MOOOLTO vicino! ;)
 
Uno dei misteri (ma ce ne sono altri), che anch'io non digerisco, è proprio 
che la soluzione ottimale non contempli la presenza delle righe 1 2 3 4 e 5 
6 7 8, insomma due righe che non abbiano tra loro elementi in comune. Credo 
che tutti partirebbero mettendo giù per prime quelle due righe lì e invece 
no. Io sarei contento se arrivassimo a giustificare il fatto che la 
soluzione ottimale in questo caso non può avere le due suddette righe. Dico 
"in questo caso" perché non penso sia generalizzabile, certamente con altri 
N e K (e G, la garanzia) questo potrà accadere.
 
Ciao.
 
Giorgio
 

 
 
Ho trovato queste sei:
 
1 2 4 6
2 3 5 7
3 5 6 7
1 4 5 8
1 2 6 8
3 4 7 8
 
Fonte:
http://sistemigiocolotto.blogspot.it/2016/03/sistema-lotto-ridotto-8-numeri-in-gioco.html
 
 
Ciao
Francesco
 
 
 

 
http://sistemigiocolotto.blogspot.it/2016/03/sistema-lotto-ridotto-8-numeri-in-gioco.html
 
 
Ok Francesco. Questa è una soluzione ottimale. Nel senso che non ci sono
soluzioni con meno di 6 righe. Questo l'ho riscontrato scrivendo un
programmino, non ho una formula per determinare il minimo, anche se mi
piacerebbe ricavarla.
 
Sicuramente una caratteristica di questa soluzione è che ogni
numero compare esattamente lo stesso numero di volte, in questo caso 3. Qui
i conti sono semplici: N = 8, 6 righe da 4 fa 24 numeri. 24 / 8 = 3. Per
altre combinazioni di N, K e G non è detto che il risultato dia un numero
intero ma ci si può aspettare che le presenze di ogni singolo numero non si
discostino di molto tra loro.
 
Il fatto però che ogni numero compaia 3 volte non è garanzia che il sistema
copra perfettamente tutte le sequenze. Un sistema bilanciatissimo:
 
1 2 3 4
5 6 7 8
1 2 5 6
3 4 7 8
1 3 5 7
2 4 6 8
 
ha tutti i numeri che compaiono 3 volte ma non copre al 100%.
 
Confrontando tra loro varie soluzioni che ho trovato, si notano alcune
caratteristiche comuni tra posizioni e occorrenze dei numeri che fanno 
pensare che
in fondo si tratti di un'unica soluzione rigirata in vari modi, però al
momento non saprei come ricondurre l'una all'altra. Tra queste
caratteristiche ce n'è una "strana", che naturalmente le accomuna tutte. Vi
riporto 3 soluzioni, oltre a quella che ha trovato Francesco. Sapete dire 
che
caratteristica è?
 
1 2 3 4
1 5 6 7
1 2 3 8
4 5 6 8
2 3 5 7
4 6 7 8
 
1 2 3 4
1 2 5 8
1 6 7 8
2 6 7 8
3 4 5 6
3 4 5 7
 
1 2 3 4
1 4 5 7
1 4 6 7
2 3 7 8
3 5 6 8
2 5 6 8
 
Ciao.
 
Giorgio
 
 

 3 4 7 8
 
   (16872453)
 
---------------------
 
 
N.B.: le trasformazioni presentate non sono univoche, altre trasformazioni analoghe che portano alla stessa soluzione base sono comunque possibili
 
Trovare le trasformazioni a mano è più facile a farsi che a scriversi, si fa veramente ad occhio e non saprei quindi come automatizzare (=scriptare/programmare) la metodologia per tutte le soluzioni trovate dal programma di Giorgio. A proposito, quante sono?
 
Avendo avuto un successo di 4/4 è facile ipotizzare che effettivamente ci sia una sola soluzione base ma fino a quando non si provano tutte...
 
Ciao,
GaS

 4 6 7 8
 
Ottimo! Mi fido!
 
Dicevo appunto che c'erano alcune caratteristiche che mi facevano pensare 
che si trattasse di una soluzione unica (a proposito non ti so dire quante 
siano, il mio programma taglia svariati rami e non le trova tutte). Quella 
caratteristica"strana" di cui parlavo nel post precedente si vede piuttosto 
bene in questa tua soluzione. Aspetto ancora che qualcuno la trovi poi vi 
dico qual è...
 
Penso che analizzare le caratteristiche che connotano la soluzione ottimale 
possa essere utile nella ricerca di nuove soluzioni quando i numeri 
diventano anche di poco più grandi. Fino a che si tratta di numeri come 8 e 
4 anche una ricerca esaustiva termina in tempi accettabili. Se anche un 
programma le volesse provare tutte fino a un livello di 6, una volta 
battezzata la prima (che sarà sempre 1 2 3 4) ne abbiamo da provare 69 x 68 
x 67 x 66 x 65. Il tutto fa 1.3 miliardi circa. Tutto sommato si può anche 
pazientare. Ma prendiamo ad esempio il caso N = 14, K = 4, G = 3 con un 
totale di 1001 righe, di cui si sa che esiste una soluzione (ottimale?) in 
42. Anche ammesso di essere riusciti a trovare un qualche criterio per 
individuare ad ogni livello 3 sole possibili scelte su cui operare (sulle 
1001 possibili), il numero di tentativi sarebbe 3^41 =~ 3.6 x 10^19 ! Eppure 
qualcuno la soluzione in 42 l'ha trovata e quindi ci deve essere qualche 
altro tipo di approccio (manuale o automatico).
 
La cosa mi intriga. Non so quanto durerà, però per il momento mi ci dedico 
un po'.
 
Ciao
 
Giorgio
 

 dico qual è...
 
Per me la caratteristica *strana* sono, considerando la sol sopra, quelle due coppie di righe, una con 1-2-3 e l'altra con 4-6-8
è proprio partendo da quelle che si possono trovare abbastanza facilmente le trasformazioni per riportare ogni (alcune?) soluzione alla soluzione base. Mi sarei aspettato righe il più diverso possibile tra di loro ma invece è proprio il contrario
 
Ciao
GaS

 invece è proprio il contrario
 
In effetti anche quella è strana, ci sono sempre due coppie di righe che 
condividono 3 numeri. Ma quella che trovo ancora più strana è quest'altra:
 
1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
4 6 7 8
 
Si è detto che ogni numero compare esattamente in 3 righe. Ebbene ci sono 
sempre due stessi numeri che compaiono insieme in tutte e 3 le righe, in 
questo caso i numeri 1 e 2.
 
Se si rappresenta lo schema così (usare spaziatura fissa):
 
XXXX....
XXX....X
XX..X.X.
..X.XXX.
...XXX.X
...X.XXX
 
si vede bene che ci sono due colonne esattamente uguali. Delle 20 differenti 
colonne possibili, qui ce ne sono 8 e due di loro sono uguali! :|
 
Ciao.
 
Giorgio
 
 
 

 l'ottimo però ti posso dire che ci sei andato MOOOLTO vicino! ;)
 
Con MOOOLTO vicino intendevo il fatto che se togli la prima riga, hai già 
trovato la soluzione da 6. La prima riga è ridondante.
 
Ciao.
 
Giorgio
 


Nooooooooooo, ma pensa te!
E pensare che avevo anche fatto il ragionamento: "1-2-3-4 compaiono quattro volte mentre 5-6-7-8 compaiono tre volte, per migliorarla bisognerebbe togliere un 1 un 2 un 3 ed un 4..."
Ed avevo la riga 1 2 3 4 davanti agli occhi
 
Grazie Giorgio
ciao
GaS


Ciao a tutti. Giorgio queste configurazioni si chiamano Block Design. 
sono imparentate con la geometria proiettiva, i quadrati latini, le 
triple di Steiner.... e tante altre cose. Puoi trovare qui un manuale 
completo:
 
https://books.google.it/books?id=S9FA9rq1BgoC&printsec=frontcover&dq=cdc+handbook+combinatorial+design&hl=fr&sa=X&ved=0ahUKEwig76qo9vPYAhVCWywKHctfBuIQ6AEILjAB#v=onepage&q=cdc%20handbook%20combinatorial%20design&f=false
 
 
Molte combinazioni possono essere trovate solo con la Brute Force, e i 
migliori risultati sono mantenuti a la Jolla:
 
https://www.ccrwest.org/cover/table.html
 
 

 
https://www.ccrwest.org/cover/table.html
 
 
Grazie Dario. Molto interessante.
 
Certo non ho la pretesa di arrivare a quei livelli, per ora mi diverte 
escogitare degli algoritmi sempre più efficienti, naturalmente per i casi 
"trattabili"...
 
Ho dato un'occhiata veloce alla tabella di La Jolla. Mi sembra che riguardi 
un problema leggermente diverso da quello che avevo posto io. Io proponevo 
di "estrarre" sequenze di k numeri di cui almeno g di questi dovevano essere 
coperti da almeno una riga della soluzione. Nel caso di La Jolla vengono 
estratti g numeri che devono essere tutti presenti in almeno una riga della 
soluzione. Per confronto riporto la mia soluzione per 8,4,3:
 
1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
4 6 7 8
 
mentre per il problema di La Jolla la soluzione per il "suo" 8,4,3 è questa:
 
1  2  3  4
1  2  5  6
1  2  7  8
1  3  5  7
1  3  6  8
1  4  5  8
1  4  6  7
2  3  5  8
2  3  6  7
2  4  5  7
2  4  6  8
3  4  5  6
3  4  7  8
5  6  7  8
 
Nel mio caso ad esempio la terzina 1 2 6 non è presente in nessuna riga, 
però una qualunque quartina che la contenga (1 2 3 6, 1 2 4 6, 1 2 5 6, 1 2 
6 7, 1 2 6 8) è "coperta" (almeno 3 in comune) da almeno una delle righe 
della mia soluzione.
 
Interessante comunque.
 
Ciao.
 
Giorgio
 


Si Giorgio ho visto la differenza.  Di queste composizioni ce ne sono di 
tanti tipi, in base al problema combinatorio da risolvere es: Calendari 
di tornei, gruppi di persone che si siedono intorno a n tavoli 
rispettando certi criteri di distribuzioni ecc.. Ho trovato qui una 
panoramica chiarificatrice per alcuni casi.
 
https://en.wikipedia.org/wiki/Combinatorial_design
 
 
Il problema che proponi è quello chiamato Lotto Design, guarda in che 
modo brillante viene risolta la Transylvanian Lottery, utilizzando il 
Piano di Fano. Estrazione di 3 numeri su 14 e si vince azzeccando il 3, 
(terno) ma anche con il 2 (ambo)
 
Per una trattazione seria sul tuo problema puoi vedere qui:
https://www.collectionscanada.gc.ca/obj/s4/f2/dsk3/MWU/TC-MWU-105.pdf
 
 
Ciao
dario