Calendario incontri di gruppo
Salve a tutti gli appassionati di questo sito
da un pò sbatto con un problema che ritengo/spero si possa risolvere facilmente con l'aiuto di qualche formula o algoritmo matematico.
Devo scrivere il calendario per fare incontrare tra di loro 21 persone suddivise in 5 gruppi.
Ogni gruppo quindi sarà formato da 4 persone (tranne uno che sarà di 5).
L'obiettivo è fare ruotare le persone in modo che possano incontrare tutti nel minor tempo possibile.
Ogni gruppo ha 1 persona-guida che non ruota, ma rimane fissa nel gruppo
(questo in effetti è una condizione che potrebbe anche essere superata).
Chiaro il problema? Cosa suggerite?
grazie
Pino
p.s. chiedo venia agli amministratori se ho sbagliato sezione spostatemi tranquillamente (tanto a furia di sbattere con questo problema sono già un pò "spostato"
da un pò sbatto con un problema che ritengo/spero si possa risolvere facilmente con l'aiuto di qualche formula o algoritmo matematico.
Devo scrivere il calendario per fare incontrare tra di loro 21 persone suddivise in 5 gruppi.
Ogni gruppo quindi sarà formato da 4 persone (tranne uno che sarà di 5).
L'obiettivo è fare ruotare le persone in modo che possano incontrare tutti nel minor tempo possibile.
Ogni gruppo ha 1 persona-guida che non ruota, ma rimane fissa nel gruppo
(questo in effetti è una condizione che potrebbe anche essere superata).
Chiaro il problema? Cosa suggerite?
grazie
Pino
p.s. chiedo venia agli amministratori se ho sbagliato sezione spostatemi tranquillamente (tanto a furia di sbattere con questo problema sono già un pò "spostato"
Risposte
Non ti arrendere mai!!!!!!!!!!!!!! 
La sezione è perfetta, vedrai che ti aiuteranno!!!!!!!
A prima vista, ho pensato ad un problema che può essere "ridotto" ad un problema di flusso massimo. A questo scopo, è necessario costruire un grafo (bipartito probabilmente) a partire dai dati di input.
Dovresti approfondire argomenti di Ricerca Locale.
(Ma aspetta qualcuno che ne sa di più del sottoscritto
)
La sezione è perfetta, vedrai che ti aiuteranno!!!!!!!
A prima vista, ho pensato ad un problema che può essere "ridotto" ad un problema di flusso massimo. A questo scopo, è necessario costruire un grafo (bipartito probabilmente) a partire dai dati di input.
Dovresti approfondire argomenti di Ricerca Locale.
(Ma aspetta qualcuno che ne sa di più del sottoscritto
)
purtroppo NON sono un matematico. Sono approdato a questo sito dopo varie ricerche per risolvere il problema.
Quindi, nell'attesa che qualcuno mi offra un suggerimento e magari per continuare la ricerca, ti chiedo:
cos'è un "flusso massimo"?
e cosa intenti per "approfondire argomenti di Ricerca Locale"?
grazie
Quindi, nell'attesa che qualcuno mi offra un suggerimento e magari per continuare la ricerca, ti chiedo:
cos'è un "flusso massimo"?
e cosa intenti per "approfondire argomenti di Ricerca Locale"?
grazie
A me il tuo problema non è per niente chiaro ... se devi "semplicemente" far incontrare tutti con tutti allora ti basta un calendario come quello del campionato di calcio ... vai su un sito di ricerca e scrivi "calendario girone a 21 squadre" e trovi un generatore per il tuo ...
Cordialmente, Alex
Cordialmente, Alex
no Alex penso che il calendario delle partite di calcio non vada bene (ho visto parecchi esempi)
perchè i "gruppi/squadre" sono a due a due, mentre nel mio caso i gruppi sono formati da 4/5 persone
per cui la rotazione è mooolto più complessa.
grazie comunque
perchè i "gruppi/squadre" sono a due a due, mentre nel mio caso i gruppi sono formati da 4/5 persone
per cui la rotazione è mooolto più complessa.
grazie comunque
T'ho detto che il tuo problema non mi è chiaro ... se lo spiegassi meglio ...
Come si devono incontrare queste persone? Per esempio come dovrebbe essere la prima "giornata? Dettaglia ...
Cordialmente, Alex
Come si devono incontrare queste persone? Per esempio come dovrebbe essere la prima "giornata? Dettaglia ...
Cordialmente, Alex
Faccio un piccolo esempio di come dovrebbe essere il calendario.
Abbiamo 21 persone che chiameremo 1, 2, 3, 4... 21.
Ogni mese queste 21 persone si incontreranno suddivise in cinque gruppi formate da 4/5 persone.
Ogni gruppo ha una testa di serie che non cambia (una guida)
quindi il gruppo A avrà sempre la persona 1, il gruppo B la persona 2, e così via.
IPOTESI
Calendario del primo incontro:
Gruppo A formato dalle persone: 1, 6, 11, 16
Gruppo B formato dalle persone: 2, 7, 12, 17
Gruppo C formato dalle persone: 3, 8, 13, 18
Gruppo D formato dalle persone: 4, 9, 14, 19
Gruppo E formato dalle persone: 5, 10, 15, 20, 21
Calendario del secondo incontro:
Gruppo A formato dalle persone: 1, 7, 13, 19, 21
Gruppo B formato dalle persone: 2, 8, 14, 20
Gruppo C formato dalle persone: 3, 6, 9, 15
Gruppo D formato dalle persone: 4, 10, 12, 16
Gruppo E formato dalle persone: 5, 11, 17, 18
Calendario del terzo incontro:
Gruppo A formato dalle persone: 1, 8, 15, 6
Gruppo B formato dalle persone: 2, 9, 16, 7
Gruppo C formato dalle persone: 3, 10, 17, 20
Gruppo D formato dalle persone: 4, 11, 18, 14, 21
Gruppo E formato dalle persone: 5, 12, 13, 19
...Altri Incontri da sviluppare...
Come si può osservare già dal terzo incontro alcune persone di incontrano nuovamente:
nel Gruppo A la 1 con la 6 si erano incontrate nel primo incontro e la 15 con la 6 che si erano già incontrate nel secondo incontro
e nel Gruppo D la 4 con la 14 che si erano incontrate nel primo incontro.
La difficoltà che ho appunto è che facendolo a mano mi imbatto in due difficoltà:
quella che le persone si incontrano nuovamente,
ma quella più importante che alcuni non si incontrano.
Per questo motivo mi chiedevo se la matematica poteva venirmi incontro per minimizzare queste ricorrenze e comunque soddisfare che tutti incontrino tutti.
Spero di avere chiarito meglio il mio problema
e comunque grazie per l'interessamento.
Abbiamo 21 persone che chiameremo 1, 2, 3, 4... 21.
Ogni mese queste 21 persone si incontreranno suddivise in cinque gruppi formate da 4/5 persone.
Ogni gruppo ha una testa di serie che non cambia (una guida)
quindi il gruppo A avrà sempre la persona 1, il gruppo B la persona 2, e così via.
IPOTESI
Calendario del primo incontro:
Gruppo A formato dalle persone: 1, 6, 11, 16
Gruppo B formato dalle persone: 2, 7, 12, 17
Gruppo C formato dalle persone: 3, 8, 13, 18
Gruppo D formato dalle persone: 4, 9, 14, 19
Gruppo E formato dalle persone: 5, 10, 15, 20, 21
Calendario del secondo incontro:
Gruppo A formato dalle persone: 1, 7, 13, 19, 21
Gruppo B formato dalle persone: 2, 8, 14, 20
Gruppo C formato dalle persone: 3, 6, 9, 15
Gruppo D formato dalle persone: 4, 10, 12, 16
Gruppo E formato dalle persone: 5, 11, 17, 18
Calendario del terzo incontro:
Gruppo A formato dalle persone: 1, 8, 15, 6
Gruppo B formato dalle persone: 2, 9, 16, 7
Gruppo C formato dalle persone: 3, 10, 17, 20
Gruppo D formato dalle persone: 4, 11, 18, 14, 21
Gruppo E formato dalle persone: 5, 12, 13, 19
...Altri Incontri da sviluppare...
Come si può osservare già dal terzo incontro alcune persone di incontrano nuovamente:
nel Gruppo A la 1 con la 6 si erano incontrate nel primo incontro e la 15 con la 6 che si erano già incontrate nel secondo incontro
e nel Gruppo D la 4 con la 14 che si erano incontrate nel primo incontro.
La difficoltà che ho appunto è che facendolo a mano mi imbatto in due difficoltà:
quella che le persone si incontrano nuovamente,
ma quella più importante che alcuni non si incontrano.
Per questo motivo mi chiedevo se la matematica poteva venirmi incontro per minimizzare queste ricorrenze e comunque soddisfare che tutti incontrino tutti.
Spero di avere chiarito meglio il mio problema
e comunque grazie per l'interessamento.
rivedendo il terzo incontro noto che ci sono più ricorrenze, ma spero che il concetto sia comunque chiaro
Premessa: questo problema non c'entra con l'informatica, la sezione giusta sarebbe quella di algebra nella quale ti avrebbero già dato risposta ...
Poi, dato che sono un po' duro non ho ancora capito bene però mi sembra che il tuo non sia un problema di incontri ma di RAGGRUPPAMENTI, in pratica trovare QUANTE e soprattutto QUALI combinazioni di 4/5 elementi da un insieme di 21 ... tanto per cominciare è da capire se esiste una possibilità del genere cioè che nessuno si incontri due volte ...
Fatti spostare il problema in algebra da qualche moderatore e le speranze aumenteranno ...
Cordialmente, Alex
Poi, dato che sono un po' duro non ho ancora capito bene però mi sembra che il tuo non sia un problema di incontri ma di RAGGRUPPAMENTI, in pratica trovare QUANTE e soprattutto QUALI combinazioni di 4/5 elementi da un insieme di 21 ... tanto per cominciare è da capire se esiste una possibilità del genere cioè che nessuno si incontri due volte ...
Fatti spostare il problema in algebra da qualche moderatore e le speranze aumenteranno ...
Cordialmente, Alex
Forse però ho trovato una soluzione ma con $20$ persone però ...
I capigruppo (fissi) sono $1,2,3,4,5$ mentre le altre $15$ persone sono $a,b,c,d,e,f,g,h,i,j,k,l,m,n,o$.
Allora avremo ...
1° giorno: $1abc\ \ \ 2def\ \ \ 3ghi\ \ \ 4jkl\ \ \ 5mno$
2° giorno: $1adg\ \ \ 2bkn\ \ \ 3col\ \ \ 4jei\ \ \ 5mhf$
3° giorno: $1ajm\ \ \ 2beh\ \ \ 3cfi\ \ \ 4dko\ \ \ 5gnl$
4° giorno: $1aek\ \ \ 2cgm\ \ \ 3boi\ \ \ 4dhl\ \ \ 5jnf$
5° giorno: $1ahn\ \ \ 2cdj\ \ \ 3bfl\ \ \ 4g\e\o\ \ \ 5mki$
6° giorno: $1afo\ \ \ 2bgj\ \ \ 3ckh\ \ \ 4dni\ \ \ 5mel$
7° giorno: $1ail\ \ \ 2bdm\ \ \ 3cen\ \ \ 4gkf\ \ \ 5jho$
Dovrebbe andar bene, verifica tu ...
Il $21°$ non ci sta, mi spiace ...
Cordialmente, Alex
I capigruppo (fissi) sono $1,2,3,4,5$ mentre le altre $15$ persone sono $a,b,c,d,e,f,g,h,i,j,k,l,m,n,o$.
Allora avremo ...
1° giorno: $1abc\ \ \ 2def\ \ \ 3ghi\ \ \ 4jkl\ \ \ 5mno$
2° giorno: $1adg\ \ \ 2bkn\ \ \ 3col\ \ \ 4jei\ \ \ 5mhf$
3° giorno: $1ajm\ \ \ 2beh\ \ \ 3cfi\ \ \ 4dko\ \ \ 5gnl$
4° giorno: $1aek\ \ \ 2cgm\ \ \ 3boi\ \ \ 4dhl\ \ \ 5jnf$
5° giorno: $1ahn\ \ \ 2cdj\ \ \ 3bfl\ \ \ 4g\e\o\ \ \ 5mki$
6° giorno: $1afo\ \ \ 2bgj\ \ \ 3ckh\ \ \ 4dni\ \ \ 5mel$
7° giorno: $1ail\ \ \ 2bdm\ \ \ 3cen\ \ \ 4gkf\ \ \ 5jho$
Dovrebbe andar bene, verifica tu ...
Il $21°$ non ci sta, mi spiace ...
Cordialmente, Alex
è una ipotesi...
però noto subito che la persona "a" è sempre nel gruppo "1" e quindi con la persona "1" mentre è opportuno che ruoti
analogamente "d" e "d" e "2" si incontrano 3 volte
"c" e "3"
"i" e "3"
...
insomma penso che anche tu sei andato a sbattere sulla mia stessa difficoltà
Penso, immagino, spero che esista una formula per creare questi raggruppamenti.
ho chiesto di spostare questa discussione in "algebra" come dici tu,
può darsi che sia più fortunato...
grazie
però noto subito che la persona "a" è sempre nel gruppo "1" e quindi con la persona "1" mentre è opportuno che ruoti
analogamente "d" e "d" e "2" si incontrano 3 volte
"c" e "3"
"i" e "3"
...
insomma penso che anche tu sei andato a sbattere sulla mia stessa difficoltà
Penso, immagino, spero che esista una formula per creare questi raggruppamenti.
ho chiesto di spostare questa discussione in "algebra" come dici tu,
può darsi che sia più fortunato...
grazie
Non credo si possa ottenere di meglio ... se hai notato tutte le $15$ "lettere" si incontrano tutte fra di loro una e una sola volta; perché questo accada sono necessarie sette "giornate" perciò per forza di cose, dato che i "capogruppo" sono $5$ qualcuno dovrà incontrarli più di una volta; certamente puoi spostare $a$ per fargli incontrare anche gli altri "numeri" (per esempio basta "riscrivere" la colonna dei numeri invece che $111....$ come $1234512$, e poi $222....$ come $2345123$, ecc) ma dovrai mettere qualcuno al suo posto ... non è possibile rispettare tutte le condizioni che chiedi ...
Cordialmente, Alex
Cordialmente, Alex
Per chiarire meglio perché quello che chiedi è impossibile ...
Il signor $1$ non deve mai incontrare gli altri signori numeri, deve però incontrare gli altri $15$ signori lettere; date che ne vede tre alla volta lo può fare in cinque volte e NON più di cinque.
Il signor $a$ deve vedere i $5$ signori numeri e lo può fare in cinque incontri, deve però vedere anche le altre $14$ lettere e dato che ne può vedere solo due alla volta, gli occorreranno sette incontri, quindi al sesto incontro dovrà forzatamente incontrare per la seconda volta uno dei signori numeri ... ok?
Cordialmente, Alex
Il signor $1$ non deve mai incontrare gli altri signori numeri, deve però incontrare gli altri $15$ signori lettere; date che ne vede tre alla volta lo può fare in cinque volte e NON più di cinque.
Il signor $a$ deve vedere i $5$ signori numeri e lo può fare in cinque incontri, deve però vedere anche le altre $14$ lettere e dato che ne può vedere solo due alla volta, gli occorreranno sette incontri, quindi al sesto incontro dovrà forzatamente incontrare per la seconda volta uno dei signori numeri ... ok?
Cordialmente, Alex
si ok, mi sembra un buon esempio su cui già da ieri sera sto lavorando. grazie Alex.
Rimane aperta la domanda , almeno come curiosità,
se esista un metodo, un criterio, una formula per approcciare il problema.
Grazie a Luca per avere spostato questa discussione in una sezione più appropriata.
Chiedo quindi a tutti gli esperti di Algebra se possono darmi una mano.
Rimane aperta la domanda , almeno come curiosità,
se esista un metodo, un criterio, una formula per approcciare il problema.
Grazie a Luca per avere spostato questa discussione in una sezione più appropriata.
Chiedo quindi a tutti gli esperti di Algebra se possono darmi una mano.
OFF-TOPIC: ma c'è qualche gara riguardo a questo problema? In due mesi sarà la terza volta che leggo un problema identico (su altri forum però)!
"Cronovirus":
OFF-TOPIC: ma c'è qualche gara riguardo a questo problema? In due mesi sarà la terza volta che leggo un problema identico (su altri forum però)!
no solo un problema personale di organizzare questi benedetti incontri della mia comunità,
problema che ho postato solo qui (anche perchè non conosco altri forum).
Se però hai qualche suggerimento, magari letto su qualche altro forum, è ben accetto
Ciao 
Ho ragionato (quando il tempo me lo permetteva ovviamente) su questo problema durante i giorni scorsi.
Innanzitutto posso affermare che è un problema che ammette almeno una soluzione. Può sembrare una considerazione banale questa che ho appena effettuato ma di fatto è lecito chiederselo davanti ad ogni problema prima di poterlo affrontare a mio parere.
Per poter "attaccare" questo problema sono ricorso alla teoria dei grafi (che ogni informatico che si rispetti dovrebbe conoscere bene). Possiamo vedere le nostre ventuno persone come vertici di un grafo non orientato completo (ossia tale per cui esiste un arco tra ogni coppia di vertici). Un arco tra un vertice $u$ ed un altro $v$ rappresenta il fatto che queste persone sono nello stesso gruppo. Partendo dunque da tale grafo inizialmente completo possiamo pensare di eliminare dallo stesso ad ogni giornata tanti insiemi di archi quanti sono i nostri gruppi (nella fattispecie cinque). Ciascuno di questi insiemi è composto da un numero di vertici pari alla cardinalità delle persone che sono presenti in quel gruppo. Nel nostro caso particolare ciascun insieme sarà dunque composto da tre vertici ad eccezione di uno di essi che ne ha quattro. Chiaramente tali insiemi non devono avere vertici in comune (poiché una persona non può essere presente in più di un gruppo contemporaneamente). L'unica accortezza è quella di tenere traccia dei gruppi in cui sono già state le varie persone in modo che quando si scelgono i vertici lo si possa fare con criterio, ossia con la certezza di non selezionare persone che sono già state in un determinato gruppo.
All'inizio si ha un totale di $\frac{21 \times 20}{2} = 210$ archi e dal grafo si eliminano $16$ archi alla volta.
Cosa ne pensate
Ho ragionato (quando il tempo me lo permetteva ovviamente) su questo problema durante i giorni scorsi.
Innanzitutto posso affermare che è un problema che ammette almeno una soluzione. Può sembrare una considerazione banale questa che ho appena effettuato ma di fatto è lecito chiederselo davanti ad ogni problema prima di poterlo affrontare a mio parere.
Per poter "attaccare" questo problema sono ricorso alla teoria dei grafi (che ogni informatico che si rispetti dovrebbe conoscere bene). Possiamo vedere le nostre ventuno persone come vertici di un grafo non orientato completo (ossia tale per cui esiste un arco tra ogni coppia di vertici). Un arco tra un vertice $u$ ed un altro $v$ rappresenta il fatto che queste persone sono nello stesso gruppo. Partendo dunque da tale grafo inizialmente completo possiamo pensare di eliminare dallo stesso ad ogni giornata tanti insiemi di archi quanti sono i nostri gruppi (nella fattispecie cinque). Ciascuno di questi insiemi è composto da un numero di vertici pari alla cardinalità delle persone che sono presenti in quel gruppo. Nel nostro caso particolare ciascun insieme sarà dunque composto da tre vertici ad eccezione di uno di essi che ne ha quattro. Chiaramente tali insiemi non devono avere vertici in comune (poiché una persona non può essere presente in più di un gruppo contemporaneamente). L'unica accortezza è quella di tenere traccia dei gruppi in cui sono già state le varie persone in modo che quando si scelgono i vertici lo si possa fare con criterio, ossia con la certezza di non selezionare persone che sono già state in un determinato gruppo.
All'inizio si ha un totale di $\frac{21 \times 20}{2} = 210$ archi e dal grafo si eliminano $16$ archi alla volta.
Cosa ne pensate
"onlyReferee":
... Innanzitutto posso affermare che è un problema che ammette almeno una soluzione. Può sembrare una considerazione banale questa che ho appena effettuato ma di fatto è lecito chiederselo davanti ad ogni problema prima di poterlo affrontare a mio parere. ...
Considerazione intelligente ma rimangono due problemi (a parer mio ...):
- spesso puoi affermare che una soluzione esiste solo dopo che l'hai trovata quindi in quel caso cercare se esiste significa cercare la soluzione (e quindi non cambia granchè ...), nell'altro caso corri il rischio di fare il lavoro due volte (se non è già evidente che la soluzione esista ...). Spero di essermi spiegato ...
- nel nostro caso come puoi affermare ciò? cioè che esista almeno una soluzione? riesci a confutare il mio esempio che dimostra la non fattibilità (anche se in effetti il mio riguarda venti persone e non ventuno)?
Cordialmente, Alex
Semplicemente prima di mettermi a trovare una soluzione in un grafo con quel numero di archi e nodi ho provato a ragionare in termini più ristretti per trarre delle conclusioni generiche.
Il problema posto da un altro utente potrebbe avere un numero diverso di persone e gruppi eppure non è diverso nella sostanza...
Il problema posto da un altro utente potrebbe avere un numero diverso di persone e gruppi eppure non è diverso nella sostanza...
mmm ... come l'hai scritta sembrava "questo tipo di problema ha sempre una soluzione" (così almeno l'ho interpretata io), ma non è così in questo caso e di conseguenza non è vero in generale (cioè non è vero che esiste sempre una soluzione a questo tipo problemi) ...
Sulla tua proposta non sono assolutamente in grado di esprimermi ...
Cordialmente, Alex
Sulla tua proposta non sono assolutamente in grado di esprimermi ...
Cordialmente, Alex
Faccio un attimo un passo indietro riguardo alla soluzione proposta poiché alla luce della considerazione seguente la stessa non si dimostra più valida: non avevo considerato nella mia soluzione con i grafi che in realtà dovrei rimuovere ad ogni iterazione tutti gli archi presenti tra i vertici (le persone) correntemente selezionate. Questo chiaramente cambia tutto il ragionamento.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo