Forum: Offtopic Kurze und einfache Frage: 4 Leute wichteln, wie viele Kombinationen gibt es?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von IncreasingVoltage .. (increasingvoltage)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von IncreasingVoltage .. (increasingvoltage)


Bewertung
0 lesenswert
nicht lesenswert
Vielen vielen Dank!

Ging auch echt zügig mit der Antwort.

Kein Wunder, dass ich nicht so leicht aufs Ergebnis gekommen bin.

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von IncreasingVoltage .. (increasingvoltage)


Bewertung
0 lesenswert
nicht lesenswert
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
von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von Teo D. (teoderix)


Bewertung
0 lesenswert
nicht lesenswert
Mike B. schrieb:
> Das ist auch die Lösung für

Hände schütteln, Gläser anstoßen....

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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!.

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von Johann L. (gjlayde) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
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.

von Paul B. (paul_baumann)


Bewertung
1 lesenswert
nicht lesenswert
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

von Max M. (jens2001)


Bewertung
0 lesenswert
nicht lesenswert
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!

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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...

von Harald W. (wilhelms)


Bewertung
0 lesenswert
nicht lesenswert
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

von Teo D. (teoderix)


Bewertung
0 lesenswert
nicht lesenswert
Bei jedem mal Händeschütteln werden 2 Geschenke bewegt....

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

von Teo D. (teoderix)


Bewertung
0 lesenswert
nicht lesenswert
Wie viele Geschenke muss eine Person mitbringen, um Jedem ein Geschenk 
zu überreichen?

von Mike B. (mike_b97) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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%.

von Harald W. (wilhelms)


Bewertung
0 lesenswert
nicht lesenswert
Teo D. schrieb:

> Wie viele Geschenke muss eine Person mitbringen, um Jedem ein Geschenk
> zu überreichen?

Das ist mir zu kompliziert!

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.