Secret santa

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Secret santa

Innlegg Aleks855 » 04/12-2019 13:05

En liten morsom sannsynlighetsnøtt som kom opp under Secret Santa-utdeling på jobb i dag.

Vi har 19 deltakere. Én person lager en lapp med hvert navn på. Han tildeler dermed hver deltaker et navn uten å se på resultatet selv. Håpet er at ingen får seg selv som Secret Santa.

Etter utdelinga nølte han, og spurte "hmm, hva er sannsynligheten for at INGEN fikk seg selv som Secret Santa?"

Den underliggende bekymringa er "hva er sannsynligheten for at noen fikk seg selv, men var fornøyd med det, og sa ikke fra?"

Syntes det var litt morsomt at en oppgave som dette dukket opp naturlig. Det er en oppgave som er veldig lik mange av de oppgavene man ser i lærebøker.
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 6066
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Secret santa

Innlegg josi » 04/12-2019 15:14

I min vankunne har jeg ikke godt grep om den tydeligvis usalige situasjon det vil være å havne som Secret Santa, men så vidt jeg kan se er det i underkant av 37% sjanse for at ingen av de 19 deltakerne vil måtte befinne seg i en lik penibel tilstand.
josi offline

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 16:34

Hei,
Jeg drister meg utpå:

X = ant som får sitt eget navn
P(X = 0) = (18/19)^19 = 0.358
P(X =/> 1) = 1 - P(X = 0) = 0.642
Det er altså 64.2 % sjanse for at NOEN får sitt eget navn

Videre har vi (se vedlagte sannsynlighetskalkulator) at
P(X = 1) = 0.3779
og sjansen for at denne ene skal la være å si at han/hun fikk sitt eget navn (lyver) er 0.5
så vi har
P(en lyver U X = 1) = 0.3779 * 0.5 = 0.189

videre har vi
P(noen lyver U X = 2) = 0.1888 (1 - 0.5^2) = 0.142
P(noen lyver U X = 3) = 0.052
P(noen lyver U X = 4) = 0.012
P(noen lyver U X = 5) = 0.002
P(noen lyver U X = 6) = 0.000


Samlet sannsynlighet for at NOEN har fått sitt eget navn OG lar være å si i fra er 0.397, altså ca 40 %
Vedlegg
Secret santa.odt
(73.45 KiB) 35 ganger
Sist endret av Kristian Saug den 04/12-2019 18:35, endret 2 ganger.
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg josi » 04/12-2019 17:30

"X = ant som får sitt eget navn
P(X = 0) = (18/19)^19 = 0.358"

Hendelsene er ikke uavhengige av hverandre. Hvis person n får navnet til person n+1, reduserer det sjansene for at person n+1 skal få sitt eget navn til null.
josi offline

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 17:52

Sjansen for at INGEN får sitt eget navn er (18/19)^19 = 0.358. Sjansen for at DU ikke får ditt eget navn er 18/19. Samme er sjansen for MEG og alle de andre. Sjansen for at EN og BARE EN får sitt eget navn er ((1/19) * (18/19)^18) * 19 = 0.378. Osv....

Se også vedlegget. Svaret blir 40 % sannsynlighet for at NOEN får sitt eget navn OG IKKE SIER FRA.

Har du et annet, komplett LF?
Vedlegg
Secret santa.odt
(73.45 KiB) 37 ganger
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg Aleks855 » 04/12-2019 18:42

Jeg har ikke LF for dette. Men en detalj jeg frykter er oversett, er at for hver gang en person trekker noen andre enn seg selv, så fins det en annen deltaker som nå ikke har muligheten til å trekke seg selv.

Betrakt følgende observasjon.

$P(\text{første person trekker noen andre enn seg selv}) = \frac{18}{19}$ trivielt. Men nå er én av de andre personene trukket og det fins 1 person som med 100% sikkerhet trekker noen andre. De andre 17 har 17/18 sjanse for å trekke noen andre enn seg selv.

$P(\text{andre person trekker noen andre enn seg selv}) = \frac{1}{18} \cdot 1 + \frac{17}{18} \cdot \frac{17}{18}$. Nå har to personer trukket noen andre enn seg selv. Av de øvrige 17 deltakerne er det nå 2 personer som med 100% sikkerhet trekker noen andre. De andre 15 har 16/17 sjanse enda, så...

$P(\text{tredje person trekker noen andre enn seg selv}) = \frac{2}{17} \cdot 1 + \frac{15}{17} \cdot \frac{16}{17}$

