Newsgroup: it.hobby.enigmi
Titolo: [Probabilità] Doni casuali

C'è un tizio che deve fare N doni a N persone, ma dopo che li ha
impacchettati arriva il suo fratello dispettoso e di nascosto rimescola a
caso le etichette con i nomi che vi erano attaccate. Qual' è la probabilità
che almeno un dono vada alla persona giusta?
Come lo risolvereste?
Ciao!!
Marco

 Come lo risolvereste?
SPOILER
Ciao,
Corrisponde esattamente all'argomento del thread che abbiamo appena 
discusso "Scommessa".  [N!/e] sono i casi in cui nessuno riceve il regalo a 
lui destinato.

"LordBeotian" <poki...@CANCELLAMIyahoo.it> ha scritto nel messaggio
news:R3Pqa.71161$DT4.2...@twister1.libero.it...

Ciao, Lord.
Scusami per l'imprecisione, ma ti faccio un esempio. Considera la
permutazione identica di N oggetti
1 2 3 4 ... N
1 2 3 4 ... N
Ed interpretala come la permutazione che fa corrispondere il dono 1 alla
persona 1 ecc...
Dobbiamo tener conto che dire "almeno una persona riceve il regalo ad essa
indirizzato" equivale a dire che è sufficiente che una permutazione F deve
essere "al minimo" una applicazione che non muove un elemento (ha un "punto
unito" direbbe qualcuno). Quindi Ogni 2-ciclo (trasposizione), ogni 3-ciclo,
..., ogni N-1-ciclo verificano quanto ti serve (credo di aver individuato i
casi favorevoli). I casi possibili sono N!
Spero di non aver detto cazzate.

 ha scritto nel messaggio
news:6VQqa.15497$K35.5...@news2.tin.it...

C'è da dire che esistono permutazioni di K elementi che non sono K-cicli, ma
sono cmq prodotti di cicli e quindi, alla fine, di trasposizioni.


Mi sa che il discorso non funzioni per N=4. I casi in cui nessuno riceve il
proprio regalo sono 9 e non 8=[4!/e]. Mi sbaglio?

Come lo risolvereste?
con il problema delle concordanze, ossia supponendo che n carte siano
numerate progressivamente con i numeri da 1 ad n e che vengano estratte in
successione da un mazzo in cui sono mescolate.
dicesi 'concordanza' quando una carta estratta porta lo stesso numero della
sua estrazione.

 diviso k fattoriale)
E' corretto.

 proprio regalo sono 9 e non 8=[4!/e]. Mi sbaglio?
Si'. Le parentesi quadre indicano che il valore e' arrotondato all'intero 
piu' vicino, (round) che in questo caso e' proprio=9
Questi derangements chiamati anche subfattoriali sono generalmente indicati 
col simbolo !N
C'e' una grossa letteratura, vedi ad es:
http://mathworld.wolfram.com/Subfactorial.html

 piu' vicino, (round) che in questo caso e' proprio=9
Io avevo capito che [x] fosse la parte intera di x (detta anche
"floor(x)" ). Cosě torna.

E' corretto.
grazie! :--)
da notare che la serie in questione, per N molto grande, tende ad e elevato
alla -1, che è all'incirca pari a 0,368. E' quindi più probabile che ci sia
almeno una concordanza che non ce ne sia nemmano una.

 successione da un mazzo in cui sono mescolate.
Sì, ok, questo che dici è certamente un problema isomorfo a quello dei doni
ma ti chiedo: come li risolvi, cioè come arrivi alla formula finale?
Ciao, Grazie!
Marco


Classico problema delle permutazioni senza ripetizione. In questa pagina e'
descritta bene la teoria.
http://mathworld.wolfram.com/Derangement.html
Bye.

 Marco
http://cerebro.xu.edu/math/Sources/Euler/E738.pdf
http://www.math.uah.edu/statold/urn/urn6.html
http://hilbert.dartmouth.edu/~doyle/docs/rank/rank/rank.html
Addirittura i bambini:
http://mathforum.org/dmpow/solutions/full_solution.ehtml?puzzle=28

>
Non ho visto tutti i link, ma mi piace questo esercizio.
Per me deve essere molto difficile "arrivare" alla formula finale.
Per fare questo ho immaginato di provare a mettere in piedi
(per calcolare l'evento
complementare "tutti hanno regali diversi") una cosa tipo:
la prima persona ha un regalo sbagliato AND la seconda ha un regalo
sbagliato etc...
e comincia a venirmi fuori un qualcosa di piuttosto massiccio:
il primo ha un regalo qualsiasi tra gli N tranne uno [il che ha 
probabilita' N-1/N]
AND
il secondo ha un regalo qualsiasi tra i rimanenti N-1 tranne uno, se il 
primo aveva ricevuto un regalo che non era del secondo
OPPURE
il secondo ha un regalo qualsiasi tra i rimanenti se il primo
aveva ricavuto proprio il regalo del secondo
[e quindi devo fare il prodotto di tutto questo con il primo termine]
AND
(il terzo ha ricevuto un regalo qualsiasi tra i rimanenti tranne uno,
se ne' il primo ne' il secondo ha ricevuto uno dei sui regali
OPPURE
il terzo riceve un regalo qualsiasi tra i rimanenti se uno dei primi due 
avevano ricevuto proprio il suo regalo )
etc...
A parte questo esercizio, che ha una sua complessita', forse
si puo' fare una cosa diversa:
prendere la formula per buona e dimostrarne la validita' per induzione.
Basterebbe dimostrare che vale quando ci sono due doni e due persone,
e poi dire che se vale per N persone, continua a valere aggiungendo
una persona ed un regalo.
