Newsgroup: it.hobby.enigmi
Titolo: Salve a tutti: chi mi da' una mano?

Saluto tutti.
Leggo sempre questo gruppo di discussione,
pero' e' la prima volta che "mi permetto" di intervenire.
E lo faccio per chiedere un aiuto.
Ho 16 squadre (A,B,C,...,P) che devono incontrarsi
in un torneo dove in ogni partita partecipano 4 squadre
(pensate ad un torneo di carte, come Hearts di Windows).
Vorrei organizzare un calendario di partite in modo tale che
ogni squadra incontri  tutte le altre squadre, pero' una sola volta.
Esempio per A
partita 1 A-B-C-D
partita 2 A-E-F-G
partita 3 A-H-I-J
partita 4 A-K-L-M
partita 5 A-N-O-P
Teoricamente ogni squadra gioca 5 partite ed il torneo si esaurisce in
20 partite.
Il problema e che "nella pratica" non riesco assolutamente a sviluppare
il calendario.
Mi date una mano, se e' possibile?.
C'e' un approccio matematico del problema?
Vi ringrazio anticipatamente.
Luigi

 wrote in message
39C672CC...@ftbcc.it...

Credo che le partite dovrebbero essere 15, perchè non appena comincio a
sviluppare quelle di B noto subito che ha già incontrato A-C-D nella partita
conteggiata nello sviluppo di A.
Così a occhio eh!

 ogni squadra incontri  tutte le altre squadre, pero' una sola volta.
Questo problema me ne ricorda altri discussi tempo fa, che sono stati
affrontati con il famoso regolo circolare. Per l'occasione provo a costruire
un regolo cilindrico.
Consideriamo il seguente schema, che rappresenta le prime 4 partite, come un
cilindro (una sorta di contatore dell'acqua, o di contachilometri), dove
ciascuna colonna puo' ruotare in verticale (dopo l'ultima casella si ritorna
alla prima).
A B C D
E F G H
I J K L
M N O P
Da questo otteniamo altri tre gruppi di 4 partite ciascuno, tenendo fissa la
prima colonna, e facendo ruotare le altre verso il basso, di tante
posizioni, rispetto allo schema base, quante ne indica il numero posto in
testa di ciascuna colonna.
- 1 2 3    - 2 3 1     - 3 1 2
A N K H    A J G P     A F O L
E B O L    E N K D     E J C P
I F C P    I B O H     I N G D
M J G D    M F C L     M B K H
L'ultimo gruppo di 4 partite lo ottieni semplicemente dalla tabella base,
invertendo le righe con le colonne:
A E I M
B F J N
C G K O
D H L P
ciao
paolo

 Vi ringrazio anticipatamente.
Ho trovato un metodo matematico (nel vero senso della parola) per
risolvere il problema, che da' luogo ad altre interessanti domande:
Prendiamo una matrice 4x4 cosi' fatta:
1 2 3 4
5 A B C
6 D E F
7 G H I
Prendiamo la sottomatrice letterale 3x3 e fingiamo di volerne calcolare
il determinante; avremo i seguenti prodotti:
Quelli col segno +
AEI   BFG   CDH
Quelli col segno -
CEG   AFH   BDI
A questo punto faccio cosi':
Prendo tutte le righe e le colonne:
1234
5ABC
6DEF
7GHI
1567
2ADG
3BEH
4CFI
Ottenendo i primi 8 incontri.
Per i successivi, elimino una alla volta le 4 colonne ottenendo
altrettante sottomatrici alfanumeriche delle quali, calcolandone il
determinante, considero alternativamente i prodotti col segno + e
quelli col segno -, e moltiplicando questi ultimi per il primo numero
della colonna;
ESEMPIO:
Elimino la prima colonna ed ottengo la sottomatrice letterale vista
all'inizio. Prendo i prodotti col segno + e li moltiplico per 1
ottenendo:
1AEI
1BGF
1CDH
Eliminando la seconda colonna prendo i prodotti col segno - e li
moltiplico per 2;
Per la terza quelli col segno + e moltiplico per 3;
Infine, elimino la quarta colonna, prendo i prodotti col segno - e li
moltiplico per 4;
ALLA FINE DI TUTTO OTTENGO:
1234
1567
1AEI
1BGF
1CDH
27EC
25FH
26BI
2ADG
3BEH
35DI
37AF
36CG
4CFI
47BD
45GE
46AH
5ABC
6DEF
7GHI
Che sono gli incontri cercati.
Naturalmente, scambiando le righe con le colonne (scambiando pero'
anche i segni dei prodotti) e costruendo la matrice con le lettere
disposte in tutti gli altri modi possibili si trovano tutte le altre
soluzioni accettabili...
A questo punto le domande nascono spontanee:
QUANTE SONO LE POSSIBILI SOLUZIONI? (semplice...)
QUAL'E' IL NUMERO MINIMO DI MATRICI DIVERSE* TRA LORO NECESSARIE PER
INDIVIDUARE TUTTE LE POSSIBILI SOLUZIONI? (piu' complicato...)
*Con le lettere/numeri disposte in maniera diversa
Suggerimento (forse ovvio): eliminiamo tutte le possibili simmetrie...
Ciao a tutti, Barabbino.
Sent via Deja.com 
http://www.deja.com/
Before you buy.

Paolo Licheri ha elegantemente scritto:

La trovo una bellissima soluzione, semplice ed elegante.
Se ti interessa, ho trovato un metodo diverso (almeno nella
costruzione) che da' luogo ad altre interessanti domande....
Ciao, Barabbino.


Metodo intrigante, pero' non funziona:
per  esempio con B
B-H si trova in due incontri, cosi' B-O
B-G non c'e', cosi' B-P
Ciao Luigi
Pero' non so cosa e' un regolo circolare.
Mi puoi dare informazoni? C'e' in qualche FAQ?
Di nuovo Luigi


Ciao a tutti, Barabbino.


 Mi puoi dare informazoni? C'e' in qualche FAQ?
visita il sito con l'archivio del ng
http://web.tiscalinet.it/paololicheri
alla sezione varie, nel problema "laboratorio di lingue", si parla
dell'utilizzo del regolo circolare perfetto (RCP), uno strano aggeggio
inventato da Dario.
La definizione era in un altro thread, che non sono riuscito a reperire. Se
Dario o qualcun altro me la potesse mandare, provvedero' ad inserirla nel
sito.
ciao
paolo

 inventato da Dario.
Ti ringrazio della fiducia, ma sola la definizione e' mia. 
Queste serie di numeri tali che le differenze di ciascuna coppia siano
tutte differenti sono state oggetto di molti studi.
Regoli perfetti non circolari, sono noti come grafi graziosi, ne ha
parlato anche Gardner.
Vedi
http://members.aol.com/golomb20/
http://www.ee.duke.edu/~wrankin/golomb/golomb.html
Gli RCP sono la stessa cosa, considerando la serie di numeri chiusi ad
anello.
Un es. con 4 termini e' 0,1,3,9. Le differenze di questi numeri, a
coppie coprono tutto il range da 1 a 12.
Allora mettiamo i numeri da 0 a 12 distribuiti su una circonferenza in
modo regolare:
               0
          12       1
       11             2
 
     10                 3
 
       9              4
          8        5
             7  6    
 
 
Costruisco un quadrilatero unendo 0,1,3,9,0
Vediamo che i punti 0 ed 1 distano 1 unita' d'arco da una parte e 12
unita' dall'altra.
Se elenchiamo tutte le distanze dei punti 0,1,3,9 presi a coppie abbiamo
Punti      Distanze
0,1         1,12
0,3         3,10
0,9         9,4
1,3         2,11
1,9         8,5
3,9         6,7
Come abbiamo detto tutte le distanze da 1 a 12 sono presenti una sola
volta.
Cosa ci serve tutto questo?
Se ad es. come nel problema appena proposto, ho 13 persone, che devo
fare incontrare 4 alla volta per 13 volte in modo che ciascuno incontri
tutti gli altri, il nostro RCP ci da subito la risposta.
Basta far ruotare il quadrilatero all'interno del cerchio di una tacca
alla volta per 12 volte, i vertici intercettano le varie quadruple:
0,1,3,9
1,2,4,10
2,3,5,11
........
12,0,2,8
Proprio per la caratteristica del RCP, nessuna coppia sara' presente 2
volte.
Nell'occasione ricordata da Paolo riuscimmo a costruire un RCP con 10
termini 
10RCP = 0,1,3,9,27,49,56,61,77,81. 
Le differenze a due a due sono tutti i naturali da 1 a 90.
:) dario

 coppie coprono tutto il range da 1 a 12.
