Permutazioni cicliche

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Odraode
Messaggi: 2
Iscritto il: 30 gen 2014, 15:51

Permutazioni cicliche

Messaggio da Odraode » 30 gen 2014, 16:16

Salve a tutti, questo è il mio primo post. L'esercizio che vi propongo dovrebbe essere un esercizio abbastanza facile che però ha dato parecchi problemi alla mia squadra nella gara online del 28. Ecco il testo:

11 uomini e 8 donne si siedono a caso attorno ad una tavola rotonda. Qual è la probabilità che ogni donna sieda tra due uomini?

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Permutazioni cicliche

Messaggio da BorisM » 31 gen 2014, 16:04

Odraode ha scritto:Salve a tutti, questo è il mio primo post. L'esercizio che vi propongo dovrebbe essere un esercizio abbastanza facile che però ha dato parecchi problemi alla mia squadra nella gara online del 28. Ecco il testo:

11 uomini e 8 donne si siedono a caso attorno ad una tavola rotonda. Qual è la probabilità che ogni donna sieda tra due uomini?
Io l' ho risolto in questo modo:
intanto per cominciare tutti i possibili casi sono tadi dall' anagramma della parola $UUUUUUUUUUUDDDDDDDD$ composta da $8U$(uomini) e $8D$ (donne).
I casi possibili sono quindi: $19!/8!11!$
Ora scegliamo una sedia. Abbiamo due casi: o vi siede un uomo o vi siede una donna.
Consideriamo il primo caso. Se chiamiamo la coppia di lettere $UD$ $X$ avremmo una parola formata da $8X$ e $3U$ quindi per contare i possibili casi in cui una donna si può sedere tra due uomini basterà fare gli anagrammi della parola $XXXXXXXXUUU$ che sono: $11!/8!3!$. Infatti anche se la parola termina per $X$ quindi se nell' undicesimo posto vi è una donna essa si troverà accanto l' uomo nel decimo posto e l' uomo nel primo in quanto il tavolo è rotondo.
Consideriamo il secondo caso. Chiamiamo sempre $X$ la coppia di lettere $UD$. Per contare in quanti modi possibili una donna può sedersi tra due uomini dobbiamo considerare che un uomo deve per forza trovarsi nell undicesimo posto altrimenti la prima donna nel caso in cui avessimo la $X$ alla fine della parola si troverebbe accanto ad una donna.
La parola diventa quindi $UD-XXXXXXXUUU$ e dobbiamo fare gli anagrammi solo della seconda parte. Quindi $10!/7!3!$.
Ora abbiamo tutti i casi favorevoli e tutti i casi possibili. Basterà dunque fare la somma dei primi e dividerli per i secondi=
$11!/8!3!$ + $10!/7!3!$ tutto fratto $19!/8!11!$
risolvendo i calcoli otteniamo $5/1326$
Spero di non aver sbagliato il ragionamento e i calcoli.

PS qualcuno può postarmi il link per la guida alla scrittura delle formule? Sono un pò impedito !! :lol:

Half95
Messaggi: 44
Iscritto il: 21 ago 2013, 21:55

Re: Permutazioni cicliche

Messaggio da Half95 » 31 gen 2014, 17:42

Io l' ho risolto in questo modo:
intanto per cominciare tutti i possibili casi sono tadi dall' anagramma della parola $UUUUUUUUUUUDDDDDDDD$ composta da $8U$(uomini) e $8D$ (donne).
I casi possibili sono quindi: $19!/8!11!$
Ora scegliamo una sedia. Abbiamo due casi: o vi siede un uomo o vi siede una donna.
Consideriamo il primo caso. Se chiamiamo la coppia di lettere $UD$ $X$ avremmo una parola formata da $8X$ e $3U$ quindi per contare i possibili casi in cui una donna si può sedere tra due uomini basterà fare gli anagrammi della parola $XXXXXXXXUUU$ che sono: $11!/8!3!$. Infatti anche se la parola termina per $X$ quindi se nell' undicesimo posto vi è una donna essa si troverà accanto l' uomo nel decimo posto e l' uomo nel primo in quanto il tavolo è rotondo.
Consideriamo il secondo caso. Chiamiamo sempre $X$ la coppia di lettere $UD$. Per contare in quanti modi possibili una donna può sedersi tra due uomini dobbiamo considerare che un uomo deve per forza trovarsi nell undicesimo posto altrimenti la prima donna nel caso in cui avessimo la $X$ alla fine della parola si troverebbe accanto ad una donna.
La parola diventa quindi $UD-XXXXXXXUUU$ e dobbiamo fare gli anagrammi solo della seconda parte. Quindi $10!/7!3!$.
Ora abbiamo tutti i casi favorevoli e tutti i casi possibili. Basterà dunque fare la somma dei primi e dividerli per i secondi=
$11!/8!3!$ + $10!/7!3!$ tutto fratto $19!/8!11!$
risolvendo i calcoli otteniamo $5/1326$
Spero di non aver sbagliato il ragionamento e i calcoli.

