Äquivalenz zweier Probleme < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:27 Sa 29.10.2011 | | Autor: | clemenum |
| Aufgabe | Man gebe einen kombinatorischen Beweis der Äquivalenz folgender Probleme:
(a) Im Parlament eines Landes gibt es 151 Sitze und drei Parteien. Wieviele Möglichkeiten der Sitzverteilung gibt es, sodaß keine Partei eine absolute Mehrheit (d.h., mehr
als 75 Sitze) hat?
(b) Wie viele Möglichkeiten gibt es, ein Paar aus einer 76-elementigen Menschenmenge (ohne Wiederholung) auszuwählen? Dabei soll es auf die Geschlechter der Einzelpersonen natürlich nicht ankommen. Bsp.: (Adam, Rudolf) würde als Paar gelten. |
Einen kombinatorischen Beweis zu geben, versagt mir leider momentan, jedoch kann ich zur ersten Problemstellung folgende Beobachtung abliefern:
Hat die 1. Partei einen Sitz ausgewählt, so kann die 2. Partei nur mehr genau 75 Sitze auswählen, damit die 3. Partei die obige Bedingung erfüllt. D.h. es gibt dafür genau eine Möglichkeit.
Hat die 1. Partei zwei Sitze ausgewählt, so gibt es für die 2. Partei die Möglichkeiten 74 und 75 und damit für die dritte Partei 75 und 74. Also hat die 2. Partei 2 Möglichkeiten für ihre Sitzauswahl.
Hat die 1. Partei drei Sitze, so gibt es für die 2. Partei die Möglichkeiten 73,74,75 und damit für die 3.Partei 75,74,73 Möglichkeiten um die Bedingung zu erfüllen.
Offenbar gilt [mm] $P_2 [/mm] = [mm] f(P_1).$ [/mm] (dabei soll [mm] $P_i$ [/mm] die (Anzahl der Sitzanordnungsmöglichkeiten der) i-te Partei kennzeichnen). Die dritte Partei übernimmt offensichtlich die Anzahl der Möglichkeiten der 2. Partei.
Die Anzahl der Möglichkeiten der Sitzanordnungen nimmt mit wachsender Sitzzahl der 1. Partei linear zu.
Dies lässt sich folgendermaßen verallgemeinern:
Hat die erste Partei k Sitze, so kann es für die zweite Partei nur mehr noch die Möglichkeiten $76-k, [mm] 76-(k-1),\ldots, [/mm] 76-(k-(k-1))=75$ geben.
Da es anfangs 1 Möglichkeiten gibt und zum Schluss genau 75 Möglichkeiten die Sitzzahl der 2. Partei auszuwählen ergibt sich die Gesamtzahl der Anordnungsmöglichkeiten zu: [mm] $\sum_{k=1}^{75} [/mm] k = [mm] \frac{75\cdot 76}{2} [/mm] = [mm] {76\choose 2 }. [/mm] Damit ist das 2. Problem eine Folgerung des ersten.
Offenbar war mein Beweis abgesehen von der kombinatorischen Herangehensweise an das Parteienproblem eine rein rechnerische Folgerung.
Wie könnte man nun - so ist es ja verlangt - mit rein kombinatorischen Argumenten die oben rein rechnerisch gefolgerte Identität beweisen?
Hat hier jemand eine Idee?
|
|
| |
|
Hallo clemenum,
ich hätte da eine Idee, aber die hast du schon selbst verwendet:
> Man gebe einen kombinatorischen Beweis der Äquivalenz
> folgender Probleme:
> (a) Im Parlament eines Landes gibt es 151 Sitze und drei
> Parteien. Wieviele Möglichkeiten der Sitzverteilung gibt
> es, sodaß keine Partei eine absolute Mehrheit (d.h., mehr
> als 75 Sitze) hat?
> (b) Wie viele Möglichkeiten gibt es, ein Paar aus einer
> 76-elementigen Menschenmenge (ohne Wiederholung)
> auszuwählen? Dabei soll es auf die Geschlechter der
> Einzelpersonen natürlich nicht ankommen. Bsp.: (Adam,
> Rudolf) würde als Paar gelten.
> Einen kombinatorischen Beweis zu geben, versagt mir leider
> momentan, jedoch kann ich zur ersten Problemstellung
> folgende Beobachtung abliefern:
>
> Hat die 1. Partei einen Sitz ausgewählt, so kann die 2.
> Partei nur mehr genau 75 Sitze auswählen, damit die 3.
> Partei die obige Bedingung erfüllt. D.h. es gibt dafür
> genau eine Möglichkeit.
>
> Hat die 1. Partei zwei Sitze ausgewählt, so gibt es für
> die 2. Partei die Möglichkeiten 74 und 75 und damit für
> die dritte Partei 75 und 74. Also hat die 2. Partei 2
> Möglichkeiten für ihre Sitzauswahl.
>
> Hat die 1. Partei drei Sitze, so gibt es für die 2. Partei
> die Möglichkeiten 73,74,75 und damit für die 3.Partei
> 75,74,73 Möglichkeiten um die Bedingung zu erfüllen.
>
> Offenbar gilt [mm]P_2 = f(P_1).[/mm] (dabei soll [mm]P_i[/mm] die (Anzahl der
> Sitzanordnungsmöglichkeiten der) i-te Partei
> kennzeichnen). Die dritte Partei übernimmt offensichtlich
> die Anzahl der Möglichkeiten der 2. Partei.
> Die Anzahl der Möglichkeiten der Sitzanordnungen nimmt mit
> wachsender Sitzzahl der 1. Partei linear zu.
> Dies lässt sich folgendermaßen verallgemeinern:
>
> Hat die erste Partei k Sitze, so kann es für die zweite
> Partei nur mehr noch die Möglichkeiten [mm]76-k, 76-(k-1),\ldots, 76-(k-(k-1))=75[/mm]
> geben.
> Da es anfangs 1 Möglichkeiten gibt und zum Schluss genau
> 75 Möglichkeiten die Sitzzahl der 2. Partei auszuwählen
> ergibt sich die Gesamtzahl der Anordnungsmöglichkeiten zu:
> [mm]$\sum_{k=1}^{75}[/mm] k = [mm]\frac{75\cdot 76}{2}[/mm] = [mm]{76\choose 2 }.[/mm]
> Damit ist das 2. Problem eine Folgerung des ersten.
Genau das ist doch die Beweisidee.
Bei der Paarauswahl gehst Du nur in anderer Reihenfolge vor.
Um die Zahl der möglichen Paare zu ermitteln, beginnst Du bei Person 1, der 75 mögliche Partner zugeteilt werden können. Damit sind alle Paarungen, in denen Person 1 vorkommt, erfasst.
Für Person 2 sind daher nur noch 74 neue Paarungen zu erfassen, für Person 3 noch 73 usw.
> Offenbar war mein Beweis abgesehen von der kombinatorischen
> Herangehensweise an das Parteienproblem eine rein
> rechnerische Folgerung.
>
> Wie könnte man nun - so ist es ja verlangt - mit rein
> kombinatorischen Argumenten die oben rein rechnerisch
> gefolgerte Identität beweisen?
> Hat hier jemand eine Idee?
Du ordnest jeden Fall des Parteienproblems dem entsprechenden Fall der Paarbildung zu. Fertig.
Grüße
reverend
|
|
|
|
