Newsgroup: it.hobby.enigmi
Titolo: BIBD

Gli RCP sono sempre utilizzabili ?
Dunque, cerchiamo di mettere un po' d'ordine.
Un sottogruppo di n k-tuple, selezionato da un'intera collezione di N
k-tuple, in modo tale che ogni elemento e' regolato da una
caratteristica prefissata, (es. ogni elemento incontra ciascun altro una
sola volta) e'
noto come BIBD, acronimo di Balanced Incomplete Block Design. Ecco un
es:
0127
1357
2457
0347
1467
2367
0567
3456
0246
0136
1256
0235
0145
1234
Ci sono 8 elementi divisi in 4-tuple. Delle C(8,4)=70 possibili
quadruple ne sono state selezionate 14 (block) tali per cui, ciascun
elemento e' presente lo stesso numero di volte (7), ed ogni paio di
elementi si incontra nella stessa riga lo stesso numero di volte (3), in
piu' sono presenti tutte le possibili triple una sola volta.
La notazione standard e' BIBD(v,b,r,k,y). Dove, in realta' l'ultimo
simbolo dovrebbe essere Lambda, ma in ascii come faccio?
I parametri sono:
v = numero degli elementi
b = numero dei subset (chiamati blocks)
r = numero di volte che ciascun elemento e' presente
k = numero di elementi contenuti in un block 
y = numero di volte che ciascun paio si incontra in un block
L'esempio fatto corrisponde a BIBD(8,14,7,4,3). Questi 5 parametri non
sono indipendenti, ma soddisfano le 2 relazioni vr = bk,  y(v-1) =
r(k-1). Per questo motivo a volte si incontra la notazione piu' compatta
BIBD(v,k,y) gli altri 2 parametri sono facilmente ricavabili.
b = v(v-1)y/k(k-1)
r = y(v-1)/k-1.
Nel nostro caso BIBD(8,4,3)
b = 8*7*3/4*3 = 14
r = 3*7/3     =  7.
Il problema del torneo proposto ultimamente e risolto da Paolo e
Barabbino, che ha riacceso l'interesse sugli RCP, poteva semplicemente
essere annunciato cosi': Trovare un BIBD(16,4,1).
Ora il dilemma e' "Come diavolo si trovano questi BIBD ?". Purtroppo non
c'e' un metodo generale.
Abbiamo visto che gli RCP ci permettono di generare i BIBD con
v=n^2-n+1, k=n, y=1,
e con il trucchetto escogitato da Paolo, il "PL metod", i BIBD con
v=n^2-n, k=n-1, y=1
Dove in entrambi i casi n deve essere un primo o un suo multiplo.
Quali altre armi abbiamo ? A seconda dei casi si puo' provare con la
geometria proiettiva, con le matrici di Hadamard, con i quadrati
latini,... ed altre simili strutture.
Un es. Nella Transylvania Lottery vengono estratti 3 numeri su 14,  si
vince col 3 e col 2.
E' evidente che per essere sicuri di azzeccare un 3, bisognera' giocare
C(14,3)=364 schedine, e per essere sicuri di fare 2? Ci viene in aiuto
la geometria proiettiva. Disegno un triangolo equilatero con le sue
altezze  
         a
        /|\
       / | \
     b/  |  \f 
     /   g   \
    /    |    \
  c/_____|_____\e
         d
Immaginiamo tracciate anche le altezze cf, be e la linea, generalmente
rappresentata da un cerchio inscritto, che tocca i punti bfd. Allora
avremo un Piano di Fano, una struttura con 7 vertici, etichettati a-g e
7 linee (3 lati, 3 altezze ed il cerchio) in modo che ad ogni vertice
concorrono 3 linee, su ogni linea ci sono 3 vertici, ed ogni coppia di
vertici e' presente su una linea. 
Disegno 2 piani di Fano, etichetto i vertici del primo con i numeri da 1
a 7, ed i vertici del secondo con i numeri da 8 a 14. Poi gioco i 3
numeri presenti su ciascuna linea, ecco le 14 giocate:
1,2,3    8,9,10
3,4,5   10,11,12
5,6,1   12,13,8
1,7,4    8,14,11
3,7,6   10,14,13
2,7,5    9,14,12
2,4,6    9,11,13
E' evidente che dei 3 numeri estratti, 2 devono far parte di una stessa
figura, e come abbiamo visto saranno intercettati da una linea. Le 14
giocate mi assicurano la vincita di un due. Siamo cosi' tornati al
concetto dei RIDUTTORI che piu' volte abbiamo tentato di trattare con
scarsi risultati.
Per sostituire il nostro grafo con la matrice corrispondente, etichetto
le 7 linee coi muneri da 1 a 7
ac = 1
ce = 2
ea = 3
ad = 4
cf = 5
be = 6
bdf= 7
Ottengo allora:
   a b c d e f g