ecc.
Ringrazio Dario per l'aggiornamento sui RCP, provvedero' ad inserire la
descrizione nell'archivio.
Questi strumenti possono essere utilizzati, con un piccolo *trucco*, anche
per QUESTO problema.
(Nota: anche se il problema e' stato gia' risolto da Barabbino, propongo
questa soluzione come un'esercitazione che mi sembra di qualche interesse).
Il *trucco*:
Consideriamo per il momento che le squadre siano 21 (anziche' 16), e che ad
ogni incontro partecipino 5 squadre (anziche' 4).
E' facile verificare che ci saranno complessivamente 21 incontri (anziche'
20) e che ciascuna squadra partecipera' a 5 partite (come nel problema
originario: e' importante osservare che questo valore e' rimasto invariato).
Siamo quindi nelle condizioni di utilizzare un RCP di 21 tacche (numerate da
0 a 20), e con un pentagono rotante, posizionato inizialmente con i vertici
nei punti 0,1,4,14,16.
Con il sistema descritto da Dario verifichiamo che le distanze tra le coppie
di vertici, misurate sulla circonferenza nei due sensi, coprono tutti i
valori da 1 a 20.
Ruotando il pentagono si genera quindi uno schema con tutti i 21 incontri a
5 squadre.
Non ci resta che eliminare gli effetti perversi del trucco.
Siano le 21 squadre:
ABCDEFGHIJKLMNOP(VWXYZ)
dove le prime 16 lettere corrispondono alle squadre reali, le ultime 5 a
squadre *virtuali*.
Facciamo in modo che in una partita, per esempio la prima, si incontrino le
5 squadre virtuali: possiamo ottenere questo disponendo le squadre virtuali
in corrispondenza dei vertici del pentagono, e tutte le altre squadre nelle
rimanenti 16 tacche.
Dal momento che ciascuna squadra deve disputare 5 partite, e che i virtuali
ne hanno gia' disputato una (che possiamo chiamare *partita virtuale*),
ciascuno di essi ne deve disputare altre 4, e, non potendosi piu' incontrare
tra loro, in ciascuna delle 20 partite *reali* sara' presente una ed una
sola squadra virtuale, e quindi 4 squadre reali.
Allora eliminiamo dallo schema la partita virtuale, e da ciascuna partita
reale eliminiamo il giocatore virtuale, ed otteniamo lo schema richiesto di
20 partite a 4 squadre.
Spero di essere stato sufficientemente chiaro, e che questa volta la cosa
funzioni
:-)
ciao
paolo

 20 partite a 4 squadre.
Geniale !
:) dario

 Geniale !
Decisamente.
E pensare che cominciammo ad usare gli RCP in questi problemi quasi per
caso!
Silv:o)

 caso!
Che ne dite creare una societa' per la produzione di regoli?
:-)
ciao
paolo
P.S.
si scrive gli RCP (gli errecipi') o i RCP (i regoli...)?

 si scrive gli RCP (gli errecipi') o i RCP (i regoli...)?
La prima che hai detto (almeno per questa volta ;-))))
Ciao
Gianni