Discussione:
[MAT] Coperture
(troppo vecchio per rispondere)
Giorgio Vecchi
2018-01-16 09:27:16 UTC
Permalink
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
Francesco Di Matteo
2018-01-16 12:59:54 UTC
Permalink
Il 16/01/2018 10:27, Giorgio Vecchi ha scritto:
[cut]
Post by Giorgio Vecchi
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.
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
Francesco Di Matteo
2018-01-16 14:07:42 UTC
Permalink
Post by Francesco Di Matteo
[cut]
Post by Giorgio Vecchi
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.
01-02-03
01-07-08
02-04-07
02-06-08
03-05-08
03-06-07
04-05-06
http://www.camelott.it/Varie/sistemi/8nx7t.htm
Francesco
opps... questo è a garanzia ambo...
Cerco meglio allora...
GaS
2018-01-16 23:36:46 UTC
Permalink
Il giorno martedì 16 gennaio 2018 10:27:18 UTC+1, Giorgio Vecchi ha scritto:
[cut]
Post by Giorgio Vecchi
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).
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.
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
Giorgio Vecchi
2018-01-17 07:58:30 UTC
Permalink
Post by Giorgio Vecchi
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 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
Giorgio Vecchi
2018-01-19 14:48:01 UTC
Permalink
Post by Giorgio Vecchi
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
Complimenti per avere trovato a mano una soluzione in 7. Non è ancora
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
GaS
2018-01-19 19:18:20 UTC
Permalink
Post by Giorgio Vecchi
Post by Giorgio Vecchi
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
Complimenti per avere trovato a mano una soluzione in 7. Non è ancora
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.
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
Francesco Di Matteo
2018-01-17 09:35:38 UTC
Permalink
Il 16/01/2018 10:27, Giorgio Vecchi ha scritto:
[ri-cut]
Post by Giorgio Vecchi
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).
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.
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
Giorgio Vecchi
2018-01-17 16:21:09 UTC
Permalink
Post by Francesco Di Matteo
1 2 4 6
2 3 5 7
3 5 6 7
1 4 5 8
1 2 6 8
3 4 7 8
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
GaS
2018-01-18 11:49:59 UTC
Permalink
Post by Giorgio Vecchi
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.
Avevo trovato un minimo *teorico* di 5 righe ragionando nel modo seguente: ogni riga mi "copre" 17 estrazioni, ovviamente righe diverse poi vanno a coprire le stesse estrazioni ma comunque avendo 70 estrazioni possibili abbiamo un minimo di 70/17=4,+ righe e quindi, arrotondando, 5 righe è un minimo teorico (purtroppo solo teorico, come abbiamo visto). Estrapolarlo per generici N, K, G non è però banale

[cut]
Post by Giorgio Vecchi
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.
[cut]

E ci credo! In effetti sono tutte la *stessa soluzione* con solo trasposizioni delle cifre, come sospettato da Giorgio. Difficile scrivere come fare la trasformazione e quindi vi do direttamente le trasformazioni necessarie per arrivare alla seguente soluzione base (diversa dalle altre 4 ma praticamente identica alla prima di Giorgio):

1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
4 6 7 8

(non mi chiedete come l'ho scelta, è troppo lungo :-)

Per ognuna delle 4 soluzioni presentate (1 Francesco + 3 Giorgio) le trasformazioni ve le propongo nella notazione standard del tipo (ABC)(D)(EF)(G) che significa:
- A->B->C->A
- D rimane se stesso
- E->F->E
- G rimane se stesso

e dove ovviamente la freccia A->B denota che che il numero A deve essere sostituito con il numero B.

Applicando queste trasformazioni, ed eventualmente riordinando le righe e le cifre nelle singole righe, tutte e 4 soluzioni si trasformano in quella precedente:

------SOL 1-------
Post by Giorgio Vecchi
1 2 3 4
1 5 6 7
1 2 3 8
4 5 6 8
2 3 5 7
4 6 7 8
(132)(4)(5)(6)(7)(8)

-------SOL 2--------------
Post by Giorgio Vecchi
1 2 3 4
1 2 5 8
1 6 7 8
2 6 7 8
3 4 5 6
3 4 5 7
(153)(27864)

-----SOL 3----------------
Post by Giorgio Vecchi
1 2 3 4
1 4 5 7
1 4 6 7
2 3 7 8
3 5 6 8
2 5 6 8
(1)(27354)(68)


-------SOL 4--------------
Post by Giorgio Vecchi
1 2 4 6
2 3 5 7
3 5 6 7
1 4 5 8
1 2 6 8
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
Giorgio Vecchi
2018-01-18 17:15:16 UTC
Permalink
Post by GaS
ogni riga mi "copre" 17 estrazioni, ovviamente righe diverse poi vanno a
coprire le stesse estrazioni ma comunque avendo 70 estrazioni possibili
abbiamo un minimo di 70/17=4,+ righe e quindi, arrotondando, 5 righe è un
minimo teorico (purtroppo solo teorico, come abbiamo visto). Estrapolarlo
per generici N, K, G non è però banale
Ciao Gabriele. Sì, questo serve a sgrossare e a trovare sicuramente un
minimo. Ma molto probabilmente il "vero" minimo è sempre superiore perché
entrano in gioco le coperture sovrapposte, ma concordo che non sia così
semplice da trovare.
Post by GaS
[cut]
E ci credo! In effetti sono tutte la *stessa soluzione* con solo
trasposizioni delle cifre, come sospettato da Giorgio. Difficile scrivere
come fare la trasformazione e quindi vi do direttamente le trasformazioni
necessarie per arrivare alla seguente soluzione base (diversa dalle altre
1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
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
GaS
2018-01-19 11:41:53 UTC
Permalink
Post by Giorgio Vecchi
Post by Giorgio Vecchi
1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
4 6 7 8
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 è...
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
Giorgio Vecchi
2018-01-19 14:45:11 UTC
Permalink
Post by GaS
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
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
Dario Uri
2018-01-25 20:58:25 UTC
Permalink
Post by Giorgio Vecchi
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).
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
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
Giorgio Vecchi
2018-01-26 09:36:33 UTC
Permalink
Ciao a tutti. Giorgio queste configurazioni si chiamano Block Design. sono
imparentate con la geometria proiettiva, i quadrati latini, le triple di
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
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
Dario Uri
2018-01-26 21:49:24 UTC
Permalink
Post by Giorgio Vecchi
Post by Dario Uri
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
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
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
1 2 3 4
1 2 3 8
1 2 5 7
3 5 6 7
4 5 6 8
4 6 7 8
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

Continua a leggere su narkive:
Loading...