Newsgroup: it.hobby.enigmi
Titolo: Per quelli bravi in matematica

In un campionato a 16 squadre, qual č il numero minimo di arbitri necessari 
affinchč nessuno diriga 2 volte la stessa squadra? 

 necessari affinchè nessuno diriga 2 volte la stessa squadra?
Dovrebbero bastarne 30. Senza entrare in complicate elucubrazione, basta 
pensare che ogni arbitro potrà arbitrare 8 partite [p.e.: AB CD EF GH IJ KL 
MN OP] e se, come è inevitabile stilando il calendario, un paio di queste 
partite coincidono, la seconda potrà sempre essere arbitrata nel girone di 
ritorno.
Un saluto
Gianni
--
"Quello che accade, accade non tanto perché una minoranza vuole che accada,
quanto piuttosto perché la gran parte dei cittadini ha rinunciato alle sue
responsabilità e ha lasciato che le cose accadessero".  Antonio Gramsci
 

 ha scritto nel messaggio 
news:dhv_e.25815$9l.6...@twister1.libero.it...

Non è così banale e la tua risposta è sbagliata 

 Non è così banale e la tua risposta è sbagliata
Hai ragione. Infatti, dopo il primo ragionamento a naso, nel mettere giù uno 
schemino si incontrano subito delle difficoltà.
Non appena avrò un po' più di tempo, cercherò di buttare giù uno schemino 
valido.


 valido.
Non sono convinto che la soluzione di Giovanni sia sbagliata.
Questi design sono noti come "Room Square" (vedi ad es: 
http://mathworld.wolfram.com/RoomSquare.html
)
Non vedo perche' non dovrebbe esistere una tale configurazione
di ordine 15.
Per la loro costruzione sono noti diversi metodi come l'algoritmo di 
Hill-Climbing, e credo siano anche ricavabili dai sistemi di triple di 
Steiner. So che c'e' pure una certa corrispondenza con certe coppie di 
quadrati latini dello stesso ordine.

Non sono convinto che la soluzione di Giovanni sia sbagliata.
Purtroppo Zibilog ha crosspostato su ism: la` e` stato
dimostrato. D'altra parte separando l'andata e il ritorno
si vede al volo:
Arbitro 1: 0f 1e 2d 3c 4b 5a 69 78
Arbitro 2: 0e 1d 2c 3b 4a 59 68 7f
.............
-- 
Ciao, rez	||  -- GNU/Linux 2.4.25 su Slackware 9.1  ||

 
Mi sembra che questo non risolva completamente il problema.
Dovresti produrre un calendario dove 2 partite arbitrate dalla stessa 
persona non vengano giocate lo stesso giorno.
Come dicevo questi problemi di "block design" sono complicati.
Conosco un metodo per ottenere "Room Squares" di ordine n, partendo da 
due sistemi ortogonali di triple di Steiner sempre di ordine n.
Se vuoi posto un esempio semplice.
ciao

"rez" <r...@rez.localhost> ha scritto nel messaggio 
news:slrndjt5...@p900.mizar...

E perchè dici "purtroppo"? La domanda è lecita in entrambi i ng.
Quella presentata non è affatto una dimostrazione. Infatti, se è vero che è 
ogni arbitro può arbitrare al MASSIMO 8 partite diverse, bisogna dimostrare 
che con un tale assegnamento si possa compilare un calendario valido, in cui 
cioè in ogni giornata non compaia due volte una stessa squadra e in cui un 
arbitro non diriga due partite contemporaneamente.