1  1 1 1 0 0 0 0 
2  0 0 1 1 1 0 0
3  1 0 0 0 1 1 0
4  1 0 0 1 0 0 1
5  0 0 1 0 0 1 1
6  0 1 0 0 1 0 1
7  0 1 0 1 0 1 0
Un "1" all'incrocio, indica che quel vertice appartiene a quella linea,
altrimenti "0".
Si puo' vedere, che ci sono tre "1" per ogni riga e per ogni colonna,
ogni paio di righe ha un "1" in comune, cosi' come ciascun paio di
colonne. Questa caratteristica non cambia permutando righe e colonne a
piacimento. Questo ci permette di risistemare la nostra matrice cosi':
 
   c g d e b f a
3  0 0 0 1 0 1 1
1  1 0 0 0 1 0 1
5  1 1 0 0 0 1 0
4  0 1 1 0 0 0 1
2  1 0 1 1 0 0 0
6  0 1 0 1 1 0 0
7  0 0 1 0 1 1 0
Che diventa un "Circolante", se immaginiamo le linee come chiuse ad
anello, tutte le righe o colonne della matrice, equivalgono ad una
posizione di uno
stesso anello ruotato di uno scatto unitario per sette volte.
Tutta la matrice puo' essere descritta con una sola riga,
la notazione ufficiale e' CIRC(0001011). Paolo! il tuo cilindro rotante
e' gia' stato inventato.
Allora Massimo, alla tua domanda non so rispondere, pero' abbiamo visto
dal BIBD(8,4,3) che se ogni terna e' presente una sola volta, ogni
coppia deve esserelo  3 volte, Sempre che siano utilizzabili, dobbiamo
cercare degli RCP dove le differenze si presentino piu' volte. In un RCP
di 37 tacche se segno i punti 0,7,8,12,18,20,21,23,27, ogni distanza
sara' disponibile 2 volte.
:) dario

 2,4,6    9,11,13
Se accoppiamo *ciascuna* riga della prima tabella con *ciascuna* riga
della seconda, otteniamo 49 bloks di 6 elementi, senza quintuple
ripetute, dove ciascun numero compare 3*7=21 volte.
Scriviamo questa tabella di 49 elementi, ed un'altra identica con i
numeri incrementati di 14 (da 15 a 28).
Ripetendo il procedimento otteniamo 49^2 bloks di 12 elementi, senza
11_tuple ripetute, e cosi' via.
E' una risposta molto parziale al problema posto da Massimo, ma forse
potrebbe servire come base per la ricerca di qualcosa di piu' generale.
Per esempio partendo dalle tabelle generate dagli RCP.
Qualcuno ci vuole provare?
ciao
paolo
Sent via Deja.com 
http://www.deja.com/
Before you buy.

 sara' disponibile 2 volte.
Come l'hai trovato?
Silv:o)

 come li hai definiti.
soprattutto perche` i BIDS (????) me li sono inventati io. Eppure la sigla
corretta ce l'avevo davanti, nell'object...
Silv:o(

 soprattutto perche` i BIDS (????) me li sono inventati io.
ma allora la sigla e' esatta
BIDS (Blocks Inventati Da Silvio)
scusa, ma non ho resistito
:-)


 per  come li hai definiti.
E' vero, volevo solo sottolineare che in certi casi lo possono
diventare.
Come si sa, per questi riduttori, piu' in generale "Covering Problem",
non c'e' niente di meglio che la forza bruta. Una enorme lista dei
risultati migliori finora ottenuti e' tenuta qui:
http://www.xs4all.nl/~rbelic/lista.htm
:) dario

 al rendimento massimo teorico ed ai riduttori perfetti. 
Infatti, la mia osservazione nasce dal fatto che non esistono
"riduttori perfetti" per giochi come il SEL etc....
Eppure, non so perche', ma il mio istinto mi dice che da
qualche parte esista una soluzione......ma il difficile
e' trovarla.
CiaO,
Massimo
PS..  grazie per il prezioso contributo a tutti.
      ;-))