Elementargeometrie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zu einer Gesellschaft sind n Leute eingeladen.
a) Begründen Sie, dass mindestens zwei Gäste gleich oft die Hand geschüttelt haben, wenn jeder mindestens einmal die hand gibt.
b) Jeder Gast möge genau r Bekannte treffen. Zeigen Sie, dass dies nur möglich ist, wenn das Produkt n*r eine gerade Zahl ist. |
bei teil a habe ich gedacht dass jeder mindestens einmal höchstens n-1 mal die Hand gibt. Also: 1[mm] \le [/mm]x[mm] \le [/mm](n-1) komme aber nicht dadrauf warum zwei gleich oft die hand gibt.
teil b komme ich überhaupt nicht weiter
|
|
| |
|
> Zu einer Gesellschaft sind n Leute eingeladen.
> a) Begründen Sie, dass mindestens zwei Gäste gleich oft
> die Hand geschüttelt haben, wenn jeder mindestens einmal
> die hand gibt.
>
> b) Jeder Gast möge genau r Bekannte treffen. Zeigen Sie,
> dass dies nur möglich ist, wenn das Produkt n*r eine gerade
> Zahl ist.
> bei teil a habe ich gedacht dass jeder mindestens einmal
> höchstens n-1 mal die Hand gibt. Also: 1[mm] \le [/mm]x[mm] \le [/mm](n-1)
> komme aber nicht dadrauf warum zwei gleich oft die hand
> gibt.
Du musst nur nochmals lesen, was Du als Betreff geschrieben hattest: "Dirichletsches Schubfachprinzip". Es gibt für den Wert von $x$ genau $n-1$ Schubfächer (die möglichen Werte $1, 2, [mm] \ldots [/mm] , n-1$, aber $n$ (d.h. also $>n-1$) Personen: daher muss es mindestens ein "Schubfach" (d.h. mindestens eine Anzahl "Handgeben") geben, in dem sich mehr als eine Person befindet.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:44 Mi 09.04.2008 | | Autor: | sakarsakir |
erstmal danke für deine bemühungen.
also gut mal sehen ob ich es richtig verstehe. wenn ich zum beispiel 5 personen habe, kann eine person höchstens viermal die hand geben. heißt es jetzt wenn ich auf das viemal hand geben fünf personen verteile das es mindestens bei einem andgeben zwei personen gibt??
aber es gehören ja zum hand geben im mer zwei personen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:53 Do 10.04.2008 | | Autor: | Marcel |
Hallo Sakarsakir,
> erstmal danke für deine bemühungen.
>
> also gut mal sehen ob ich es richtig verstehe. wenn ich zum
> beispiel 5 personen habe, kann eine person höchstens
> viermal die hand geben. heißt es jetzt wenn ich auf das
> viemal hand geben fünf personen verteile das es mindestens
> bei einem andgeben zwei personen gibt??
> aber es gehören ja zum hand geben im mer zwei personen.
Machen wir es ruhig mal mit Deinem Beispiel. Wir haben $n=5$ Personen. Wir gehen auch davon aus, dass sich zwei Personen, die sich begrüßt haben (schon die Hand geschüttelt haben), sich nicht nochmal begrüßen werden (was bei 5 Personen auch relativ realitätsnahe ist, solange keiner an Gedächtnisschwund oder so leidet  ).
Nennen wir die mal [mm] $P_1,...,P_5$. [/mm] Nun haben wir die Schubladen [mm] $S_1,...,S_4$, [/mm] wobei in der Schublade [mm] $S_j$ [/mm] eine Person [mm] $P_k$ [/mm] sitzen soll, wenn die Person [mm] $P_k$ [/mm] dann $j$-Mal die Hand gegeben habe.
[mm] $P_1$ [/mm] begrüße [mm] $P_2$, [/mm] wir setzen jetzt mal einfach [mm] $P_2$ [/mm] in [mm] $S_1$ [/mm] (damit oben nicht immer $j=k$ gilt, wenn [mm] $P_j$ [/mm] in [mm] $S_k$ [/mm] sitzt).
[mm] $P_1$ [/mm] begrüße nun [mm] $P_4$.
[/mm]
Nun begrüße [mm] $P_1$ [/mm] auch [mm] $P_5$ [/mm] und [mm] $P_1$ [/mm] setzt sich mal in [mm] $S_3$.
[/mm]
[mm] $P_4$ [/mm] begrüßt [mm] $P_5$ [/mm] und [mm] $P_4$ [/mm] setzt sich in [mm] $S_2$.
[/mm]
Momentaner Stand der Dinge:
[mm] $P_2$ [/mm] sitzt in [mm] $S_1$ [/mm] (hat also einer Person die Hand gegeben, und zwar war das [mm] $P_1$)
[/mm]
[mm] $P_4$ [/mm] sitzt in [mm] $S_2$ [/mm] (hat also zwei Personen die Hand gegeben, und das waren [mm] $P_{1,5}$)
[/mm]
[mm] $P_1$ [/mm] sitzt in [mm] $S_3$ [/mm] (hat also drei Personen die Hand gegeben, und zwar waren die [mm] $P_{2,4,5}$)
[/mm]
Draußen sind also noch [mm] $P_{3,5}$. [/mm] Begrüßt [mm] $P_3$ [/mm] nun eine Person, die nicht [mm] $P_2$ [/mm] ist, so schickt er ggf. die andere Person eine Schublade "höher", muss sich dann aber zu [mm] $P_1$ [/mm] gesellen. Dem kann er dann ausweichen, indem er dann [mm] $P_1$ [/mm] begrüßt, aber dann muss er ins schon besetzte [mm] $S_2$ [/mm] usw.
.
.
.
Das könnte man jetzt komplett duchspinnen, aber es läuft im Prinzip auf folgendes Hinaus:
Du hast $n$ Personen, und die verteilst Du auf maximal $n-1$ Schubfächer (o.B.d.A. kannst Du also annehmen, Dir stünden $n-1$ Schubfächer zur Verfügung; aber mehr kann es nicht geben, da eine Person sich ja nicht selbst begrüßt), d.h. Du hast $m < n$ Schubfächer, dann gibt es natürlich ein Schubfach, dass mindestens zwei Objekte enthält.
Also nochmal mit Deinem obigen Beispiel:
Du hast $5$ Personen [mm] $P_{1,2,3,4,5}$ [/mm] und steckst diese in $4$ Schubladen [mm] $S_{1,2,3,4}$, [/mm] wobei von den $5$ niemand übrig bleiben darf (jeder muss ja einmal jemanden begrüßen); denn eine jede der $5$ Personen kann ja maximal $4$ andere Personen begrüßen (auch, wenn das manche tun, sich selbst zu begrüßen gilt hier nicht ).
Klar, dass dann in einer Schublade zwei Personen stecken müssen (im Sinne von mindestens zwei) (und ich hoffe, dass die Schubladen hier groß genug sind *g*)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:38 Do 10.04.2008 | | Autor: | Marcel |
Hi,
> b) Jeder Gast möge genau r Bekannte treffen. Zeigen Sie,
> dass dies nur möglich ist, wenn das Produkt n*r eine gerade
> Zahl ist.
> bei teil a habe ich gedacht dass jeder mindestens einmal
> höchstens n-1 mal die Hand gibt. Also: 1[mm] \le [/mm]x[mm] \le [/mm](n-1)
> komme aber nicht dadrauf warum zwei gleich oft die hand
> gibt.
>
> teil b komme ich überhaupt nicht weiter
hier kannst Du z.B. folgendes machen: Wir nennen die Personen wieder [mm] $P_1,...,P_n$.
[/mm]
Wir schreiben [mm] $(P_j,P_k) \in [/mm] B$, wenn die Person [mm] $P_j$ [/mm] die Person [mm] $P_k$ [/mm] kennt (für $j [mm] \not=k$).
[/mm]
Dann sei [mm] $B_j:=\{k \in \{1,2,...,n\}\setminus\{j\}: (P_j,P_k) \in B\}$, [/mm] d.h. [mm] $B_j$ [/mm] enthält die Nummern aller Bekannten von $j$; für $j=1,...,n$.
Dann gilt [mm] $|B_j|=r$ [/mm] nach Voraussetzung für jedes $j [mm] \in \{1,...,n\}$.
[/mm]
Damit:
[mm] $n*r=\sum_{j=1}^n |B_j|=\sum_{j=1}^n \left|\{k \in \{1,2,...,n\}\setminus\{j\}: (P_j,P_k) \in B\}\right|=\left|\bigcup_{j=1}^{n} \bigcup_{k=1 \mbox{ und } k \not=j}^{n} \{(P_j,P_k) \in B\}\right|$
[/mm]
und die letztgenannte Menge [mm] $R:=\bigcup_{j=1}^{n} \bigcup_{k=1 \mbox{ und } k \not=j}^{n} \{(P_j,P_k) \in B\}$ [/mm] kann nur eine gerade Anzahl von Elementen haben, aus dem einfachen Grund (einer vorliegenden Symmetrie):
[mm] $(P_j,P_k) \in [/mm] B [mm] \gdw (P_k,P_j) \in [/mm] B$ (beachte, dies gilt für $k [mm] \not=j$; [/mm] d.h. [mm] $(P_j,P_j) \notin [/mm] B$, also: man zählt sich selbst nicht zu den Bekannten, die man trifft (weil man sich selbst nicht trifft, oder weil man sich selbst nicht kennt, den Grund dafür kannst Du Dir selbst aussuchen ))
Also die Person [mm] $P_j$ [/mm] kennt [mm] $P_k$ [/mm] genau dann, wenn [mm] $P_k$ [/mm] auch [mm] $P_j$ [/mm] kennt.
(Ansonsten macht die Aufgabe auch keinen Sinn, denn bei drei Personen könnte dann ja jede Person genau eine andere kennen, also [mm] $P_1$ [/mm] kennt [mm] $P_2$, [/mm] aber [mm] $P_2$ [/mm] nicht [mm] $P_1$, [/mm] aber dafür [mm] $P_3$ [/mm] und [mm] $P_3$ [/mm] kennt dann vielleicht [mm] $P_2$, [/mm] aber nicht [mm] $P_1$ [/mm] und hier wäre dann $r=1$ und $n=3$ und $n*r=3*1=3$ sicher nicht gerade. Also kennen heißt hier: Sich gegenseitig kennen!)
Damit solltest Du Dir klarmachen können, dass auch gilt:
[mm] $(P_j,P_k) \in [/mm] R$ (was eh nur für $j [mm] \not=k$ [/mm] gelten kann) gilt genau dann, wenn [mm] $(P_k,P_j) \in [/mm] R$. Und die Konsequenz dieser Tatsache ist eben, dass $R$ nur eine gerade Anzahl von Elementen haben kann, und diese Anzahl ist eben, wie oben gesehen, gerade $=n*r$.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:24 Do 10.04.2008 | | Autor: | sakarsakir |
danke ich wäre von alleine nie im leben darauf gekommen!!!!
gruß
sakarsakir
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:07 Do 10.04.2008 | | Autor: | Somebody |
> > b) Jeder Gast möge genau r Bekannte treffen. Zeigen Sie,
> > dass dies nur möglich ist, wenn das Produkt n*r eine gerade
> > Zahl ist.
Man kann dies auch als Anwendung des ersten Satzes über Graphentheorie auffassen, den Euler formuliert hat: Die Summe der Ordnungen aller Ecken eines (ungerichteten) Graphen ist das doppelte der Kantenzahl. Grund: Es wird beim Summieren der Ordnungen jede Kante doppelt gezählt (da sie ja stets zwei Ecken verbindet).
Hier wären also $n$ Ecken (=Personen) mit derselben Ordnung $r$ (=kennen sich) gegeben ("regulärer Graph"). Die Summe aller Ordnungen der $n$ Ecken ist somit [mm] $n\cdot [/mm] r$ und dies ist, gemäss Euler, das Doppelte der Kantenzahl, also jedenfalls eine gerade Zahl.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:04 Fr 11.04.2008 | | Autor: | aless |
| Aufgabe |
Man kann dies auch als Anwendung des ersten Satzes über Graphentheorie auffassen, den Euler formuliert hat: Die Summe der Ordnungen aller Ecken eines (ungerichteten) Graphen ist das doppelte der Kantenzahl. Grund: Es wird beim Summieren der Ordnungen jede Kante doppelt gezählt (da sie ja stets zwei Ecken verbindet).
Hier wären also Ecken (=Personen) mit derselben Ordnung (=kennen sich) gegeben ("regulärer Graph"). Die Summe aller Ordnungen der Ecken ist somit und dies ist, gemäss Euler, das Doppelte der Kantenzahl, also jedenfalls eine gerade Zahl. |
ich wollte fargen ob du die zweite zum schluss angegebene lösung für b etw. ausfürhlicher erklären könntest.
lg aless
|
|
|
| |
|
>
> Man kann dies auch als Anwendung des ersten Satzes über
> Graphentheorie auffassen, den Euler formuliert hat: Die
> Summe der Ordnungen aller Ecken eines (ungerichteten)
> Graphen ist das doppelte der Kantenzahl. Grund: Es wird
> beim Summieren der Ordnungen jede Kante doppelt gezählt (da
> sie ja stets zwei Ecken verbindet).
>
> Hier wären also $n$ Ecken (=Personen) mit derselben Ordnung $r$
> (=kennen sich) gegeben ("regulärer Graph"). Die Summe aller
> Ordnungen der Ecken ist somit [mm] $n\cdot [/mm] r$ und dies ist, gemäss Euler,
> das Doppelte der Kantenzahl, also jedenfalls eine gerade
> Zahl.
> ich wollte fragen ob du die zweite zum schluss angegebene
> lösung für b etw. ausführlicher erklären könntest.
.. und ich dachte, diese Lösung empfehle sich gerade wegen ihrer Kürze
Also, um etwas auszuholen: Ein (ungerichteter) Graph ist eine endliche Menge von Ecken und Kanten. Die Kanten verbinden jeweils zwei Ecken (eventuell sogar eine Ecke mit sich selbst): diese beiden Ecken sind quasi die Endpunkte der betreffenden Kante.
Die Zahl der Kanten, die in einer Ecke des Graphen zusammentreffen, nennt man die Ordnung dieser Ecke.
Zählt man die Ordnungen aller Ecken zusammen, so erhält man, wie Euler als erster feststellte, das Doppelte der Kantenzahl des Graphen, weil man ja auf diese Weise jede Kante zweimal zählt. Einmal mit der Ordnung ihres einen, ein zweites mal mit der Ordnung ihres anderen Endpunktes.
Wir können bei der Teilaufgabe b) nun die $n$ Personen als Ecken und die Beziehung "sind Bekannte" als Kanten eines solchen (ungerichteten) Graphen auffassen. Eine Kante soll also zwei Ecken (=Personen) genau dann verbinden, wenn sie Bekannte sind.
Da, gemäss Aufgabenstellung, jede der $n$ Personen genau $r$ Bekannte hat, ist die Ordnung aller Ecken dieses Graphen dieselbe, nämlich $r$. Die Summe aller Ordnungen der $n$ Ecken des Graphen ist daher gleich [mm] $n\cdot [/mm] r$ und, gemäss Euler, gleich der doppelten Kantenzahl. Wir brauchen nicht zu wissen, wieviele Kanten dieser Graph besitzt, um sagen zu können: es handelt sich jedenfalls um eine natürliche Zahl, deren Doppeltes [mm] $n\cdot [/mm] r$ somit eine gerade Zahl sein muss. Was zu zeigen war.
|
|
|
|