Se vuoi posto un esempio semplice.
Ti ringrazio, ma non ne avrei il tempo oltre al fatto
che dev'essere parecchio complicatino: non capisco
neppure tutti questi termini che usi, o per lo meno non
mi sembra di conoscerli. Grazie della disponibilita`:-) 
Ps. Se pero` non ti costa postarlo magari e` pure
interessante conoscerlo.. ah la curiosita`!
Pps. Ma quell'elenco sui numeri l'hai aggiornato? perche'
ne avevo (quest'estate) messo da parte un paio che non
c'erano, pero' ora in questo momento non li trovo.



Ho visto il link di Dario, che illustra un quadrato di ordine 8.
Io ne avevo elaborato una versione leggermente diversa, realizzata parecchi
anni fa con i "ridotti derivati" per sistemi totocalcio, e che ho postato
sul crosspost di ISM.
Se le 16 squadre fossero suddivise in 2 gruppi da 8 (serie A1, squadre 
1...8,
serie A2, squadre 9...16), calendari e arbitraggi potrebbero essere
ottimizzati al valore teorico e nelle 14 giornate del campionato
(7 di andata e 7 di ritorno) basterebbero 14 arbitri (ciascuno arbitra
4 partite di andata (di una serie) e 4 partite di ritorno (dell'altra 
serie).
In questo modo non ci sarebbero però le 128 partite di incrocio fra le
squadre di A1 e quelle di A2. Non penso (almeno, io non ne sono capace)
che queste partite possano essere affidate a soli 16 arbitri.
Probabilmente, il problema si risolve al meglio con algoritmi genetici,
che non conosco.
Con una rozza integrazione carta e penna mi ci vogliono altri 22 arbitri,
per cui il totale risulterebbe di 36 arbitri, 6 in più del teorico.
Sono però portato a pensare si possa fare meglio, forse con 32.
Ciao, Nino 

 Sono però portato a pensare si possa fare meglio, forse con 32.
Ciao Nino, sicuramente 30 sono sufficienti.
Spiego qui l'unico metodo che conosco per generare questi calendari 
(Rooms Squares per i matematici).
Un sistema di triple di Steiner (STS)di ordine n, e' una selezione 
dall'insieme di tutte le possibili terne che si possono formare con gli 
n simboli, in modo che tutte le doppie siano presenti una ed una volta sola.
Questi STS esistono solo per ordini ==1 o 3 mod.6 = 3,7,9,13,15,19,21...
Prendiamo ad es. n=7.
Con 7 simboli si possono generare 7*6*5/3*2*1=35 terne. Fra queste e' 
possibile selezionarne un sottoinsieme di 7 in modo che ciascun simbolo 
incontri ciascun altro una sola volta. Ecco un es:
124
235
346
457
561
672
713
Come si vede, utilizzando un linguaggio da lotteria, tutti gli ambi sono 
presenti.
Da questo, poi se ne possono derivare molti altri applicando alcune 
trasformazioni scambiando ad es alcuni simboli fra loro oppure 
sostituendo ogni cifra con il proprio complemento ad 8. In questo caso 
ottiene:
764
653
542
431
327
216
175
Questi due STS hanno tra loro 2 caratteristiche particolari
a) Non hanno terne in comune.
b) Se due ambi nel primo set stanno con uno stesso terzo simbolo, allora 
gli stessi due ambi appaiono con 2 simboli differenti nel secondo set.
Un esempio chiarira' meglio questo punto;
Nel primo set troviamo 124 e 364 quindi i due ambi 1,2 e 3,6 hanno in 
comune nelle loro  terne lo stesso simbolo 4.
Nel secondo set, gli stessi due ambi stanno con simboli diversi, difatti 
li troviamo nelle terne 216 e 653.
Due sistemi con queste caratteristiche sono detti ortogonali.
E qui veniamo al punto: Avendo a disposizione 2 STS ortogonali di ordine 
n, possiamo generare facilmente il calendario cercato (Room Squares) con 
un metodo semplice ma ingegnoso, di ordine n+1. In questo caso n=8.
Costruisco un quadrato 8 x 8 numerando sia le righe che le colonne da 1 
a 8. Osservo la prima coppia nel primo STS che e' 12 il numero in comune 
nella stessa terna e' =4, cerco la stessa coppia 12 nel secondo STS e 
vedo che stanno nella terna assieme al 6. Quindi scrivo nella casella 
con coordinate (4,6) la coppia 12. Applico lo stesso procedimento a 
tutte le coppie di numeri procedendo con 24, sta con 1 nel primo STS e 
con 5 nel secondo, cosi' la coppia 24 ve scritta nella casella (1,5)
Procedendo cosi' con tutte le 21 coppie si ottiene:
-- -- -- 57 -- 34 62
73 -- -- -- 61 -- 45
56 14 -- -- -- 72 --
-- 67 25 -- -- -- 13
24 -- 71 36 -- -- --
-- 35 -- 12 47 -- --
-- -- 46 -- 23 51 --
Ora non resta che riempire la diagonale con le restanti 18, 28, ...78
18 -- -- 57 -- 34 62
73 28 -- -- 61 -- 45
56 14 38 -- -- 72 --
-- 67 25 48 -- -- 13
24 -- 71 36 58 -- --
-- 35 -- 12 47 68 --
-- -- 46 -- 23 51 78
Ottenendo cosi' un calendario di andata per otto squadre, le righe 
rappresentano le giornate e le colonne gli otto arbitri occorrenti.
Purtroppo io non ho sottomano una coppia di (STS)15 ortogonali, ma sono 
state pubblicate intere tavole di queste garantendo che la soluzione 
richiesta esiste.
Per chi ha voglia di lavorarci su, eccone uno. So che con opportune 
trasformazioni e' possibile da questo ottenere un proprio ortogonale, ma 
non conosco il metodo:
  1  2  3
  1  4  5
  1  6  7
  1  8  9
  1 10 11
  1 12 13
  1 14 15
  2  4  6
  2  5  7
  2  8 10
  2  9 11
  2 12 14
  2 13 15
  3  4  7
  3  5  6
  3  8 11
  3  9 10
  3 12 15
  3 13 14
  4  8 12
  4  9 13
  4 10 14
  4 11 15
  5  8 13
  5  9 12
  5 10 15
  5 11 14
  6  8 14
  6  9 15
  6 10 12
  6 11 13
  7  8 15
  7  9 14
  7 10 13
  7 11 12

 richiesta esiste.
Per quanto riguarda le terne su 15 numeri, sempre mutuando dal ridotto
perfetto di 15 doppie (n-1) col. 2048, ho elaborato una decina di
versioni da 35 terne, raccogliendole in coppie senza terne in comune;
purtroppo non sono riuscito a far rispettare la proprietà b) che hai
citato (se due ambi nel primo set stanno con uno stesso terzo simbolo,
allora gli stessi due ambi devono apparire con due simboli differenti
nel secondo set).
Si verificano quindi trasposizioni sovrapposte nella stessa casella e
l'impossibilità di realizzare un calendario di andata per 16 squadre,
con 15 giornate di gioco e 15 arbitri occorrenti.
Se, come dici, esiste la soluzione, penso sia necessario conoscere il
metodo, perchè a tentativi è praticamente impossibile realizzare una
coppia di STS 15 ortogonali.
Ciao, Nino