Ich kann nichts was ihr hoffentlich könnt

Sir_Tom · 11. März 2004 um 19:31

…Hi Leute!

Unser Lehrer hat uns letzte Mathestunde nur so zum Spass mal eine Aufgabe zum unserem jetzigen Thema Wahrscheinlichkeitsrechnung gegeben. Nach 5 Minuten hat er eingesehen, dass das zu heftig für die Schule ist. Jetzt sass ich hier den ganzen Tag rum, und überlege mir, wie man die Aufgabe wohl anpackt, und ob ich sie nicht doch im Rätselforum stellen soll. Also, hier ist sie nun:

25 Personen kommen ins Kino, darunter sind 12 Pärchen und ein Single. Nun sollen diese in einem Kino mit 60 Sitzplätzen (Zur Vereinfachung geht man von einer Reihe mit 60 Plätzen aus) so plaziert werden, dass auf jeden Fall die Partner nebeneinander sitzen. Auf wie viele unterschiedliche Möglichkeiten lassen sich die 12 Paare und der Single im Kino anordnen? Und verdammt nochmal warum???

Viel Spaß mit dieser wunderschönen Aufgabe und einen schönen Abend,

Greetz, Sir Tom

anon92079305 · 11. März 2004 um 21:46

Hallo Sir Tom,

mir hat die Aufgabe irgendwie gefallen und ich hab mir zunächst mal folgendes überlegt (keine Ahnung ob das richtig ist):

60 Sitze 25 Personen = 60*59* … 37*36
Ergibt 8,05*10^41

Jetzt zu den Pärchen (ich nehme der einfachheit halber an Sie sitzen in einem Kreis)
Für Paar 1 gibt es 60 freie Plätze für die 1. Person und 2 Möglichkeiten für die 2. Person sich zu setzen
Paar 1 setzt sich 60*2=120
Paar 2 setzt sich 120*58*2=13920
Paar 3 setzt sich 13920*56*2
…
Paar 12 setzt sich 9,14*10^21*38*2=
Bleiben für den Single noch 36 weitere Möglichkeiten sich zu setzen
Single 6,95*10^23* 36 =2,5*10^25

Ergibt 2,5*10^25 Möglichkeiten

Übrigens macht es einen Unterschied ob sich der Single zuerst oder am Ende setzt.

Gruss
Nils

Saruman · 11. März 2004 um 22:48

Hallo!

Ich habe mir das mal so überlegt:
Der Single hat 60 verschiedene Plätze zur Auswahl, bleiben 59 wenn er platz genommen hat. Da der Rest Paare sind, verbleiben effektiv 58 Sitzplätze, also 29 Möglichkeiten (da ja alle Paare nebeneinander sitzen wollen) insgesamt für alle Paare sich zu platzieren.
Dabei ist die Reihenfolge der Platzwahl ausschlaggebend und dass Wiederholungen unmöglich sind. Meiner Meinung nach handelt es sich um eine Permutation ohne Wiederholung, d.h. die Formel

(n)*k! (sprich: n über k mal Fakultät k)
(k)
müsste zur Anwendung kommen, wobei n Anzahl der Möglichkeiten und k Anzahl der Paare. Also
(29)*12!=1.190713477*10²⁵
(12)

Da nun der Mann rechts und die Frau links sitzen kann sowie vice versa müsste man das Ergebniss verdoppeln. Es gibt also 2.381426954*10²⁵ Möglichkeiten.

Bitte nicht schlagen, wenn es falsch ist
Aber du kannst mal bitte deinen Lehrer fragen, wie das richtige Ergebnis lautet. Das würde mich sehr interessieren.

mfG Dirk

anonym1_d1f5ab · 11. März 2004 um 23:40

Dann will ich meine Theorie auch noch in den Raum schmeissen!

2 Plätze gehen durch den Single immer verloren. Und es gibt 60 Möglichkeiten wo der sitzen kann.

