Erweiterte Permutation? < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:36 Di 30.08.2016 | | Autor: | zarkus |
| Aufgabe | | Es gibt 100 Stühle (die im Kreis aufgebaut sind) für 100 Personen. Wieviele Möglichkeiten gibt es, wenn jede Person jedesmal auf einem anderen Stuhl sitzt und jedes mal einen anderen Nachbarn hat. (jede Person darf nie den gleichen Nachbarn haben) |
Mir ist gar nicht klar wie ich die Nachbarn mit einbeziehen kann.
...jede Person auf anderem Stuhl würde bedeuten 100! aber das kann bedeuten, dass es Wiederholungen in den Nachbarn gibt?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Es gibt 100 Stühle (die im Kreis aufgebaut sind) für 100
> Personen. Wieviele Möglichkeiten gibt es, wenn jede Person
> jedesmal auf einem anderen Stuhl sitzt und jedes mal einen
> anderen Nachbarn hat. (jede Person darf nie den gleichen
> Nachbarn haben)
> Mir ist gar nicht klar wie ich die Nachbarn mit
> einbeziehen kann.
> ...jede Person auf anderem Stuhl würde bedeuten 100! aber
> das kann bedeuten, dass es Wiederholungen in den Nachbarn
> gibt?
Guten Tag zarkus
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
ich denke, dass du mit diesen Angaben keine klar definierte
Aufgabe beschrieben hast. Mindestens bleiben da bei mir gewisse
Zweifel.
Die Sache mit den 100 im Ring aufgestellten Sitzplätzen scheint
zwar klar und ist bei derartigen Kombinatorik-Aufgaben sogar
recht häufig.
Als "Möglichkeiten" sollen wohl Sitzordnungen für die 100
Personen gemeint sein, also bijektive Zuordnungen von der
Menge der 100 Personen zu den 100 verfügbaren Plätzen.
Diese insgesamt 100! Zuordnungen entsprechen anzahlmäßig
den sämtlichen Permutationen einer Menge von 100 Elementen.
Die Forderung, dass jede Person bei jeder zulässigen Anordnung
auf einem anderen Stuhl sitzen soll, schränkt die gesamte
Anzahl der zulässigen Sitzordnungen sofort auf maximal 100
(hundert, nicht etwa 100!) ein.
Die Einschränkung, dass jede der 100 Personen bei keiner
neuen Sitzordnung einen Nachbarn von einer anderen Sitzordnung
haben darf, ist dann vielleicht gar nicht mehr so sehr einschränkend,
wie man sich zunächst denken könnte. Beachte dabei aber, dass
jede der Personen in der ringförmigen Anordnung nicht nur einen,
sondern stets zwei Sitznachbarn hat (einen links und einen rechts).
Ich könnte mir vorstellen, dass es möglich sein könnte, eine Menge von
100 Sitzordnungen mit den geforderten Eigenschaften zu finden.
Dabei lasse ich mich aber gern eines besseren belehren. Je kleiner
die mögliche Maximalzahl der Sitzordnungen, umso mehr werde
ich die Aufgab als "interessant" würdigen ....
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:00 Di 30.08.2016 | | Autor: | zarkus |
Hallo Al-Chwarizmi!
Danke für deine Antwort!
um es noch mal zu erklären: jede Person soll an allen möglichen Plätzen sitzen - Einschränkung ist nur, dass die Nachbarn nie dieselben sind.
Wenn A auf Platz 1 und B auf Platz 2 und C auf Platz 3 sitzt, dann in der nächsten Möglichkeit zB A auf Platz 2 rutscht dürfen B und C nie mehr die Nachbarn sein...
Vllt ist es jetzt etwas "interessanter"?  Danke schon mal für eure Hilfe
|
|
|
| |
|
> Hallo Al-Chwarizmi!
>
> Danke für deine Antwort!
>
> um es noch mal zu erklären: jede Person soll an allen
> möglichen Plätzen sitzen - Einschränkung ist nur, dass
> die Nachbarn nie dieselben sind.
>
> Wenn A auf Platz 1 und B auf Platz 2 und C auf Platz 3
> sitzt, dann in der nächsten Möglichkeit zB A auf Platz 2
> rutscht dürfen B und C nie mehr die Nachbarn sein...
(Beachte zunächst einmal, dass C gar kein "Nachbar" von A
ist, wenn C auf Platz 3 und A auf Platz 1 ist ! ...... )
Naja, erst mal geht es mir auch nur darum, deine eigentliche
Frage richtig zu verstehen. Zu diesem Zweck möchte ich
einmal vorschlagen, die Anzahl der Sitzplätze auf 26
(anstatt 100) zu setzen. Grund: Unser Alphabet hat 26
Buchstaben.
Es soll also genau 26 Plätze geben. Nummerieren wir sie mit den
Zahlen 1 bis und mit 26. Der Platz 1 hat dann die Nachbarn
2 und 26. Sind in der "Grundanordnung"auf den Plätzen 1, 2
und 3 die Personen A, B und C und auf dem letzten Platz
(Nr. 26) die Person Z, dann hat z.B. B die Nachbarn A und C.
Die Person A hat aber die Nachbarn Z und B.
Ich habe nun deine Aufgabe folgendermassen verstanden:
Eine Grundmenge G hat 26 (oder allgemeiner: g) Elemente.
Gesucht ist eine (maximale) Menge M von Permutationen der 26
(oder allgemein g) Elemente mit folgenden Eigenschaften:
(1.) Jedes der g Elemente nimmt jeden der g möglichen
Plätze (die von 1 bis g nummeriert sind) höchstens in
einer einzigen der in der Menge M vorkommenden Permutationen
ein.
(2.) Zwei der g Elemente der Grundmenge G dürfen in
höchstens einer der in M enthaltenen Permutationen
"benachbart" sein.
Aus der Bedingung (1.) ergibt sich nun, wie ich schon
ausgeführt habe, dass die Menge M auch höchstens g
Elemente (=Permutationen der Menge G) enthalten kann.
Eventuell willst du aber (unter dieser neuen Betrachtungs-
weise) auf die Forderung (1.) verzichten. Du würdest dann
also nur nach der maximalen Anzahl der "zyklischen
Permutationen" einer Menge von g Elementen fragen,
welche untereinander "nachbarfremd" sind.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:33 Do 01.09.2016 | | Autor: | zarkus |
Ja, soweit richtig Bedingung 1 kann unter Umständen vernachlässigt werden bzw is zweitrangig - mir ist klar das A nicht auf allen Plätzen sitzen kann wenn die Bedingung 2 zutreffen soll - genau so war die Aufgabe gemeint... sorry wg meiner schlechten Aufgabenstellung...
|
|
|
| |
|
> Ja, soweit richtig Bedingung 1 kann unter Umständen
> vernachlässigt werden bzw is zweitrangig - mir ist klar
> das A nicht auf allen Plätzen sitzen kann wenn die
> Bedingung 2 zutreffen soll - genau so war die Aufgabe
> gemeint... sorry wg meiner schlechten Aufgabenstellung...
Guten Abend !
So können wir also die Aufgabe neu so formulieren:
Wir betrachten eine (endliche) Grundmenge G von 100
(oder allgemein g) Elementen.
P sei die Menge aller g! Permutationen von G.
Gesucht ist eine Teilmenge M von P mit möglichst vielen
Elementen, welche jedoch folgende Eigenschaft besitzen
soll:
(E) je zwei Elemente x,y von G (mit x≠y) dürfen in
höchstens einer der in M enthaltenen Permutationen
"zyklisch benachbart" (modulo g) sein.
Für die weitere Bearbeitung der Frage ist es sinnvoll, einem
bestimmten ausgewählten Element von G jeweils einen
bestimmten Platz in der zyklischen Anordnung zuzuordnen,
also etwa Person A stets auf Platz 1.
Leicht kann man nun eine Obergrenze für die maximale
Anzahl der "zyklisch nachbarfremden" Permutationen
anzugeben. Im Fall g=100 hat z.B. die Person A jedesmal
genau 2 Nachbarn. Da insgesamt nur 99 Personen als
mögliche Sitznachbarn zur Verfügung stehen, kann es
höchstens [mm] $\lfloor 99/2\rfloor\ [/mm] =\ 49$ Permutationen geben,
die "zyklisch nachbarfremd" sind.
LG , Al-Chwarizmi
|
|
|
| |
|
> Leicht kann man nun eine Obergrenze für die maximale
> Anzahl der "zyklisch nachbarfremden" Permutationen
> anzugeben. Im Fall g=100 hat z.B. die Person A jedesmal
> genau 2 Nachbarn. Da insgesamt nur 99 Personen als
> mögliche Sitznachbarn zur Verfügung stehen, kann es
> höchstens [mm]\lfloor 99/2\rfloor\ =\ 49[/mm] Permutationen
> geben,
> die "zyklisch nachbarfremd" sind.
Nach etwas Ausprobieren bin ich zur Vermutung gekommen,
dass die angegebene Obergrenze wohl auch wirklich erreichbar
ist. Jedenfalls trifft dies für kleine Werte von g offenbar zu.
Für die Werte g = 1, 2 ist nicht einmal eine einzige Permutation
"zyklisch nachbarfremd". Für g = 3 oder 4 jeweils eine einzige,
wovon man sich leicht überzeugen kann. Für g=5 gibt es 2,
z.B. ABCDE und ACEBD . Auch für g=6 gehen maximal 2, zum
Beispiel ABCDEF und ACEBFD.
Für g=7 kommen z.B. in Frage: ABCDEFG, ACEGBDF, ADGCFBE.
Mehr als 3 kommen aber ja sicher nicht in Frage.
Nun wäre meine Vermutung, dass die Maximalzahl
$\ m\ =\ [mm] \lfloor\,g\,/2\ [/mm] -\ [mm] 1\,\rfloor$
[/mm]
an "zyklisch nachbarfremden Permutationen" stets auch erreichbar
ist.
Für die anfänglich vorgegebenen Anzahl g=100 (von Stühlen
im Kreis und Personen) käme man also auf
$\ m\ =\ [mm] \lfloor\,100\,/2\ [/mm] -\ [mm] 1\,\rfloor\ [/mm] =\ 49$
LG , Al-Chwarizmi
|
|
|
|
