www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - Elementargeometrie
Elementargeometrie < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Elementargeometrie: dirichletsches schubfachprinzp
Status: (Frage) beantwortet Status 
Datum: 19:20 Mi 09.04.2008
Autor: sakarsakir

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

        
Bezug
Elementargeometrie: a)
Status: (Antwort) fertig Status 
Datum: 20:18 Mi 09.04.2008
Autor: Somebody


> 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.



Bezug
                
Bezug
Elementargeometrie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                        
Bezug
Elementargeometrie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Elementargeometrie: Teil b)
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Elementargeometrie: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:24 Do 10.04.2008
Autor: sakarsakir

danke ich wäre von alleine nie im leben darauf gekommen!!!!

gruß
sakarsakir

Bezug
                
Bezug
Elementargeometrie: b) Graphentheorie
Status: (Mitteilung) Reaktion unnötig Status 
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.



Bezug
                        
Bezug
Elementargeometrie: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                                
Bezug
Elementargeometrie: Antwort
Status: (Antwort) fertig Status 
Datum: 13:25 Fr 11.04.2008
Autor: Somebody


>
> 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.


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]