Die Möglichkeiten die es für ein Paar gibt sind 58/2, da dann wieder zwei Plätze besetzt sind ist die nächste Möglichkeit 56/2 (54/2; 52/2 etc. bla bla)

Und so komme ich auf:

60*29*28*27*26*25*24*23*21*20*19*18*17= 2,54 * 10^19

Hoffe mal das das stimmt…

mfg matze

jns4sen · 12. März 2004 um 03:05

Allgemeine Lösung
Hallo,

für N Sitzplätze, p Pärchen und s Singles habe ich mir folgende Lösung überlegt:

A(N, p, s) = (N-p|p) \* p!\*2^p \* (N-2p|s) \* s!

, wobei (a|b) eine Abkürzung für a!/((a-b)!*b!) das heißt a über b) ist.

Für den speziellen Fall mit N=60, p=12, s=1 folgt somit

A(60, 12, 1)
= (48|12) \* 12! \* 2^12 \* (36|1) \* 1!
= 69 668 534 468 \* 479 001 600 \* 4 096 \* 36 \* 1
= 4 920 804 234 337 392 053 452 800
≈ 4.92 \* 10^24

Der Faktor (N-p|p) gibt an, wie viele Möglichkeiten existieren, p benachbarte Sitzplatzpaare zu wählen. Der Faktor 12! berücksichtigt, dass die Paare auf diesen (N-p|p) Sitzplatzpaaren in verschiedener Reihenfolge angeordnet sein können und der Faktor 2^12 trägt dem Umstand Rechnung, dass es egal ist, ob die Frau oder der Mann auf der linken (bzw. rechten) Seite sitzt. Schließlich gibt es für die Singles (N-2p|s)*s! Möglichkeiten, sich auf die verbleibenden N-2p Sitzplätze zu setzen.

Viele Grüße
Jens

jns4sen · 12. März 2004 um 03:32

Hallo Nils,

Jetzt zu den Pärchen (ich nehme der einfachheit halber an Sie
sitzen in einem Kreis)
Für Paar 1 gibt es 60 freie Plätze für die 1. Person und 2
Möglichkeiten für die 2. Person sich zu setzen
Paar 1 setzt sich 60*2=120

soweit richtig (, falls im Kreis gesessen wird).

Paar 2 setzt sich 120*58*2=13920

und hier kommt der Fehler. Du setzt nämlich voraus, dass sich die dritte Person nicht unmittelbar neben die erste oder die zweite setzt. Falls sich die dritte Person dennoch direkt neben das bereits sitzende Paar setzt, gibt es für deren Partner nur noch 1 anstatt 2 Möglichkeiten, sich zu setzen.

Paar 3 setzt sich 13920*56*2

Hier wird es nun noch komplizierter. Nicht nur, dass hierfür vorausgesetzt wird, dass sich die 5. Person nicht neben eine bereits sitzende Person setzt (dies galt ja bereits im Schritt zuvor), sondern es wird noch zusätzlich angenommen, dass die beiden bereits sitzenden Paare keinen einzelnen Sitzplatz eingeschlossen haben.

…
Paar 12 setzt sich 9,14*10^21*38*2=

im ungünstigsten Fall haben die anderen 11 Paare 10 Sitzplätze isoliert, die vom 12. Paar nicht mehr besetzt werden können.

Bleiben für den Single noch 36 weitere Möglichkeiten sich zu
setzen
Single 6,95*10^23* 36 =2,5*10^25

Ergibt 2,5*10^25 Möglichkeiten

Durch das Nichtbeachten der isolierten Sitzplätze wird deine Lösung um den Faktor 5 vergrößert (, was dem Physiker als grobe Abschätzung allemal ausreichen tut).

Übrigens macht es einen Unterschied ob sich der Single zuerst
oder am Ende setzt.