Generelt: $P(\text{n'te person trekker noen andre enn seg selv}) = \frac{n-1}{20-n} + \frac{\left[19-2(n-1)\right]\left[19-n\right]}{(20-n)^2}$

Men i det jeg tipper er en overkomplisering, så har jeg gjort noe feil, fordi når jeg summerer over dette uttrykket for $n = 1,2,3,\ldots, 6$ så får jeg allerede et resultat som er større enn 1.
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 6066
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 18:48

Aleks855 skrev:Jeg har ikke LF for dette. Men en detalj jeg frykter er oversett, er at for hver gang en person trekker noen andre enn seg selv, så fins det en annen deltaker som nå ikke har muligheten til å trekke seg selv.

Betrakt følgende observasjon.

$P(\text{første person trekker noen andre enn seg selv}) = \frac{18}{19}$ trivielt. Men nå er én av de andre personene trukket og det fins 1 person som med 100% sikkerhet trekker noen andre. De andre 17 har 17/18 sjanse for å trekke noen andre enn seg selv.

$P(\text{andre person trekker noen andre enn seg selv}) = \frac{1}{18} \cdot 1 + \frac{17}{18} \cdot \frac{17}{18}$. Nå har to personer trukket noen andre enn seg selv. Av de øvrige 17 deltakerne er det nå 2 personer som med 100% sikkerhet trekker noen andre. De andre 15 har 16/17 sjanse enda, så...

$P(\text{tredje person trekker noen andre enn seg selv}) = \frac{2}{17} \cdot 1 + \frac{15}{17} \cdot \frac{16}{17}$

Generelt: $P(\text{n'te person trekker noen andre enn seg selv}) = \frac{n-1}{20-n} + \frac{\left[19-2(n-1)\right]\left[19-n\right]}{(20-n)^2}$

Men i det jeg tipper er en overkomplisering, så har jeg gjort noe feil, fordi når jeg summerer over dette uttrykket for $n = 1,2,3,\ldots, 6$ så får jeg allerede et resultat som er større enn 1.



Hei!

Jeg tenkte også først noe liknende med det du gjør her, men slo så fast at det ikke stemte.........
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg Aleks855 » 04/12-2019 18:50

Da er det med andre ord minst én annen detalj som er oversett.
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 6066
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 18:54

Aleks855 skrev:Da er det med andre ord minst én annen detalj som er oversett.


Hmmm....., nei, jeg mener min løsning er riktig. Dersom noen får sitt eget navn, som du påpeker, er vi ute i sannsynligheten for at en eller flere får sitt egen navn. Og det er tatt hensyn til...

Men, jeg er førstemann til å innrømme feil dersom det er begått.
Det interessante er om du kan komme med et annet LF, der summen av sannsynlighetene for de forskjellige utfall er 1.
Sist endret av Kristian Saug den 04/12-2019 18:57, endret 1 gang
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg Aleks855 » 04/12-2019 18:57

Er det? Hvis alle har 18/19 sjanse for å trekke noen andre, antyder ikke det tilbakelegging?
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 6066
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 19:02

Aleks855 skrev:Er det? Hvis alle har 18/19 sjanse for å trekke noen andre, antyder ikke det tilbakelegging?


Javisst har alle 18/19 sjanse for å trekke noen andre enn seg selv. Det vil alle tenke der de står og svelger sin gløgg. Og det er rett.

Men, jeg er førstemann til å innrømme feil dersom det er begått.
Det interessante er om du kan komme med et annet LF, der summen av sannsynlighetene for de forskjellige utfall er 1. Da kan vi se nærmere på det.
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg Aleks855 » 04/12-2019 19:06

Jeg ser nå at jeg kanskje var uklar, men det er ingen tilbakelegging i Secret Santa. Dersom det var tilbakelegging, så ville noen personer fått flere gaver, og noen ville ikke fått noe.

Alle navn trekkes nøyaktig én gang.

Derav min tankegang om at når én trekning er gjort, så er ett navn ute av hatten, og den personen har nå 0% sjanse for å velge seg selv.
Bilde
Aleks855 online
Rasch
Rasch
Innlegg: 6066
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Secret santa

Innlegg josi » 04/12-2019 19:30

Nitten lapper med med navnene til 19 personer, ett navn på hver lapp, deles ut til disse 19 personene i tilfeldig rekkefølge, én lapp til hver. Hva er sjansene for at minst én person blir tildelt en lapp med eget navn? La [tex]E_j[/tex] betgne at person nr [tex]j[/tex] får lapp med eget navn.

Da har vi
[tex]P(E_j) = \frac1n[/tex] for alle [tex]j[/tex]

[tex]P(E_i[/tex]&[tex]E_j) = \frac1n*\frac1{(n-1)}[/tex] for alle [tex]i<j[/tex]

[tex]P(E_i[/tex]&[tex]E_j[/tex]& ....&[tex]E_n[/tex]) = [tex]\frac1{n!}[/tex]

Antall ledd som inngår i de enkelte summene:

[tex]\Sigma_{j =1}^nP(E_j) = n*\frac1n = 1[/tex]

Sjansene foe at ingen får en lapp med eget navn er: 1 -0.6321 = 0.3679

[tex]\Sigma_{i<j}P(E_i[/tex]&[tex]E_j)[/tex] = [tex]\frac{n(n-1)}{1*2}*\frac1{n*(n-1)} = \frac1{2!}[/tex]

Ved å summere summene får vi:

[tex]P(E_1uE_2u.....uE_n) = 1 -\frac1{2!} +\frac1{3!} -\frac1{4!} + ....+(-1)^{n-1}\frac1{n!}[/tex]

n = 19, og summen konvergerer raskt til 1 - [tex]e^{-1}[/tex] = 0.6321

Sjansene for at ingen får lapp med eget navn = 0.3679
josi offline

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 19:41

josi skrev:Nitten lapper med med navnene til 19 personer, ett navn på hver lapp, deles ut til disse 19 personene i tilfeldig rekkefølge, én lapp til hver. Hva er sjansene for at minst én person blir tildelt en lapp med eget navn? La [tex]E_j[/tex] betgne at person nr [tex]j[/tex] får lapp med eget navn.

Da har vi
[tex]P(E_j) = \frac1n[/tex] for alle [tex]j[/tex]

[tex]P(E_i[/tex]&[tex]E_j) = \frac1n*\frac1{(n-1)}[/tex] for alle [tex]i<j[/tex]

[tex]P(E_i[/tex]&[tex]E_j[/tex]& ....&[tex]E_n[/tex]) = [tex]\frac1{n!}[/tex]

Antall ledd som inngår i de enkelte summene:

[tex]\Sigma_{j =1}^nP(E_j) = n*\frac1n = 1[/tex]


Ja, samme svar som jeg har!
Men så skal du iflg oppgaven videre regne på sannsynligheten for at noen (en eller flere) trekker eget navn OG ikke sier fra om det. Da tenker jeg du kommer frem til 40 % sannsynlighet også...

Sjansene foe at ingen får en lapp med eget navn er: 1 -0.6321 = 0.3679

[tex]\Sigma_{i<j}P(E_i[/tex]&[tex]E_j)[/tex] = [tex]\frac{n(n-1)}{1*2}*\frac1{n*(n-1)} = \frac1{2!}[/tex]

Ved å summere summene får vi:

[tex]P(E_1uE_2u.....uE_n) = 1 -\frac1{2!} +\frac1{3!} -\frac1{4!} + ....+(-1)^{n-1}\frac1{n!}[/tex]

n = 19, og summen konvergerer raskt til 1 - [tex]e^{-1}[/tex] = 0.6321

Sjansene for at ingen får lapp med eget navn = 0.3679
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Re: Secret santa

Innlegg Kristian Saug » 04/12-2019 19:46

Aleks855 skrev:Jeg ser nå at jeg kanskje var uklar, men det er ingen tilbakelegging i Secret Santa. Dersom det var tilbakelegging, så ville noen personer fått flere gaver, og noen ville ikke fått noe.

Alle navn trekkes nøyaktig én gang.

Derav min tankegang om at når én trekning er gjort, så er ett navn ute av hatten, og den personen har nå 0% sjanse for å velge seg selv.


Regn hele oppgaven. Jeg sier heller ikke at lappene legges tilbake.
Fremgangsmåten din og sluttsvaret blir interessant. Altså sannsynligheten for at en eller flere trekker eget navn OG ikke sier fra om det. Se også til at summen av sannsynlighetene for de forskjellige utfallene blir 1.
Kristian Saug offline
Weierstrass
Weierstrass
Innlegg: 453
Registrert: 11/11-2019 18:23

Neste

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 80 gjester