Problem om julklappar

Hur skulle 4 kunna få den julklapp hen har köpt själv, utan att den femte också får sin egen julklapp?

Det finns fem sätt (fem över ett, som du har skrivit) att välja en som får sin egen julklapp, men sen finns det många sätt för de fyra återstående att få de andra, så resonemanget stämmer inte. 

Laguna skrev:

Det finns fem sätt (fem över ett, som du har skrivit) att välja en som får sin egen julklapp, men sen finns det många sätt för de fyra återstående att få de andra, så resonemanget stämmer inte. 

för de fyra andra personerna finns det 4*3*2*1 sätt? 

Nichrome skrev:

Laguna skrev:

Det finns fem sätt (fem över ett, som du har skrivit) att välja en som får sin egen julklapp, men sen finns det många sätt för de fyra återstående att få de andra, så resonemanget stämmer inte. 

för de fyra andra personerna finns det 4*3*2*1 sätt? 

Inte riktigt så många, för då får du med fall där någon får den julklapp den själv har köpt.

Laguna skrev:

Nichrome skrev:

Visa föregående citat

Laguna skrev:

Det finns fem sätt (fem över ett, som du har skrivit) att välja en som får sin egen julklapp, men sen finns det många sätt för de fyra återstående att få de andra, så resonemanget stämmer inte. 

för de fyra andra personerna finns det 4*3*2*1 sätt? 

Inte riktigt så många, för då får du med fall där någon får den julklapp den själv har köpt.

Nu hänger jag inte med, vad är det jag räknar fel?

Det här är antagligen inte så som det är tänkt att man ska tänka:

Anta att vi håller oss till samma uppgift fast bara 3 stycken personer. Detta ger en så liten mängd kombinationer att vi kan rabbla upp alla kombinationer och se hur många som alla får någon annans klapp på.

Anta att personerna heter A, B, och C och att de sitter i bokstavsordning. Det finns då 3! = 6 stycken kombinationer. Anta att paketen är markerade med givarens namn. Då blir kombinationerna och antalet som fick sitt eget paket som följer

ABC     3 fick sitt eget paket

ACB     1 fick sitt eget paket

BAC     1 fick sitt eget paket

BCA     0 fick sitt eget paket

CAB     0 fick sitt eget paket

CBA     1 fick sitt eget paket

På denna mindre uppgift fanns det alltså 2 stycken lösningar. Båda lösningarna motsvarade att strängen ABC förskjutits antingen ett steg bakåt eller ett steg framåt.

Om vi nu tänker på den faktiska uppgiften. Om vi tänker oss det som ett träd där vi i varje steg väljer paket för en person. Och för att göra det lätt för oss tänker vi oss att om personen på steg n valde person X:s paket så är nästa person att få välja person X. Vad sker då?

Nyckelbiten är att det kommer uppstå cirklar av givande (t.ex. A ger till B som ger till C som ger till A) och att dessa bör väljas så att ingen tvingas in i en cirkel på 1.

Den första lösningen är då en cirkel på 5. Person 1 kan då välja alla utom sitt egen paket, dvs. 4.

Person 2(vars paket person 1 valde) kan då av kvarvarande 4 paket välja alla utom Person 1:s, dvs. 3. 

Person 3(vars paket person 2 valde) kan då av kvarvarande 3 paket välja alla utom Person 1:s, dvs. 2.

Person 4(vars paket person 3 valde) kan då av kvarvarande 2 paket välja alla utom Person 1:s, dvs. 1.  

Person 5(vars paket person 4 valde) kan då av kvarvarande 1 paket bara välja Person 1:s, dvs. ett val på 1.

4*3*2*1*1 = 24 uppsättningar där alla ingår i en cirkel.

Då går vi över till fler fast mindre cirklar. Om vi har två cirklar blir uppdelningen {4;1}, {3,2}, {2,3} eller {1,4}. Den första och sista har dock att en person bara får ge till sig själv så de kan vi stryka.

Från det tidigare exemplet vet vi att två cirklar kan bildas med tre personer. På två personer består cirkeln av ett enkelt klapputbyte som bara kan göras på ett sätt. Så det borde bli antalet sätt man kan dela in 5 personer i två grupper á 2 & 3 på. Det borde bli $2*1*\left(\begin{array}{c}5\\ 2\end{array}\right)=2*\frac{5*4}{2*1}=20$sätt.