PS qualcuno può postarmi il link per la guida alla scrittura delle formule? Sono un pò impedito !! :lol:
Dubbio: in questo caso due disposizioni non si considerano uguali se posso ottenere una delle due partendo dall' altra con una rotazione?

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Permutazioni cicliche

Messaggio da BorisM » 31 gen 2014, 20:09

Se non sbaglio in questi problemi i posti è come se fossero numerati. Ad esempio dovrebbe cambiare considerare seduta sulla prima sedia una donna o un uomo. Per questo ho analizzato entrambi i casi. In questo caso è come se i posti fossero numerati da 1 a 11. Naturalmente se la mia ipotesi è sbagliata anche la soluzione è errata di conseguenza.

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Permutazioni cicliche

Messaggio da _Ipazia_ » 01 feb 2014, 15:12

BorisM ha scritto:Se non sbaglio in questi problemi i posti è come se fossero numerati.
Penso che se i posti fossero numerati sarebbe detto esplicitamente :? In ogni caso, forse quello che sto per dire non sta nè in cielo nè in terra ma può essere che il risultato sia uguale. Infatti essendo 8 e 11 coprimi ogni combinazione di posti può essere ripetuta per rotazione 19 volte (che sono i posti), quindi nel calcolo della probabilità si dividerebbe per 19 sia il numero di casi favorevoli sia i casi totali. Ma non sono per niente sicura di quello che sto dicendo :roll:
edit: sì l'ho fatto con i posti non numerati e il risultato viene uguale :)
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

BorisM
Messaggi: 45
Iscritto il: 08 lug 2013, 20:11

Re: Permutazioni cicliche

Messaggio da BorisM » 01 feb 2014, 18:50

_Ipazia_ ha scritto:
BorisM ha scritto:Se non sbaglio in questi problemi i posti è come se fossero numerati.
Penso che se i posti fossero numerati sarebbe detto esplicitamente :? In ogni caso, forse quello che sto per dire non sta nè in cielo nè in terra ma può essere che il risultato sia uguale. Infatti essendo 8 e 11 coprimi ogni combinazione di posti può essere ripetuta per rotazione 19 volte (che sono i posti), quindi nel calcolo della probabilità si dividerebbe per 19 sia il numero di casi favorevoli sia i casi totali. Ma non sono per niente sicura di quello che sto dicendo :roll:
edit: sì l'ho fatto con i posti non numerati e il risultato viene uguale :)
Che cosa intendi per "comprimi ogni rotazione di posti"?
Magari posta la tua soluzione se ne hai voglia :D
Comunque ho trovato problemi simili che davano come consiglio quello di numerare i posti quindi penso che ci sia differenza

_Ipazia_
Messaggi: 50
Iscritto il: 23 feb 2013, 15:23

Re: Permutazioni cicliche

Messaggio da _Ipazia_ » 03 feb 2014, 16:10

Dunque, l'idea è di contare le combinazioni come anagrammi di UUUUUUUUUUUDDDDDDDD e poi dividere il risultato per 19, che sono i posti. Infatti da ogni combinazione in quella forma se ne possono ottenere altre 18 (spostando l'ultima lettera all'inizio della sequenza) che in un tavolo circolare si equivalgono per rotazione. Questo è possibile perchè i numeri di lettere U e D, 11 e 8 sono coprimi. Altrimenti il numero di combinazioni equivalenti per rotazione non sarebbe esattamente il numero dei posti. Ad esempio (con numeri più piccoli :wink: ) la combinazione DDUUDDUU è uguale per rotazione solo a UDDUUDDU , UUDDUUDD e DUUDDUUD, non ad altre 8, come il numero delle lettere.
Io per risolvere il problema ho iniziato a disporre le donne e poi un uomo fra ogni coppia di donne:
UDUDUDUDUDUDUDUD
Quindi avanzano 3 uomini che si devono disporre ancora negli spazi fra una donna e l'altra, quindi in 8 posizioni:
UD_UD_UD_UD_UD_UD_UD_UD_
Dobbiamo quindi mettere 3 uomini in 8 spazi. Il che equivale a contare le permutazioni di UUUAAAAAAA, dove ogni A rappresenta un "separatore" fra uno spazio e l'altro. Tali permutazioni sono 10! / 3!*7!=120. Ma siccome il tavolo è circolare da ogni combinazione se ne possono ricavare altre 7 uguali per rotazione (infatti i posti da "ruotare" sono 8 ). Quindi il risultato va diviso per 8, ottenendo 120/8=15.
Ora che abbiamo calcolato i casi favorevoli passiamo ai casi totali: si tratta delle permutazioni di UUUUUUUUUUUDDDDDDDD, che sono 19! / 11!*8!=75582. Anche questo va diviso per 19, per eliminare le permutazioni identiche per rotazione: 75582/19=3978.
La probabilità cercata è quindi 15/3978=5/1326 :)
“SE ASCOLTO DIMENTICO, SE GUARDO IMPARO, SE FACCIO CAPISCO”

Rispondi