matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-SonstigesElementargeometrie
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]