24+20= 44 sätt får jag det till.

Det är mycket möjligt att jag tänkt helt fel ovan. Och att om jag tänkt rätt så lär det finnas andra sätt att komma fram till samma siffra i slutändan.

Jag hänger inte alls med, hur räknar man ut att de resterande 4 personerna inte får den julklapp som de själv har köpt. Om vi nu antar att det är bara en person som får den julklapp som hen själv har köpt. 

Jag använde Bedinsis metod, och jag tycker den är enkel, men det är för att jag har läst om gruppteori och permutationer och cykler osv. Det kan inte vara så det är tänkt att man ska komma på svaret i Matte 1.

Det kanske går att räkna upp möjligheterna på ett bra sätt, ungefär som Nichrome försökte.

Vi ska fortsätta tänka. 

Jag har läst en del om permutationer men inte om gruppteori och cykler...

Är uppgiften från Matte 1?

Ja, jag vet inte riktigt jag vill bara lösa den

Din uppställning är nog den bästa för att räkna ut svaret, om man dessutom tänker på hur många sätt det finns att permutera ett mindre antal element så att inget behåller sin plats.

Vi betraktar dina fem fall "k personer får den julklapp den själv har köpt".

För k = 1 väljer vi först den personen, vilket sker på $5\choose 1$ = 5 sätt. De övriga fyra ska inte få den julklapp den själv har köpt, och hur många det är vet vi inte just nu, men vi kallar det talet P₄ så länge. (Talet vi håller på och beräknar blir P₅.)

För k = 2 väljer vi de två personerna, vilket sker på $5\choose 2$ = 10 sätt. De övriga tre ska inte få den julklapp den själv har köpt, och det kan ske på P₃ sätt.

För k = 3 får vi ${{5}\choose {3}} \cdot P_2$. P₂ är enkelt att räkna ut, det är 1.

Fallet k = 4 finns inte, som Smaragdalena påpekade, och för k = 5 finns 1 möjlighet.

Vi behöver talen P₃ och P₄.

Med samma resonemang som tidigare blir $P_3 = 3! - ({3\choose 1} \cdot P_2 + {3\choose 3}) = 2$.

Med samma resonemang som tidigare blir $P_4 = 4! - ({4\choose 1} \cdot P_3 + {4\choose 2} \cdot P_2 + {4\choose 4}) = 9$.

P₅ är alltså $5! - ({5 \choose 1} \cdot P_4 + {5\choose 2}\cdot P_3 + {5\choose 3}\cdot P_2 + {5\choose 5}) = 44$.

Övning: beräkna P₆.

 k = 1, när du säger "och hur många det är vet vi inte just nu" menar du hur många av de 4  kan få den julklapp den själv har köpt? Förutom en av de 5 som kommer att få den julklapp som den själv har köpt 100%. Eller vad är talet P egentligen? Är det antal kombinationer där 1, 2, 3, eller 4 av de kvarvarande kan få en julklapp(själv har köpt) när bara en av dem får den julklapp den själv har köpt(alltså att det är ett säkert fall).

*Nu är jag med på varför k=4 inte funkar! 

Mitt $P_k$ betyder antalet permutationer av k element så att inget ligger kvar där det var, eller med språkbruket från uppgiften, ingen får den julklapp den själv har köpt. 

> k = 1, när du säger "och hur många det är vet vi inte just nu" menar du hur många av de 4  kan få den julklapp den själv har köpt?

Laguna menar hur många sätt eller permutationer som det är. Det var en smula olyckligt att ett av de orden eller en synonym till de föll bort.

> Eller vad är talet P egentligen?

P_n anger på hur många sätt som man kan låta n personer dela ut sina n klappar mellan sig på ett vis som gör att ingen får klappen som de själva gav.

Då man exempelvis räknar ut P₃ så utgår vi från hur många kombinationer man totalt sett kan göra, dvs. 3!, och från detta subtraherar vi antalet av dessa där någon fick sin egen klapp.

Antingdera fick 1 sin egen klapp och därmed fick 2 det inte, och att välja ut vem denna självgivare är kan ske på $\left(\begin{array}{c}3\\ 1\end{array}\right)$ vis. Detta multiplicerar man med hur många sätt som man kan låta 2 personer dela ut sina 2 klappar mellan sig på ett vis som gör att ingen får klappen som de själva gav, dvs. P₂.

Eller så fick 3 sin egen klapp och därmed fick 0 det inte, och att välja ut vilka dessa självgivare är kan ske på $\left(\begin{array}{c}3\\ 3\end{array}\right)$ vis. Detta multiplicerar man med hur många sätt som man kan låta 0 personer dela ut sina 0 klappar mellan sig på ett vis som gör att ingen får klappen som de själva gav, dvs. P₀ .

Detta ger:

$P_3=3!-\left(\left(\begin{array}{c}3\\ 1\end{array}\right)*P_2+\left(\begin{array}{c}3\\ 3\end{array}\right)*P_0\right)$

vilket är exakt det som Laguna skrev, även om hen gjorde den direkta konverteringen av P₀ till sitt värde 1. Och om jag skall vara riktigt petig är lösningen egentligen

$P_3=3!-\left(\left(\begin{array}{c}3\\ 1\end{array}\right)*P_2+\left(\begin{array}{c}3\\ 2\end{array}\right)*P_1+\left(\begin{array}{c}3\\ 3\end{array}\right)*P_0\right)$

Men eftersom P₁ anger på hur många sätt en person kan dela klapp med bara sig själv och samtidigt se till att hen inte får sin egen blir den termen nollställd.

EDIT: ...och medan jag skriver ett svar hinner Laguna svara själv. Nåväl.

Jag hänger med i vad vi gör och varför vi gör som vi gör men hur kan vi lösa uppgiften när vi multiplicerar med okända värden? Och varför blev det plötsligt $\left(\begin{array}{c}3\\ 1\end{array}\right)$ ? Vi har 5 personer hela tiden?  När vi har $\left(\begin{array}{c}5\\ 3\end{array}\right)$ = 10 det finns 10 permutationer och de två som är kvar kan få den julklapp som de själv har köpt på 1 sätt. Hur många kombinationer blir det? 

Och jag förstår inte riktigt vad händer med k = 3....

5! = totalt

(5 / 1 ) * (4! - ( (4 / 4) + (4 /2) + (4 / 1) ))= 5 * (24 - ( 1 + 6 + 4)) = 5*(24-11) 

( 5 / 2) * (3! - ( (3 /3) + (3 /1) ) = 10 * (6 - (1 + 3) = 10 * 2 = 20

(5 / 3) = 10

( 5 / 5) = 1

Jag har tänkt så, med (5/5) menar jag fem över fem alltså. Men det blir inte rätt, trots att jag använder samma logik, typ...?

Det är bättre att försöka tänka själv än att chansa på att använda en formel som man tycker ser snygg ut. 

Om tre personer får sin egen julklapp är det två som får varandras. Det finns 5*4/2 = 10 sätt att välja ur vilka två som byter med varandra. Man kan bara få sin egen julklapp på ett enda sätt.

Smaragdalena skrev:

Det är bättre att försöka tänka själv än att chansa på att använda en formel som man tycker ser snygg ut. 

Om tre personer får sin egen julklapp är det två som får varandras. Det finns 5*4/2 = 10 sätt att välja ur vilka två som byter med varandra. Man kan bara få sin egen julklapp på ett enda sätt.

Jag har tänkt! Jag tänkte att av de 4 som är kvar kan de alla få olika julklappar på 4! sätt och $\left(\begin{array}{c}4\\ 4\end{array}\right) + \left(\begin{array}{c}4\\ 2\end{array}\right)+\left(\begin{array}{c}4\\ 1\end{array}\right)$ är antalet permutationer där alla, 2 eller 1 av de resterande får den julklapp som de har köpt själva. Och det tog jag bort från 4! och multiplicerar med $\left(\begin{array}{c}5\\ 1\end{array}\right)=5$ för att det upprepar sig för varenda person som vi väljer som får den julklapp som den själv har köpt(100% säkert).

Och sedan försökte jag applicera samma logik på de andra. Men jag förstår inte varför det blir fel, jag hade svårt med att följa Lagunas lösning så jag försökte förenkla den.... Jag vet inte om jag uppfattade det rätt...

Förstod du min lösning för när 3 personer får sin egen julklapp:

Om tre personer får sin egen julklapp är det två som får varandras. Det finns 5*4/2 = 10 sätt att välja ur vilka två som byter med varandra. Man kan bara få sin egen julklapp på ett enda sätt.