Tischordnungen < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:18 So 23.10.2011 | | Autor: | Sin777 |
| Aufgabe | Auf wie viele Arten koennen 5 Personen so an einem runden Tisch mit 12 Plaetzen
platziert werden, dass mindestens ein freier Platz zwischen je zwei Personen bleibt?
Die Plaetze seien dabei nicht unterscheidbar, d.h. drehsymmetrische Anordnungen
gelten als gleich. |
Mein Amsatz: Zunächst einmal handelt es sich um den Fall mit Anordnung, ohne Wiederholung, da zwei verschiedenen Personen nicht der gleiche Stuhl zugeordnet werden kann. Des Weiteren ist es von belang, welcher Person welcher Stuhl zugeordnet ist. Also gibt es zunächst 12*11*10*9*8 Möglichkeiten. Da drehsymmetrische Anordnungen als gleich gelten, könnten ja immer alle einfach eins Weiterrutschen und es wäre das gleiche Ergebnis. Man kann also 1 bis 11 mal weiterrutschen und hat immer noch die gleiche Sitzordnung: (12*11*10*9*8)/11. Stimmt das so weit? Jetzt hänge ich aber, da ich nicht weiß, wie ich dieses Nachbarprinzip mit einbringen kann.
mfg
|
|
| |
|
Hallo Sin777,
hier im Forum laufen gerade mehrere Aufgaben um, wo ein Platz frei bleiben muss. Es ist nicht so einfach, da eine allgemeine Lösung zu finden, aber in diesem Fall sollte es "zu Fuß" leicht gehen.
> Auf wie viele Arten koennen 5 Personen so an einem runden
> Tisch mit 12 Plaetzen
> platziert werden, dass mindestens ein freier Platz
> zwischen je zwei Personen bleibt?
> Die Plaetze seien dabei nicht unterscheidbar, d.h.
> drehsymmetrische Anordnungen
> gelten als gleich.
>
> Mein Amsatz: Zunächst einmal handelt es sich um den Fall
> mit Anordnung, ohne Wiederholung, da zwei verschiedenen
> Personen nicht der gleiche Stuhl zugeordnet werden kann.
> Des Weiteren ist es von belang, welcher Person welcher
> Stuhl zugeordnet ist. Also gibt es zunächst 12*11*10*9*8
> Möglichkeiten. Da drehsymmetrische Anordnungen als gleich
> gelten, könnten ja immer alle einfach eins Weiterrutschen
> und es wäre das gleiche Ergebnis. Man kann also 1 bis 11
> mal weiterrutschen und hat immer noch die gleiche
> Sitzordnung: (12*11*10*9*8)/11. Stimmt das so weit?
Man kann auch gar nicht weiterrutschen, was der 12. Fall ist. Du musst also hier durch 12 teilen.
> Jetzt
> hänge ich aber, da ich nicht weiß, wie ich dieses
> Nachbarprinzip mit einbringen kann.
Nachträglich ist das schwierig.
Ich würde darum ganz anders anfangen.
Wir haben 12 Plätze, im Uhrzeigersinn betrachtet:
............
Als 1. Platz zählen wir immer den, auf dem Person 1 sitzt.
Dann kann auf Platz 12 niemand sitzen. Es genügt darum, wenn wir nur 11 Plätze betrachten, wobei der erste schon an Person 1 vergeben ist und ja auch Platz 2 frei bleiben muss. Bleiben noch 9 Plätze:
.........
Die können nun wie folgt belegt sein:
x.x.x.x..
x.x.x..x.
x.x..x.x.
x..x.x.x.
.x.x.x.x.
x.x.x...x
x.x..x..x
x..x.x..x
.x.x.x..x
x.x...x.x
x..x..x.x
.x.x..x.x
x...x.x.x
.x..x.x.x
..x.x.x.x
Das sind 15 Möglichkeiten. Habe ich eine vergessen?
Natürlich bezeichnet x einen besetzten Platz, ein Punkt einen unbesetzten.
Auf die vier besetzten Plätze können die Personen 2 bis 5 in beliebiger Reihenfolge verteilt werden, wofür es 4! Möglichkeiten gibt.
Insgesamt sind also 15*4!=360 Sitzverteilungen möglich, etwaige Drehungen nicht mitgerechnet.
Die Frage ist nun, wie man das verallgemeinern könnte. Wenn die 15 ein Binomialkoeffizient ist, dann sind nur [mm] \vektor{6\\2},\ \vektor{6\\4},\ \vektor{15\\1} [/mm] und [mm] \vektor{15\\14} [/mm] möglich.
Wären 6 Personen auf die 12 Plätze zu verteilen, so gibt es nur eine einzige Möglichkeit der Platzverteilung (mal 5!=120 Permutationen der Personen 2 bis 6).
Wieviele Möglichkeiten gäbe es bei 5 Personen und 13 Plätzen, wieviele bei 6 Personen und 13 Plätzen?
Aber das ist letztlich ja auch eine Zusatzaufgabe, die gar nicht gefordert war.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:17 Do 27.10.2011 | | Autor: | Sin777 |
Es heißt hier aber zwischen je zwei Personen. Also zwei dürfen schon nebeneinander sitzen, wenn ich das richtig verstanden habe.
Nochmals: Zunächst gibt es 11! Möglichkeiten, wenn man drehsymmetrische Anordnungen nicht mitzählt. Nun gehe ich sukzessiv alle Möglichkeiten durch, bei denen 5, 4 und 3 Personen nebeneinander sitzen.
Es gibt, wenn man Drehsymmetrien außer Acht lässt, genau eine Anordnung, bei der fünf Personen nebeneinander sitzen => 5! Möglichkeiten fallen weg. Neue Lösung: 11! - 5!
Es gibt, wenn man Drehsymmetrien außer Ach lässt, genau 6 Anordnungen, bei der 4 Personen nebeneinander sitzen => 6*5! Möglichkeiten fallen weg.
Zum Schluss gibt es noch 21 Möglichkeiten (7!/(5!*2!)) bei
der drei Personen nebeneinander sitzen
Endergebnis: 11! - 5! - 6*5! - 21*5! = 4560.
|
|
|
| |
|
Hallo,
lies die Aufgabe nochmal.
So, wie Du sie hier eingestellt hast, dürfen zwei Personen nicht nebeneinander sitzen: "mindestens ein freier Platz zwischen zwei Personen".
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:45 Do 27.10.2011 | | Autor: | Sin777 |
Nein, da steht zwischen JE zwei Personen. Ich verstehe unter "je" 2 mal 2. Stimmt das etwa nicht?
|
|
|
| |
|
Hi,
> Nein, da steht zwischen JE zwei Personen. Ich verstehe
> unter "je" 2 mal 2. Stimmt das etwa nicht?
Nein, das stimmt sprachlich nicht. Die Aufgabe ist exakt formuliert. Niemand sitzt unmittelbar neben irgendeiner andern Person, sondern hat links und rechts neben sich garantiert einen freien Platz.
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:14 Do 27.10.2011 | | Autor: | Sin777 |
Ok, dann muss ich meine Lösung ja nur um einen Schritt erweitern. Nochmal komplett:
Nochmals: Zunächst gibt es 11! Möglichkeiten, wenn man drehsymmetrische Anordnungen nicht mitzählt. Nun gehe ich sukzessiv alle Möglichkeiten durch, bei denen 5, 4, 3 und 2 Personen nebeneinander sitzen.
Es gibt, wenn man Drehsymmetrien außer Acht lässt, genau eine Anordnung, bei der fünf Personen nebeneinander sitzen => 5! Möglichkeiten fallen weg.
Es gibt, wenn man Drehsymmetrien außer Acht lässt, genau 6 Anordnungen, bei der 4 Personen nebeneinander sitzen => 6*5! Möglichkeiten fallen weg.
Zum Schluss gibt es noch 21 Möglichkeiten (7!/(5!*2!)) bei
der drei Personen nebeneinander sitzen
und 28 Möglichkeiten, bei denen 2 Personen nebeneinander sitzen.
Endergebnis: 11! - 5! - 6*5! - 21*5! - 28*5! = 1200.
Stimmt das so oder wo liegt mein Fehler?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:33 Do 27.10.2011 | | Autor: | Sin777 |
Das stimmt nicht. Wenn mir was einfällt, dann melde ich mich nochmal :) Danke soweit.
|
|
|
| |
|
Hallo nochmal,
> Ok, dann muss ich meine Lösung ja nur um einen Schritt
> erweitern.
Ja, richtig.
> Nochmal komplett:
>
> Nochmals: Zunächst gibt es 11! Möglichkeiten, wenn man
> drehsymmetrische Anordnungen nicht mitzählt.
Nein. Der Platz, auf dem Person 1 sitzt, wird als Platz #1 gezählt. Person 2 hat dann noch 11 Möglichkeiten, Person 3 hat 10 etc., also insgesamt nur 11*10*9*8=7920 Möglichkeiten, nicht etwa 39916800. Aber Du scheinst auch mit der richtigen Zahl gerechnet zu haben; nur die Darstellung stimmt nicht. Es gibt 11!/7! Möglichkeiten.
> Nun gehe ich
> sukzessiv alle Möglichkeiten durch, bei denen 5, 4, 3 und
> 2 Personen nebeneinander sitzen.
> Es gibt, wenn man Drehsymmetrien außer Acht lässt, genau
> eine Anordnung, bei der fünf Personen nebeneinander sitzen
> => 5! Möglichkeiten fallen weg.
> Es gibt, wenn man Drehsymmetrien außer Acht lässt, genau
> 6 Anordnungen, bei der 4 Personen nebeneinander sitzen =>
> 6*5! Möglichkeiten fallen weg.
> Zum Schluss gibt es noch 21 Möglichkeiten (7!/(5!*2!))
> bei
> der drei Personen nebeneinander sitzen
Bis hierhin kann ich Dir ansonsten folgen. ![[ok]](/images/smileys/ok.gif "[ok]")
> und 28 Möglichkeiten, bei denen 2 Personen nebeneinander
> sitzen.
Die musst Du mal erläutern. Irgendwo sitzen also zwei nebeneinander. Die beiden Plätze neben ihnen sind leer, bleiben also 8 zu besetzende. Hast Du hier berücksichtigt, dass die restlichen drei Personen auch nebeneinander sitzen könnten (und daher schon im vorigen Fall erfasst sind), oder dass von diesen drei noch einmal zwei nebeneinander sitzen (was hieße, dass dieser Fall doppelt erfasst würde)?
> Endergebnis: 11! - 5! - 6*5! - 21*5! - 28*5! = 1200.
> Stimmt das so oder wo liegt mein Fehler?
Im letzten Term.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:43 Do 27.10.2011 | | Autor: | Sin777 |
Also:
Die Anzahl der Möglichkeiten ohne Drehsymmetrien ist 11*10*9*8, da es pro Anordnung ja 12 Möglichkeiten gibt, die identisch sind.
Wie viele Möglichkeiten gibt es nun, dass mindestens zwei Leute nebeneinander sitzen. Die erste Person hat zwölf Möglichkeiten. Die zweite Person hat nun 2 Möglichkeiten, nämlich links oder rechts von der anderen. Für die übrigen bleiben jetzt noch 10*9*8 Möglichkeiten. Das ganze war jetzt aber mit Drehsymmetrien. Ohne muss ich das ganze nochmal durch 12 teilen. D.h. es entfallen 2*10*9*8 Möglichkeiten.
Insgesamt also 11*10*9*8 - 2*10*9*8 = 6480
Das müsste jetzt aber stimmen.
Danke für deine Hilfe :)
|
|
|
| |
|
Hallo Sin777,
> Also:
>
> Die Anzahl der Möglichkeiten ohne Drehsymmetrien ist
> 11*10*9*8, da es pro Anordnung ja 12 Möglichkeiten gibt,
> die identisch sind.
Ja, das ist unbestritten.
> Wie viele Möglichkeiten gibt es nun, dass mindestens zwei
> Leute nebeneinander sitzen. Die erste Person hat zwölf
> Möglichkeiten. Die zweite Person hat nun 2 Möglichkeiten,
> nämlich links oder rechts von der anderen. Für die
> übrigen bleiben jetzt noch 10*9*8 Möglichkeiten. Das
> ganze war jetzt aber mit Drehsymmetrien. Ohne muss ich das
> ganze nochmal durch 12 teilen. D.h. es entfallen 2*10*9*8
> Möglichkeiten.
>
> Insgesamt also 11*10*9*8 - 2*10*9*8 = 6480
>
> Das müsste jetzt aber stimmen.
Nein. Du nimmst jetzt die Personen als unterscheidbar an, was sicher nicht schädlich ist. (Habe ich vorher auch schon getan)
Wer sagt jetzt, dass gerade Person 2 neben Person 1 sitzen muss, oder dass überhaupt jemand neben Person 1 sitzen muss? Vielleicht sind die unmittelbar benachbarten ja auch gerade Person 3 und 5. Der "Abzug" muss deutlich größer sein.
Die konstruktive Lösung aus meinem ersten Post scheint mir immer noch korrekt zu sein: 360 Möglichkeiten.
Jeder andere Weg zum Ergebnis muss doch aber das gleiche Ergebnis liefern.
Grüße
reverend
> Danke für deine Hilfe :)
|
|
|
|