Das kann nicht sein, die Anzahl der Möglichkeiten, auf die Sitzplätze verteilt zu SEIN (beachte: Zustand, nicht Vorgang) ist von der Reihnfolge des Sich-Hinsetzens unabhängig. Dass man sich bei der Herleitung der mathematischen Formel eine zeitliche Reihenfolge denkt, in welcher sich die Personen hinsetzen, ist lediglich eine Denkhilfe. Dass dein mathematisches Modell für verschiedene Reihenfolgen verschiedene Ergebnisse liefert, ist bereits ein hinreichndes Kriterium dafür, dass es falsch sein muss.

Viele Grüße
Jens

jns4sen · 12. März 2004 um 04:25

Hallo Dirk,

Ich habe mir das mal so überlegt:
Der Single hat 60 verschiedene Plätze zur Auswahl, bleiben 59
wenn er platz genommen hat. Da der Rest Paare sind, verbleiben
effektiv 58 Sitzplätze

Die Überlegungen werden wesentlich einfacher, wenn man zuerst die Paare anordnet und den Single ganz zum Schluss (für das Endergebnis ist die Reihenfolge des Anordnens unerhblich).

, also 29 Möglichkeiten (da ja alle
Paare nebeneinander sitzen wollen) insgesamt für alle Paare
sich zu platzieren.

Du bildest also Paare aus benachbarten Sitzen. Allderding hast du lediglich die Sitzplatz-Paarbildung (1,2)(3,4)(5,6)…(57,58) berücksichtigt. Ein (Personen)-Paar dürfte sich demnach lediglich so hinsetzn, dass die kleinere Nummer eine ungerade Zahl ist. Es muss aber bedacht werden, dass sich das (Personen)-Paar XY auch auf die Plätze (2,3) oder (4,5) usw. hinsetzen kann. Es fehlen dir also ganz viele Möglichkeiten.

Dabei ist die Reihenfolge der Platzwahl ausschlaggebend und
dass Wiederholungen unmöglich sind. Meiner Meinung nach
handelt es sich um eine Permutation ohne Wiederholung, d.h.
die Formel

(n)*k! (sprich: n über k mal Fakultät k)
(k)
müsste zur Anwendung kommen, wobei n Anzahl der Möglichkeiten
und k Anzahl der Paare.

Die Formel wäre tatsächlich korrekt, falls die oben erwähnten Fälle (2,3) usw. ausgeschlossen wären. Falls diese nicht ausgeschlossen sind (wie hier in der vorliegenden Aufgabe), so muss die Formel modifiziert werden. Anstelle von (n|k)*k! tritt der Faktor (N-k|k)*k! mit N=60. Der Grund für N=60 (anstelle von N=59): Der Single wird zum Schluss angeordnet, so dass für die Paare alle 60 Sitzplätze zur Verfügung stehen. Der Single hat dann auf jeden Fall (egal wie sich die Paare hinsetzen) genau 36 Möglichkeiten, sich zu setzen. Denkt man sich den Single als ersten hingesetzt, so wird die anzusetzende Formel für die Paare davon abhängig, auf welchen Platz sich der Single gesetzt hat. Dies ist unnötig kompliziert, und da die Anzahl der Sitzanordnungen nicht von der Reihenfolge des Sich-Setzens abhängt, wählt man halt die einfachste Reihenfolge.

Also
(29)*12!=1.190713477*10²⁵
(12)

Hups; da hat sich ein Rechenfehler eingeschichen.

(29|12)\*12! = 24 858 235 898 496 000 ≈ 2.5 \* 10^16

Da nun der Mann rechts und die Frau links sitzen kann sowie
vice versa müsste man das Ergebniss verdoppeln.

Nein. Nicht verdoppeln, sondern ver-2^12-fachen. Jedes Paar kann unabhängig voneinander entweder den Mann oder die Frau links sitzen haben. Macht also einen Faktor 2^12=4096.

Es gibt also
2.381426954*10²⁵ Möglichkeiten.

Bitte nicht schlagen, wenn es falsch ist

Schlagen nicht, aber helfen gern!

Gruß
Jens

jns4sen · 12. März 2004 um 04:35

Hi Matze,

Und so komme ich auf:

60*29*28*27*26*25*24*23*21*20*19*18*17= 2,54 * 10^19

du hast (versehentlich?) den Faktor 22 ausgelassen. Ansonsten entspricht dein Lösungsvorschlag demjenigen von Dirk, nur dass du einen Faktor 2 (mit dem Dirk berücksichtigen wollte, dass entweder die Frau oder der Mann auf der rechten Seite sitzen kann) weniger hast. Siehe also meinen Kommentar zu Dirks Antwort.

Hoffe mal das das stimmt…

Die Hoffnung stirbt zuletzt

Viele Grüße
Jens

Saruman · 12. März 2004 um 09:53

Hallo!

Danke für deine Ausführungen, das hat mich überzeugt.

(29)*12!=1.190713477*1025
(12)

Hups; da hat sich ein Rechenfehler eingeschichen.
(29|12)*12! = 24 858 235 898 496 000 ≈ 2.5 *10^16

Hopla, wie peinlich. Man hätte natürlich den allgemeinen Binomialkoeffizienten anwenden müssen.

mfG Dirk

Oliver_a32c43 · 12. März 2004 um 15:08

Hi Jens,

Der Faktor (N-p|p) gibt an, wie viele
Möglichkeiten
existieren, p benachbarte Sitzplatzpaare zu
wählen

Wie kommst du da drauf?

Gruß
Oliver

Martin · 12. März 2004 um 15:33

Hallo Oliver,

Der Faktor (N-p|p) gibt an, wie viele
Möglichkeiten existieren, p benachbarte Sitzplatzpaare zu wählen

Wie kommst du da drauf?

das habe ich mich im ersten Moment auch gefragt, aber wenn Du etwas drüber nachdenkst, wird es sofort klar.

Wenn zwei Dreiercliquen „AAA“ und „BBB“ eine 10er-Reihe im Kino zur Verfügung haben, dann sind z. B. „AAA—BBB-“ und „----AAABBB“ mögliche Konfigurationen. Die Anzahl aller Konfigurationen ist offensichtlich genauso groß wie bei dem Problem, daß zwei Singles „S“ und „T“ eine _Sechser_reihe zur Verfügung haben: Den beiden obigen Beispiele haben die Single-Entsprechungen „S—T-“ und „----ST“ (klar?). Hier kennt man die Möglichkeiten-Anzahl jedoch: (6 über 2). Jetzt mußt Du Dir nur noch überlegen, wie man von den Dreiercliquen und der 10er-Reihe auf die Zahl 6 kommt: Klar, 2 Dreiercliquen [allegmeine: k C-er Cliquen] benötigen einfach 4 [allgemein: k (C–1)] Plätze mehr als 2 Singles, deshalb: 10 – 4 = 6.

Ergebnis: Stehen k C-er-Cliquen eine n-er Sitzreihe zur Verfügung, dann gibt es

( n - k (C–1) ) 
( )
( k )

Konfigurationen. Für Paare (C = 2) folgt daraus:

( n - k ) 
( )
( k )

Gruß
Martin

Enno_Sandner_66c4aa · 12. März 2004 um 16:29

Hallo,
anschaulich betrachtet kann man bei N Plätzen und p Paaren die z.B. Rechtssitzenden eines Paares als isolierte Menge von p Plätzen betrachten. Jede Auswahl von Plätzen für die Linkssitzenden aus den verbleibenden N-p Plätzen, kann zur einer Lsg. gemacht werden, indem man die Rechtssitzenden wieder einfügt. Bsp.:
N=6, p=2. Die Plätze: PPPPPP werden gesplittet in PPPP und RR (sozusagen reserviert für Rechtssitzende). Jetzt wählen wir zwei Sitzplätze für die Linkssitzenden PLLP und fügen die Rechtsitzenden passend ein PLRLRP. Umgekehrt läßt sich jede Lsg. wieder in die gesplittete Form bringen.

Gruss
Enno