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
Non si capisce cosa sia lo scontro diretto.
Penso intenda che la squadra A possa giocare 2 volte nella stessa fascia con la squadra B oltre alla partita A-B
"hydro":
Non si capisce cosa sia lo scontro diretto.
È la partita A - B nel caso della squadra A
Ciao, quando dici
con "calendario" ti riferisci all'insieme di giornate e fasce orarie o solo alle fasce orarie?
Chiedo perché ho l'impressione che il problema sia indipendente dalle giornate.
"Al-Mat":
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?
con "calendario" ti riferisci all'insieme di giornate e fasce orarie o solo alle fasce orarie?
Chiedo perché ho l'impressione che il problema sia indipendente dalle giornate.
Con calendario intendo l'insieme delle 11 giornate, di cui ogni giornata è composta da 6 partite distribuite in 3 fasce orarie
Ma, tralasciando per il momento le fasce orarie, numericamente quanti sarebbero i possibili diversi calendari in un girone all'italiana di sola andata composto da un numero pari $n$ di partecipanti (dove l'ordine degli $n-1$ turni, l'ordine delle $n/2$ partite all'interno del singolo turno e l'ordine dei due sfidanti all'interno della singola partita, non determinano la diversità tra due calendari)?
Penso che determinarlo potrebbe essere un buon primo passo!
Penso che determinarlo potrebbe essere un buon primo passo!
"utente__medio":
Ma, tralasciando per il momento le fasce orarie, numericamente quanti sarebbero i possibili diversi calendari in un girone all'italiana di sola andata composto da un numero pari $n$ di partecipanti (dove l'ordine degli $n-1$ turni, l'ordine delle $n/2$ partite all'interno del singolo turno e l'ordine dei due sfidanti all'interno della singola partita, non determinano la diversità tra due calendari)?
Penso che determinarlo potrebbe essere un buon primo passo!
Ci stavo pensando anch'io. Non sembra un problema banale, lo si può vedere così: scrivo una tabella quadrata $n\times n$ dove le $n$ righe e le $n$ colonne sono i partecipanti $x_1,\ldots,x_n$. Dare un calendario significa compiere la seguente operazione: sulla diagonale della tabella metto tutti $0$, perchè un partecipante non può incontrare sè stesso, su ogni riga ed ogni colonna devono esserci tutti i numeri $1,\ldots,n-1$, che rappresentano le giornate, in modo che la tabella sia simmetrica. Questi però sono i calendari ordinati, mentre ad op non interessa l'ordine delle partite. Quindi possiamo assumere che la prima riga abbia i numeri $0,1,2,\ldots,n-1$ in ordine, il che equivale ad ordinare il calendario in modo che $x_1$ affronti $x_i$ alla giornata $i-1$. In altre parole, il numero di calendari è il numero di quadrati latini simmetrici rispetto alla diagonale, tali che sulla diagonale appaia sempre lo stesso numero e tali che la prima riga sia $0,1,\ldots,n-1$ in quest'ordine. La formula per il numero di quadrati latini di ordine $n$ è già piuttosto complicata, il che non promette bene...
Dato 1 calendario qualsiasi, gli altri sono al massimo tutte le permutazioni di 12 squadre. IHMO
Quindi 1 solo calendario li riassume tutti.
Detto questo, solo alcune delle permutazioni possibili soddisfano le richieste.
Quindi 1 solo calendario li riassume tutti.
Detto questo, solo alcune delle permutazioni possibili soddisfano le richieste.
"hydro":
Ci stavo pensando anch'io. Non sembra un problema banale, lo si può vedere così: scrivo una tabella quadrata...
Avevo impostato anche io uno schema simile soffermandomi sulla parte superiore alla diagonale (con il vincolo che ogni valore da $1$ a $n-1$ deve ripetersi esattamente $n/2$ volte, ma mai nella stessa riga o colonna), ma effettivamente non è semplice...
"hydro":
il numero di calendari è il numero di quadrati latini simmetrici rispetto alla diagonale, tali che sulla diagonale appaia sempre lo stesso numero e tali che la prima riga sia $0,1,...,n−1$ in quest'ordine.
Fissare la prima riga è sufficiente ad escludere/ignorare l'ordine delle partite, o meglio, delle giornate?
"axpgn":
Dato 1 calendario qualsiasi, gli altri sono al massimo tutte le permutazioni di 12 squadre. IHMO
Quindi 1 solo calendario li riassume tutti.
Lo avevo pensato anche io, per questo dicevo
"utente__medio":
ho l'impressione che il problema sia indipendente dalle giornate.
"axpgn":
Detto questo, solo alcune delle permutazioni possibili soddisfano le richieste...
Premesso che non ho testato l'immagine che hai postato, stai dicendo che la risposta alla domanda dell'OP è affermativa?
In ogni caso appena ho tempo provo ad implementare qualcosa pure io!
"utente__medio":
Premesso che non ho testato l'immagine che hai postato, stai dicendo che la risposta alla domanda dell'OP è affermativa?
No, intendo dire che basta quel calendario per averli tutti, è sufficiente (
) permutare le squadre; ad ogni permutazione si controlla se il calendario rispetta i criteri richiesti: se no lo si scarta e si passa alla permutazione successiva; se sì allora si può fare
.
Sulle matrici non saprei cosa dire, non ho approfondito quanto detto e comunque avrei capito poco
Se fossi in grado di programmare seriamente io farei così ...
Ogni calendario è formato da 132 record costruiti in questo modo:
1^ e 2^ cifra -> codice squadra (da 01 a 12)
3^ e 4^ cifra -> codice giornata (da 01 a 11)
5^ cifra -> codice fascia (1, 2, 30
6^ cifra -> codice partita (1, 2)
Poi per ogni calendario confronterei ogni squadra verso le altre, una alla volta, passando al calendario successivo al primo "errore"
Sono solo $12!$ calendari
($479.001.600$)
@sellacollesella
Io penso tu sia sulla buona strada ovvero non troverai niente
Se fossi in grado di programmare seriamente io farei così ...
Ogni calendario è formato da 132 record costruiti in questo modo:
1^ e 2^ cifra -> codice squadra (da 01 a 12)
3^ e 4^ cifra -> codice giornata (da 01 a 11)
5^ cifra -> codice fascia (1, 2, 30
6^ cifra -> codice partita (1, 2)
Poi per ogni calendario confronterei ogni squadra verso le altre, una alla volta, passando al calendario successivo al primo "errore"
Sono solo $12!$ calendari
($479.001.600$)@sellacollesella
Io penso tu sia sulla buona strada ovvero non troverai niente
.
"sellacollesella":
ho considerato una permutazione casuale delle dodici squadre partecipanti al torneo, ho eseguito le rispettive sostituzioni nel calendario di axpgn e ho rieseguito tale test. Risultato: nulla di fatto, dato che la matrice $A′$ così ottenuta non è altro che una permutazione degli elementi non diagonali di $A$. Pertanto, ho ripetuto tali operazioni qualche decina di volte e poi mi sono fermato, inutile insistere.
Questo sembra confermare quanto detto da me e axpgn in precedenza:
"utente__medio":
con "calendario" ti riferisci all'insieme di giornate e fasce orarie o solo alle fasce orarie?
Chiedo perché ho l'impressione che il problema sia indipendente dalle giornate.
"axpgn":
Dato 1 calendario qualsiasi, gli altri sono al massimo tutte le permutazioni di 12 squadre. IHMO
Quindi 1 solo calendario li riassume tutti.
"sellacollesella":
Per tal motivo, non ho fatto altro che ripetere le medesime operazioni, ma permutando casualmente anche le partite nelle tre fasce orarie di ciascuna giornata del torneo. Risultato: ora le matrici $A′$ cambiano e ce ne sono alcune più lontane, altre più vicine, rispetto a $B$, ma dopo milioni di iterazioni non sono riuscito a scendere sotto a quota $100$.
Effettivamente, essendo secondo me il problema indipendente dal calendario in termini di giornate, ma dipendente solo dal calendario in termini di fasce orarie, è proprio quello che mi sarei aspettato.
A questo punto, per tagliare la testa al toro, andrebbero testati tutti i diversi calendari in termini di fasce orarie (relativi ad uno stesso generico calendario in termini di giornate), ma per farlo bisognerebbe innanzitutto calcolarne il numero preciso $m$.
Io partirei dai possibili diversi raggruppamenti delle $6$ partite di una generica giornata in $3$ gruppi da $2$ elementi ciascuno, che dovrebbero essere
$((6),(2))*((4),(2))=90$
Quindi in definitiva, considerando le $11$ giornate, avremo $m=90^11$, che è peggio del $12!$ di @axpgn, ma meglio del $12!*33!$ di @sellacollesella. Chi ha ragione?
Non vedo perché i calendari debbano essere più di $12!$.
Per esempio, tieni fissa la squadra a e permuti tutte le altre, ottieni tutti i calendari possibili con a in quella posizione.
Poi sposti la a di un posto (diciamo così) e fai lo stesso, ottieni tutti i calendari possibili con a in quest'altra posizione e così via.
"Mescolare" le fasce non cambia niente a mio avviso perché non fai altro che riordinare le righe di una matrice.
Questo l'avevo capito, il mio dubbio (superficiale non avendo approfondito la questione) è se la matrice così fatta rappresenti effettivamente tutti i casi reali.
Peraltro, cosa ne pensi del modo in cui procederei io (se ne fossi capace ) ?
Per esempio, tieni fissa la squadra a e permuti tutte le altre, ottieni tutti i calendari possibili con a in quella posizione.
Poi sposti la a di un posto (diciamo così) e fai lo stesso, ottieni tutti i calendari possibili con a in quest'altra posizione e così via.
"Mescolare" le fasce non cambia niente a mio avviso perché non fai altro che riordinare le righe di una matrice.
"sellacollesella":
Non ci credo!
Questo l'avevo capito, il mio dubbio (superficiale non avendo approfondito la questione) è se la matrice così fatta rappresenti effettivamente tutti i casi reali.
Peraltro, cosa ne pensi del modo in cui procederei io (se ne fossi capace
) ?
@utente_medio
Non è sufficiente, a parere mio, testare "solo" le fasce.
Prendi per esempio il mio calendario e prendi solo la prima giornata; facendo tutte le possibili permutazioni ottieni tutte le possibili "prime" giornate ma poi devi andare a vedere tutte le altre giornate come si sposano con questa e tra di loro; d'altronde il vincolo che ha messo l'OP è su TUTTO il campionato in quanto ogni squadra non deve giocare più di 2 volte nella stessa fascia di un'altra e questo lo vedi SOLO su tutto il campionato.
@selalcollesella
Quanti sono i diversi calendari possibili in generale?
Per diversi intendo NON ricavabili uno dall'altro solo permutando le squadre (e l'ordine delle giornate e delle fasce e sq-home vs sg-away).
Esistono veramente calendari diversi ignorando quanto ho detto sopra?
Non è sufficiente, a parere mio, testare "solo" le fasce.
Prendi per esempio il mio calendario e prendi solo la prima giornata; facendo tutte le possibili permutazioni ottieni tutte le possibili "prime" giornate ma poi devi andare a vedere tutte le altre giornate come si sposano con questa e tra di loro; d'altronde il vincolo che ha messo l'OP è su TUTTO il campionato in quanto ogni squadra non deve giocare più di 2 volte nella stessa fascia di un'altra e questo lo vedi SOLO su tutto il campionato.
@selalcollesella
Quanti sono i diversi calendari possibili in generale?
Per diversi intendo NON ricavabili uno dall'altro solo permutando le squadre (e l'ordine delle giornate e delle fasce e sq-home vs sg-away).
Esistono veramente calendari diversi ignorando quanto ho detto sopra?
.
Mica solo il tuo computer
Dunque, riflettendo un pochino ... permutando le squadre di UN calendario, non cambia niente perché non si fa altro che cambiare il nome alla prima squadra, alla seconda, ecc. ma i rapporti tra loro rimangono gli stessi; ergo è inutile permutare le squadre tra loro e basta e avanza un calendario come base (risparmiamo $12!$ )
Permutare le partite tra le fasce significa avere $6*5*4*3=360$ combinazioni a giornata quindi in totale dovrebbero essere $360^11$ le combinazioni da testare?
Se così fosse allora dovresti solo usare un computer più potente
Dunque, riflettendo un pochino ... permutando le squadre di UN calendario, non cambia niente perché non si fa altro che cambiare il nome alla prima squadra, alla seconda, ecc. ma i rapporti tra loro rimangono gli stessi; ergo è inutile permutare le squadre tra loro e basta e avanza un calendario come base (risparmiamo $12!$
)Permutare le partite tra le fasce significa avere $6*5*4*3=360$ combinazioni a giornata quindi in totale dovrebbero essere $360^11$ le combinazioni da testare?
Se così fosse allora dovresti solo usare un computer più potente
No, sono meno a giornata ... dovrebbero essere solo $90=15*6$
E se invece di cercarlo provassimo a costruirlo il calendario che vuole OP?
La prima giornata non è altro che ab+cd|ef+gh|ij+kl, il programma è sicuramente più complesso ma forse occorrerebbe meno tempo per giungere ad una conclusione ...
La prima giornata non è altro che ab+cd|ef+gh|ij+kl, il programma è sicuramente più complesso ma forse occorrerebbe meno tempo per giungere ad una conclusione ...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo