Il calendario Impossibile, un anno dopo
Salve a tutti;
Ripubblico un dilemma che ormai mi perseguita da diversi anni, l'anno scorso non ebbi esito positivo, anche perché forse spiegai in maniera difficile il problema. Questa volta cerco di essere più chiaro.
Il problema è il seguente:
Ci sono 12 squadre: (A, B, C, D,....., L)
Le 12 squadre devono affrontarsi in un girone all'italiana di sola andata (quindi 11 giornate)
Ogni giornata di campionato è composto da 3 fasce orarie in cui giocare (15:00, 18:00, 21:00), ad ogni fascia oraria si disputano 2 partite.
DOMANDA
E' possibile la creazione di un calendario in cui, oltre allo scontro diretto, ogni squadra gioca esattamente per 2 volte nella stessa fascia oraria con tutte le altre squadre?
Esempio per essere più chiaro
Giornata 1
Ore 15:00
A - B; C - D;
Ore 18:00
E - F; G - H;
Ore 21:00
I - J; K - L.
In questo esempio la squadra A gioca contro B (e non la deve più affrontare in campionato) e gioca nella stessa fascia oraria con C e D, quindi con queste ultime 2 squadre può giocarci soltanto un'altra volta nella stessa fascia oraria (escluso lo scontro diretto).
Credo di essere stato chiaro ed esaustivo e spero di incontrare qualche buon anima che risolva una volta per tutte questo problema (o al limite mi dimostra la sua infattibilità).
Ripubblico un dilemma che ormai mi perseguita da diversi anni, l'anno scorso non ebbi esito positivo, anche perché forse spiegai in maniera difficile il problema. Questa volta cerco di essere più chiaro.
Il problema è il seguente:
Ci sono 12 squadre: (A, B, C, D,....., L)
Le 12 squadre devono affrontarsi in un girone all'italiana di sola andata (quindi 11 giornate)
Ogni giornata di campionato è composto da 3 fasce orarie in cui giocare (15:00, 18:00, 21:00), ad ogni fascia oraria si disputano 2 partite.
DOMANDA
E' possibile la creazione di un calendario in cui, oltre allo scontro diretto, ogni squadra gioca esattamente per 2 volte nella stessa fascia oraria con tutte le altre squadre?
Esempio per essere più chiaro
Giornata 1
Ore 15:00
A - B; C - D;
Ore 18:00
E - F; G - H;
Ore 21:00
I - J; K - L.
In questo esempio la squadra A gioca contro B (e non la deve più affrontare in campionato) e gioca nella stessa fascia oraria con C e D, quindi con queste ultime 2 squadre può giocarci soltanto un'altra volta nella stessa fascia oraria (escluso lo scontro diretto).
Credo di essere stato chiaro ed esaustivo e spero di incontrare qualche buon anima che risolva una volta per tutte questo problema (o al limite mi dimostra la sua infattibilità).
Risposte
"utente__medio":
Non dovrebbe essere sempre massimo $ 2 $ volte in contemporanea (escluso lo scontro diretto)?
Ho pensato che andasse ridotto anche quel vincolo altrimenti troppo restrittivo (e di fatto tu lo confermi)
Ma il numero di squadre che giocano in contemporanea ad una generica squadra nel corso delle varie giornate è sempre lo stesso, ossia $2*(8-1)=14$, quindi $1$ sola volta in contemporanea non ha senso come vincolo; infatti, ridistribuendo equamente quelle $14$ partite tra le altre $7$ squadre, si ottiene appunto $2$ partite in contemporanea.
Non necessariamente ci sarebbe una distribuzione equa, è solo uno dei casi possibili; comunque era solo per provare un caso "ridotto", vedere quanto costava in termini di risorse e poi eventualmente ampliarlo con aggiustamenti progressivi e mirati, non casuali al fine di riuscire ad ottenere un risultato al problema originale, positivo o negativo che fosse.
"axpgn":
Non necessariamente ci sarebbe una distribuzione equa, è solo uno dei casi possibili;
Quello che intendo è che fissare massimo $1$ partita in contemporanea non ha senso come vincolo, in quanto una generica squadra già alla sua quarta partita (delle $7$ totali) avrà giocato in contemporanea con un'altra squadra almeno $2$ volte.
Ok, ma il punto non era quello (i vincoli che ho messo non li ho pensati più di tanto); come ho scritto prima l'idea è quella di provare qualcosa di più "piccolo" per vedere se potesse esse utile.
.
@sellacollesella
Penso che l'OP dovrebbe almeno pagarti da bere ...
Penso che l'OP dovrebbe almeno pagarti da bere ...
Complimenti a sellacollesella, e a tutti, per questa soluzione, perché poi c'è stato un lavoro di squadra ed è bello vedere, come in questo thread, l'intelligenza di tutti volare! 
Grande! 
Però bisognerebbe capire come ci siano arrivati...
A quali permutazioni ti riferisci?
Però bisognerebbe capire come ci siano arrivati...
"sellacollesella":
Così, su due piedi e pure su due gambe, non credo che abbiano testato le $11! =39916800$ permutazioni possibili.
A quali permutazioni ti riferisci?
.
"sellacollesella":
Oggi non avevo proprio la testa per capire la spiegazione, prometto di farlo prossimamente.
Figurati, fai con calma!
Nel frattempo però volevo esporre un dubbio.
Eravamo tutti d'accordo sul fatto che fosse sufficiente fare riferimento ad un generico calendario per poi considerare le $90^(11)$ combinazioni ottenibili scambiando le partite tra le fasce all'interno di una stessa giornata, giusto?
A tal proposito consideriamo il seguente generico calendario:
GIORNATA 0: 0-11 1-10 2- 9 3- 8 4- 7 5- 6 GIORNATA 1: 1-11 2- 0 3-10 4- 9 5- 8 6- 7 GIORNATA 2: 2-11 3- 1 4- 0 5-10 6- 9 7- 8 GIORNATA 3: 3-11 4- 2 5- 1 6- 0 7-10 8- 9 GIORNATA 4: 4-11 5- 3 6- 2 7- 1 8- 0 9-10 GIORNATA 5: 5-11 6- 4 7- 3 8- 2 9- 1 10- 0 GIORNATA 6: 6-11 7- 5 8- 4 9- 3 10- 2 0- 1 GIORNATA 7: 7-11 8- 6 9- 5 10- 4 0- 3 1- 2 GIORNATA 8: 8-11 9- 7 10- 6 0- 5 1- 4 2- 3 GIORNATA 9: 9-11 10- 8 0- 7 1- 6 2- 5 3- 4 GIORNATA 10: 10-11 0- 9 1- 8 2- 7 3- 6 4- 5
Se la soluzione al problema è unica ed è questa
"sellacollesella":
[size=120]\[ \color{red}{\boxed{((8,11),\,(4,7)),\quad((9,10),\,(1,3)),\quad((0,5),\,(2,6))}} \][/size]
allora avoglia a scambiare partite all'interno di una stessa giornata... il suddetto calendario non potrà mai trasformarsi nella "soluzione". Che ne pensate? Mi sono perso qualcosa?
.
"sellacollesella":
[quote="utente__medio"]
Eravamo tutti d'accordo sul fatto che fosse sufficiente fare riferimento ad un generico calendario per poi considerare le $ 90^(11) $ combinazioni ottenibili scambiando le partite tra le fasce all'interno di una stessa giornata, giusto?
Eh già, per \( n=8 \) mi pare avessimo pure concluso con zero tituli; invece, ho trovato sei tituli.
[...]
per \( n=8 \) la faccenda non è banale, vi sono ben sei "giornate 0" che generano calendari validi: [size=120]\[ \color{blue}{\boxed{\begin{aligned} &((0,7),\,(1,3)),\quad((2,6),\,(4,5))\\ &((0,7),\,(1,5)),\quad((2,3),\,(4,6))\\ &((0,7),\,(2,3)),\quad((1,5),\,(4,6))\\ &((0,7),\,(2,6)),\quad((1,3),\,(4,5))\\ &((0,7),\,(4,5)),\quad((1,3),\,(2,6))\\ &((0,7),\,(4,6)),\quad((1,5),\,(2,3))\\ \end{aligned}}} \][/size][/quote]
Per $n=8$ avevo fatto riferimento al seguente calendario:
GIORNATA 0: 0-7 1-6 2-5 3-4 GIORNATA 1: 1-7 2-0 3-6 4-5 GIORNATA 2: 2-7 3-1 4-0 5-6 GIORNATA 3: 3-7 4-2 5-1 6-0 GIORNATA 4: 4-7 5-3 6-2 0-1 GIORNATA 5: 5-7 6-4 0-3 1-2 GIORNATA 6: 6-7 0-5 1-4 2-3
Ma anche qui avoglia a scambiare le partite all'interno delle varie giornate... le sei soluzioni che hai postato non sarebbero mai potute essere trovate!
Morale della favola: a quanto pare non basta un calendario per domarli tutti!
Sul come e sul perché, al momento non saprei...
"sellacollesella":
Infatti, ho scritto un codice che, perlomeno teoricamente, vale per ogni \( n=4,8,12,16\dots \)
Dovrei leggermelo e approfondire la questione con calma.
.
"sellacollesella":
In particolare, nel primo blocco ho implementato i seguenti passi:
[*:2n8bo9cj] in \(a_0\) ho elencato gli interi da \(0\) ad \(n-1\);
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_1\) ho elencato le combinazioni semplici di classe \(2\) di \(a_0\);
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_2\) ho elencato le combinazioni semplici di classe \(2\) di \(a_1\);
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_3\) ho selezionato i raggruppamenti di \(a_2\) senza numeri ripetuti;
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_4\) ho elencato le combinazioni semplici di classe \(n/4\) di \(a_3\);
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_5\) ho selezionato i raggruppamenti di \(a_4\) senza numeri ripetuti;
[/*:m:2n8bo9cj]
[*:2n8bo9cj] in \(a_6\) ho selezionato i raggruppamenti di \(a_5\) con \(n-1\) nella posizione fissata;[/*:m:2n8bo9cj][/list:u:2n8bo9cj]
che, ad esempio, per \(n=8\) comporta: \[
||a_0||=8,\qquad||a_1||=28,\qquad||a_2||=378,\qquad||a_3||=210,\\||a_4||=21945,\qquad||a_5||=315,\qquad||a_6||=45
\] dove è evidente che il cono di bottiglia sia \(a_4\), che è esattamente dove si pianta da \(n=12\) in poi!
Sto cercando di implementare un modo efficiente di generare le distinte "giornate 0" da cui ricavare i calendari da testare; in particolare ipotizzo che due "giornate 0" distinte debbano essere indipendenti dall'ordine delle fasce orarie, dall'ordine delle partite all'interno delle singole fasce orarie e dall'ordine delle squadre all'interno delle singole partite.
Per esempio, applicando il tuo procedimento sopra riportato a $n=8$, quante distinte "giornate 0" ti ritrovi? Sono per caso $630$?
.
Dovreste metter su un business
.
"axpgn":
Dovreste metter su un business
Per il momento il nostro primo e unico "cliente" si è dato alla macchia!
"sellacollesella":
Se riesci ad andare oltre, sono interessato!
Forse ci sono riuscito, ma vorrei fare ancora qualche test.
Per curiosità, come passi dall'elenco di tutte le possibili $315$ giornate ai $45$ calendari?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo