Hi und gleichzeitig sorry wegen dieser blöden Frage, wenn 4 Leute wichteln, und zwar so, das sich niemand selber beschenkt, wie viele Möglichkeiten gibt es? Ich bin nicht gebildet genug um das zu lösen. Jetzt müsst Ihr mir helfen :D Irgendwie ist mein Denkmuster für solche simplen aufgaben nicht geeignet... Sorry nochmal für den sinnlosen Threat. Und ja, es sind meine Hausaufgaben aus der 7. Klasse die ich zur Zeit besuche, falls sich wer wundert. Schönes WE allen.
9 https://de.wikipedia.org/wiki/Fixpunktfreie_Permutation#Anzahl Als grobe Näherung geht n! / e, hier also 1·2·3·4 / 2.7 was ca. 8.88 ist —> liegt bereits gut am richtigen Ergebnis 9.
:
Bearbeitet durch User
Vielen vielen Dank! Ging auch echt zügig mit der Antwort. Kein Wunder, dass ich nicht so leicht aufs Ergebnis gekommen bin.
n*n-n hätte ich gedacht... =4*4-4=12 Lösung kann ja nur ganzzahlig sein... So mit 8,88 Möglichkeiten kann man da nix anfangen 1 2 3 4 1 - 2 - 3 - 4 - Die Kombinationen rechts oben entsprechen nicht denen links unten denn es ist ein Unterschied ob 1 der 2 was schenkt oder die 2 der 1 was schenkt. Die 1 braucht der 1 nix zu schenken, usw.
:
Bearbeitet durch User
Mike B. schrieb: > n*n-n hätte ich gedacht... So war auch mein Denkansatz, aber irgendwie... da gibts nen englischen Spruch: I can't wrap my head around this. Der erklärt das besser, als wie ich das jemals könnte. Die Lösung von Johann scheint aber auch sehr plausibel aufzugehen (zumindest für mich). Und Johann schrieb ja auch "Näherung". Und mit e in der Formel gibts eh immer ein krummes Ergebnis. Man könnte eine Tabelle mit allen Möglichkeiten aufstellen oder Excel ein wenig rechnen lassen. Ich bin aber faul und Excel ist noch nicht so mein Gebiet.
:
Bearbeitet durch User
IncreasingVoltage .. schrieb: > Man könnte eine Tabelle mit allen Möglichkeiten aufstellen oder Excel > ein wenig rechnen lassen. Ich bin aber faul und Excel ist noch nicht so > mein Gebiet. schreib auf 1-2 2-1 1-3 3-1 usw. und zähle
Mike B. schrieb: > n*n-n hätte ich gedacht... kleiner Tip: Das ist auch die Lösung für gegeben: n Mannschaften gesucht: Wieviele Spiele mit Hin- und Rückrunde?
:
Bearbeitet durch User
Mike B. schrieb: > So mit 8,88 Möglichkeiten kann man da nix anfangen NACK. Du denkst zu klein. Für gerade n aufrunden, für ungerade n abrunden: n = 2: 2! / e ~ 0.736 => 1 n = 3: 3! / e ~ 2.207 => 2 n = 4: 4! / e ~ 8.829 => 9 n = 5: 5! / e ~ 44.146 => 44 n = 6: 6! / e ~ 264.873 => 265 n = 7: 7! / e ~ 1854.112 => 1854 n = 8: 8! / e ~ 14832.899 => 14833 n = 9: 9! / e ~ 133496.092 => 133496 n = 10: 10! / e ~ 1334960.916 => 1334961 n = 11: 11! / e ~ 14684570.077 => 14684570 n = 12: 12! / e ~ 176214840.928 => 176214841 n = 13: 13! / e ~ 2290792932.067 => 2290792932 n = 14: 14! / e ~ 32071101048.937 => 32071101049 n = 15: 15! / e ~ 481066515734.059 => 481066515734 n = 16: 16! / e ~ 7697064251744.944 => 7697064251745 n = 17: 17! / e ~ 130850092279664.062 => 130850092279664 Und jetzt vergleichen mit den Werten aus OEIS :-)) http://oeis.org/A000166 Ab n >= 18 reicht die Genauigkeit der von mir verwendete double-Arithmetik nicht mehr aus. Und Wiki kennt natürlich auch die explizite Formel, aus der man z.B. auch die o.g. Rundung bei der Näherung ableiten kann sowie auch den gemachten Fehler betragsmäßig nach oben abschätzen.
:
Bearbeitet durch User
Teo D. schrieb: > Mike B. schrieb: >> Das ist auch die Lösung für > > Hände schütteln, Gläser anstoßen... Nein, dafür gibt es n·(n-1)/2 Möglichkeiten, das wächst aber nur quadratisch und nicht wie n!.
Johann L. schrieb: > Teo D. schrieb: >> Mike B. schrieb: >>> Das ist auch die Lösung für >> >> Hände schütteln, Gläser anstoßen... > > Nein, dafür gibt es n·(n-1)/2 Möglichkeiten, das wächst aber nur > quadratisch und nicht wie n!. n*(n-1)/2 ist die Berechnung für ein Turnier, jede Mannschaft spielt einmal gegen jede Mannschaft, d.h. ohne Rückrunde ich schrieb extra mit Hin- und Rückrunde, Weil im vom TE ja auch Schenken in beide Richtungen gefordert wurde. Und dann darf man das nicht halbieren. Eine andere Begründung/Berechnung für n+n-n=n*(n-1) in diesem Fall ist: Wenn jeder von den 4 Leuten jedem anderen etwas schenken soll, dann gibt es 4 Personen, die jeweils 3 anderen Personen was schenken sollen. Also 4*3=12 Geschenke/Möglichkeiten. =n*n-n Damit ist die vorgeschlagene Lösung n! / e = 4! / e = 8.88 ~ 9 falsch.
:
Bearbeitet durch User
Mike B. schrieb: > gibt es 4 Personen, die jeweils 3 anderen Personen was schenken sollen. Es gibt 4 Personen, und jede schenkt einer anderen Person etwas. Und zwar so, dass es 4 Schenker und 4 Beschenkte gibt, und niemand sich selbst etwas schenkt. Vielleicht hab aber Wichteln nicht verstanden; in meiner Heimat ist dieser Brauch nicht sehr üblich.
Johann L. schrieb: > Vielleicht hab aber Wichteln nicht verstanden; in meiner Heimat ist > dieser Brauch nicht sehr üblich. Mit anderen Worten: Die Wichtung des Wichtelns ist in Deiner Heimat nicht sehr hoch. MfG Paul
Johann L. schrieb: > Es gibt 4 Personen, und jede schenkt einer anderen Person etwas. Und > zwar so, dass es 4 Schenker und 4 Beschenkte gibt, und niemand sich > selbst etwas schenkt. Genau! Ich schick mal (n-1)! ins Rennen!
Johann L. .. schrieb Datum: 19.11.2017 14:02: > Es gibt 4 Personen, und jede schenkt einer anderen Person etwas. Und > zwar so, dass es 4 Schenker und 4 Beschenkte gibt, und niemand sich > selbst etwas schenkt. Das wären dann 4 Geschenke, da muss man nix rechnen... IncreasingVoltage .. schrieb: > Hi und gleichzeitig sorry wegen dieser blöden Frage, > > wenn 4 Leute wichteln, und zwar so, das sich niemand selber beschenkt, > wie viele Möglichkeiten gibt es? So wie ich das verstanden hab schenkt jeder jedem etwas aber natürlich nicht sich selbst.
Wiki sagt zu Wichteln: "Dabei wird durch zufällige Auswahl für jedes Gruppenmitglied ein anderes Gruppenmitglied bestimmt, von dem es dann beschenkt wird." Also 4 Schenkende und 4 Beschenkte, also 4 Geschenke, hast Recht, Johann L.! Auf die Art des Wichtelns jibbet nix zu rechnen...
IncreasingVoltage .. schrieb: > wenn 4 Leute wichteln, und zwar so, das sich niemand selber beschenkt, > wie viele Möglichkeiten gibt es? Das errechnet man mit Hilfe der Kombinatorik. Siehe hier: https://de.wikipedia.org/wiki/Kombinatorik
Bei jedem mal Händeschütteln werden 2 Geschenke bewegt....
Mike B. schrieb: > Johann L. .. schrieb Datum: 19.11.2017 14:02: >> Es gibt 4 Personen, und jede schenkt einer anderen Person etwas. Und >> zwar so, dass es 4 Schenker und 4 Beschenkte gibt, und niemand sich >> selbst etwas schenkt. > > Das wären dann 4 Geschenke, da muss man nix rechnen... Es geht um die Anzahl der Beschenkungsmöglichkeiten für alle. Bei 3 Leuten A, B, C gibt es z.B. nur 2 Möglichketen: A -> B -> C -> A A -> C -> B -> A Bei 4 Leuten sind der wie gesagt 9. Wenn du da nix rechnen musst - schön.
IncreasingVoltage .. schrieb: > Man könnte eine Tabelle mit allen Möglichkeiten aufstellen oder Excel > ein wenig rechnen lassen. Ich bin aber faul und Excel ist noch nicht so > mein Gebiet. Für Excel wäre ich auch zu faul, dann noch lieber von Hand ;-) Hab's stattdessen mal in Haskell programmiert:
1 | import Data.List |
2 | import Control.Monad |
3 | import System.Environment |
4 | |
5 | wichtel xs = wichtel' xs xs |
6 | where wichtel' [] [] = [[]] |
7 | wichtel' bs xs = do |
8 | x <- xs |
9 | guard $ x /= head bs |
10 | ys <- wichtel' (tail bs) (delete x xs) |
11 | return $ x : ys |
12 | |
13 | main = do |
14 | n <- liftM (read . head) getArgs |
15 | putStrLn $ "wichtel " ++ show n ++ ":" |
16 | mapM print $ wichtel [1..n] |
Das Programm wird mit der Anzahl der Teilnehmer als Argument aufgerufen. Beispielaufruf:
1 | $ wichtel 4 |
2 | wichtel 4: |
3 | [2,1,4,3] |
4 | [2,3,4,1] |
5 | [2,4,1,3] |
6 | [3,1,4,2] |
7 | [3,4,1,2] |
8 | [3,4,2,1] |
9 | [4,1,2,3] |
10 | [4,3,1,2] |
11 | [4,3,2,1] |
Bei 4 Teilnehmern gibt es also 9 Möglichkeiten, wie die Geschenke ihre Besitzer wechseln können, ohne dass einer der Teilnehmer sein eigenes Geschenk zurückerhält. Die Datei im Anhang enthält die Ausgaben des Programms für 2 bis 7 Teilnehmer.
Wie viele Geschenke muss eine Person mitbringen, um Jedem ein Geschenk zu überreichen?
Die Originalfrage war: IncreasingVoltage .. schrieb: > Hi und gleichzeitig sorry wegen dieser blöden Frage, > > wenn 4 Leute wichteln, und zwar so, das sich niemand selber beschenkt, > wie viele Möglichkeiten gibt es? Wieviele Möglichkeiten für was? Das ich ein bestimmtes Geschenk bekomme? Oder für was? *Die Aufgabenstellung ist unklar.* - Beim Wichteln laut Wiki gibt jeder genau ein Geschenk ab. Das wird hingestellt und dann wird ausgelost, wer welches Geschenk bekommt. 4 Geschenke werden an 4 Beschenkte verteilt. - jeder schenkt jedem etwas n*n, jeder gibt 4 und jeder bekommt 4 also 16 Geschenke - jeder schenkt jedem ausser sich selbst etwas n*n-n=n*(n-1), jeder gibt 3 und jeder bekommt 3 also 12 Geschenke Wenn man die Anzahl der Möglichkeiten der Verteilung der Geschenke an alle Personen wissen will, mögt ihr mit n!/e Recht haben. Aber wie gesagt, die Aufgabenstellung und damit die Frage des op ist unklar.
Zum Berechnen für kleine Zahlen ist auch die Rekursion a(1) = 0 a(n) = n·a(n-1) + (-1)^n für n > 1 ganz nett, die übrigens bereits Leonhard Euler kannte und bewies. Die Aufgabe gibt's zum Beispiel auch als: "n Leute geben an einer Garderobe ihren Mantel ab. Wie groß ist die Wahrscheinlichkeit, dass bei zufälliger Ausgabe der Mäntel niemand seinen eigenen Mantel erhält?" Diese ist Anzahl der fixpunktfreien Permutationen dividiert durch die Anzahl aller Permutationen, und strebt mit wachsender Anzahl an Leuten fix gegen 1/e also ca. 37%.
Teo D. schrieb: > Wie viele Geschenke muss eine Person mitbringen, um Jedem ein Geschenk > zu überreichen? Das ist mir zu kompliziert!
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.