Induktiver Beweis < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie: In jeder Gruppe von [mm] \vektor{2a-2 \\ a-1} [/mm] Personen gibt es mindestens a Personen, die sich entweder alle untereinander kennen oder alle untereinander nicht kennen.
Hinweis: Verwenden Sie vollständige Induktion über a |
Hallo.
Mir ist bei dieser Aufgabe nicht so recht klar was es bei der vollständigen Induktion überhaupt zu zeigen gilt.
"Kennen" verstehe ich so: A kennt B [mm] \gdw [/mm] B kennt A.
Der Induktionsanfang ist ja im Grunde klar:
a = 1
"Gruppe" von [mm] \vektor{0 \\ 0} [/mm] = 1 Person und diese kennt sich natürlich ;)
im Zweifelsfall noch
a = 2
Gruppe von [mm] \vektor{2 \\ 1} [/mm] = 2 Personen.
Dann gilt:
A kennt B [mm] \wedge [/mm] B kennt A oder
A kennt nicht B [mm] \wedge [/mm] B kennt nicht A.
Ich hoffe die Aufgabe ist verständlich und mir kann jemand dabei helfen.
Vielen Dank schon mal
und viel Grüße
Ludolf
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:31 Fr 03.06.2011 | | Autor: | abakus |
> Beweisen Sie: In jeder Gruppe von [mm]\vektor{2a-2 \\ a-1}[/mm]
> Personen gibt es mindestens a Personen, die sich entweder
> alle untereinander kennen oder alle untereinander nicht
> kennen.
>
> Hinweis: Verwenden Sie vollständige Induktion über a
> Hallo.
> Mir ist bei dieser Aufgabe nicht so recht klar was es bei
> der vollständigen Induktion überhaupt zu zeigen gilt.
>
> "Kennen" verstehe ich so: A kennt B [mm]\gdw[/mm] B kennt A.
>
> Der Induktionsanfang ist ja im Grunde klar:
> a = 1
> "Gruppe" von [mm]\vektor{0 \\ 0}[/mm] = 1 Person und diese kennt
> sich natürlich ;)
>
> im Zweifelsfall noch
> a = 2
> Gruppe von [mm]\vektor{2 \\ 1}[/mm] = 2 Personen.
> Dann gilt:
> A kennt B [mm]\wedge[/mm] B kennt A oder
> A kennt nicht B [mm]\wedge[/mm] B kennt nicht A.
Hallo,
nach dem Induktionsprinzip nehmen wir jetzt also an, dass in einer Menge von [mm]\vektor{2a-2 \\ a-1}[/mm] Personen es mindestens a Personen gibt, die sich untereinander kennen oder eben nicht kennen.
Nun ist zu zeigen, dass unter dieser Voraussetzung auch gilt, dass sich unter [mm]\vektor{2(a+1)-2 \\ (a+1)-1}[/mm] Personen mindestens a+1 Personen ....
Teste erst einmal, wie viele Personen in die bestehende Menge neu dazukommen, wenn die Personenzahl von [mm]\vektor{2a-2 \\ a-1}[/mm] auf [mm]\vektor{2a \\ a}[/mm] steigt. Einige der neu hinzugekommenen Personen könnten die vorhandenen Personen teilweise kennen, eventuell auch teilweise alle nicht kennen.
Gruß Abakus
>
>
> Ich hoffe die Aufgabe ist verständlich und mir kann jemand
> dabei helfen.
>
> Vielen Dank schon mal
> und viel Grüße
> Ludolf
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Danke für deine Hilfe!
Wenn die Personenzahl auf [mm] \vektor{2a \\ a} [/mm] steigt ist die Gruppe ja mehr als 3-mal so groß. Es kommen also eine ganze Menge Personen hinzu, wobei aber die die sich kennen oder eben nicht nur um 1 steigt.
Also entweder (bei "kennen") wird mindestens eine (oder mehrere gekannt und der Satz gilt wieder oder alle kennen sich nicht und es gilt dann "nicht kennen" und es gilt wieder der Satz. Und eben umgekehrt.
Stimmt das soweit oder habe ich da einen Denkfehler?
Grüße
Ludolf
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Di 07.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
