Die Mathe-Redaktion - 19.10.2017 16:22 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 861 Gäste und 23 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Stern Mathematik: Dirichlets Schreibtisch
Freigegeben von matroid am Fr. 10. Mai 2002 18:29:55
Verfasst von matroid -   5272 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Man kann es sich vorstellen: Johann Peter Gustav Lejeune Dirichlet, (1805 bis 1859), sitzt an seinem Schreibtisch in seinem Berliner Arbeitszimmer und sucht nach einem überzeugenden Argument, mit dem er einen Beweis abschließen kann.
Es gelingt aber nicht recht, und schließlich lehnt er sich etwas zurück, nimmt seine Brille ab, putzt sie und setzt sie wieder auf.
Sein Blick fällt auf den Aufsatz des Schreibmöbels, an dem er sitzt, und er erfreut sich, wie schon oft, an diesem schönen Stück, mit den vielen kleinen Schubladen und den reichhaltigen Intarsien aus verschiedenen Edelhölzern.
Nach diesem kurzen Moment der Entspannung wendet er sich erneut seiner Arbeit zu. Direkt aus der Feder formulieren sich nun die Sätze, mit denen er seinen Beweis zu Ende führt.



Später, nach seinem Tod, wurden Dirichlets Vorlesungen über Zahlentheorie von seinem Schüler Richard Dedekind veröffentlicht - das war 1863.
Darin findet sich die erste bekannte Formulierung dessen, was wir heute Schubfachprinzip nennen. Dirichlet selbst hatte dem keinen besonderen Namen gegeben.
Schubfachprinzip:
Werden nk+1 Perlen auf n Schubfächer verteilt, so gibt es wenigstens ein Schubfach mit mehr als k Perlen.
Das Schubfachprinzip wirkt vollkommen trivial und macht keinerlei Aufhebens von sich. Aber tatsächlich kann man mit ihm die unglaublichsten Aussagen beweisen. Dieses Prinzip heißt manchmal auch "Taubenschlagprinzip" nach dem englischen "pigeonhole principle".

Was kann man damit beweisen?
  1. Unter 3 Personen haben mindestens 2 das gleiche Geschlecht.
     
  2. Von 13 Personen haben 2 im gleichen Monat Geburtstag.
Sagte ich doch, absolut trivial.

Nun aber (allmählich) steigernd:
  1. Zeige, daß es zwei Deutsche mit der gleichen Anzahl von Haaren gibt!
     
  2. Weil das Licht ausgefallen ist, mußt Du im Dunkeln in der Kommodenschublade zwei gleichfarbige Socken suchen. Deine Socken sind entweder schwarz oder weiß, und Du machst Dir nie die Mühe, die Socken zu Paaren zu rollen. Wieviele Socken mußt Du herausnehmen, um garantiert ein gleichfarbiges Paar zu haben? Wie viele Socken müßtest Du herausnehmen, wenn Du garantiert ein schwarzes Paar haben willst? [Lösung]
    Anmerkung: Um Socken entnehmen zu können, muß man wissen, daß Socken in der Schublade sind. Die Formulierung 'Schublade mit Socken' legt die Reichhaltigkeit nur scheinbar nahe. Um diese Interpretationsmöglichkeit auszuschalten, sei präzisiert, daß sich in der Sockenschublade je 5 Paar schwarze und weiße Socken befinden.
     
  3. In jeder Gruppe von mindestens zwei Personen gibt es zwei, die die gleiche Anzahl von Bekannten innerhalb dieser Gruppe haben.[Lösung]
     
  4. Unter 52 natürlichen Zahlen kann man zwei Zahlen auswählen, deren Summe oder deren Differenz durch 100 teilbar ist. Ist diese Behauptung auch für 51 Zahlen richtig?
     
  5. Unter 9 Gitterpunkten der Ebene gibt es drei, deren Schwerpunkt ebenfalls ein Gitterpunkt ist. [Lösung]
     
  6. Unter je fünf Punkten, die in einem Quadrat der Seitenlänge 4 liegen, gibt es zwei, die einen Abstand <= 3 haben.
     
  7. Angenommen in einem Dorf leben 15 Männer und 10 Frauen. Jede Frau ist mit einer bestimmten Anzahl von Männern befreundet. Der König des Landes kommt in das Dorf, und bestimmt 10 Männer, die heiraten sollen.
    Warum sind mindestens 60 Freundschaften (zwischen Frauen und Männern) nötig, damit, egal welche 10 Männer ausgewählt werden, jede Frau einen Mann heiraten kann, mit dem sie auch befreundet ist?
Um das S.P. zur Anwendung zu bringen, muß man entscheiden, was die Schubladen, und was die Perlen sein sollen. Darin besteht die Kunst.

Die Zahlentheorie kennt eine Reihe von Aussagen, die sich mit Hilfe des Schubfachprinzips beweisen lassen:
  1. Ein Primzahl der Form 4n+1 ist Summe zweier Quadratzahlen.
     
  2. Jede natürliche Zahl ist Summe von vier Quadratzahlen


Mehr über das S.P. und weitere interessante, gelöste Aufgaben:
  1. von Robert Strich, Seite 11 ff [postscript],
    Ausschnitte daraus das S.P. betreffend bei math4u.de.
    [Beide Autoren widmen sich (gemeinsam) der Vorbereitung von Schülern für den Wettbewerb der Deutschen Mathematik Olympiaden, und ihre Seiten sind eine Schatztruhe voller mathematischer Geheimnisse und Tricks! Unter der Adresse math4u.de findet man 470+ Mathematik-Aufgaben zum Training in Vorbereitung auf Olympiaden und Wettbewerbe, mit ausführlichen Lösungen.


Trennlinie

Lösung der Sockenaufgabe:
Wir teilen die Socken in zwei Kategorien (Schubfächer) ein, in die Kategorie der weißen und die der schwarzen Socken; das sind die 2 Schubfächer.
  1. Wenn Du 3 Socken entnimmst, und sie in die 2 Schubfächer sortierst, dann kommen garantiert zwei Socken in die gleiche Schublade. Du hast entweder zwei weiße oder zwei schwarze Socken gefunden.
  2. Wenn Du aber zwei Socken Deiner Lieblingsfarbe 'schwarz' suchst, so mußt Du im schlimmsten Fall 12 Socken ziehen, denn die ersten 10 könnten ja alle weiß sein.


Lösung des Bekanntenschaftsproblems:
Eine Person kommt in Schubfach i, wenn sie i Bekannte hat. Es gibt n Personen und n Schubfächer (nämlich 0, 1, ..., n-1). Aber die Schubfächer 0 und n-1 können nicht gleichzeitig besetzt sein.

Lösung Gitterpunkte:
Der Schwerpunkt von 3 Punkten x, y, z der Ebene errechnet sich als arithmetisches Mittel der Punktkoordinaten. Der Schwerpunkt ist dann ein Gitterpunkt, wenn die Summen x1+y1+z1 und x2+y2+z2 durch 3 teilbar sind.
Nun definiere Schubfächer und beschrifte sie mit (i,j), i,j Î{0,1,2}, den möglichen Resten bei Division durch 3. Das ergibt also 3² = 9 Schubfächer.
Als Perlen betrachte die Koordinatensummen von je 3 der 9 Gitterpunkte. Es gibt "9 über 3" = 84 Möglichkeiten diese Kombinationen zu bilden.
[Anm.: es ist nicht verlangt, daß die 9 Gitterpunkte alle verschieden sind. Sollten sich unter den 9 Punkten einige mehrfach befinden, dann unterscheide sie künstlich, etwa durch Zuordnung einer Farbe.]

Eine solche Perle kommt in Schubfach (i,j), wenn die Summe der ersten Koordinaten = i mod 3 und die Summe der zweiten Koordinaten = j mod 3 ist.

Verteile die 84 Perlen auf die 9 Schubfächer.
Wenn das Schubfach (0,0) nicht leer ist, dann sind wir fertig.

Nehmen wir also an, das Schubfach (0,0) sei leer und führen diese Annahme zu einem Widerspruch.

Dazu wieder eine Überlegung: Wenn 3 Punkte ein Dreieck bilden, dessen Schwerpunkt ein Gitterpunkt ist, dann ändert sich daran nichts, wenn man die Punktkoordinaten modulo 3 rechnet. Diese Aussage formulieren wir als

Lemma 1: Der Schwerpunkt des Dreiecks aus den Punkten x,y,z, mit
x = (x1,x2),
y = (y1,y2),
z = (z1,z2),
ist genau dann ein Gitterpunkt, wenn das für x'=r3(x), y'=r3(y), z'=r3(z) gilt.
Dabei ist r3(x) die Abbildung von IR³->IR³, die einen Punkt x = (x1,x2) abbildet auf (x'1,x'2), wobei x'i der Divisionsrest von xi beim Teilen durch 3 ist.
Beweis: Zur Übung überlassen. ;-))

Wenn das Schubfach (0.0) leer ist, dann bedeutet das:
  1. daß alle Schwerpunkte von Dreiecken aus den 9 Punkten keine Gitterpunkte sind,
  2. daß es keine 3 gleichen unter den Gitterpunkten gibt.
Aus 1. und dem Lemma 1 folgert man, daß dann auch die transformierten Punkte keine Dreiecke mit einem Gitterpunkt als Schwerpunkt bilden.
Betrachen wir ab jetzt ausschließlich die auf {0,1,2}² transformierten Punkte.

Aus 2. folgert man, daß es mindestens 5 verschiedene Punkte geben muß. Das gilt für alle möglichen Wahlen von 9 Punkten. Es gilt - und darauf kommt es an - auch in {0,1,2}².

Nun benötigen wir ein weiteres

Lemma 2: Unter 5 Gitterpunkten der Ebene sind stets zwei, deren Verbindungslinie einen Gitterpunkt enthält. Insbesondere ist dieser Gitterpunkt der Mittelpunkt der Verbindungsstrecke.

Beweis: Mit dem Schubfachprinzip: Wir wählen beliebige 4 Gitterpunkte A, B, C, D in der Ebene. Nun füge diesen 4 Punkten A, B, C, D einen fünften Punkt P hinzu. Durch den neuen Punkt werden mit den 4 vorhanden Punkten 4 Verbindungslinien definiert.
Bilde (ähnlich wie oben) Schubladen (i,j) und lege eine durch 2 Punkte
x = (x1,x2) und
y = (y1,y2)
bestimmte Verbindungsstrecke in die Schublade (i,j), wenn die koordinatenweise Summe der beiden Punkte in der ersten Koordinate gleich i modulo 2 ist und in der zweiten gleich j modulo 2, also
x1 + y1 = i mod 2 und
x2 + y2 = j mod 2.
Es gibt 4 Schubladen und 4 Perlen, nämlich die Verbindungsstrecken von dem neuen Punkt P zu den 4 vorhandenen Punkten.

Wenn die Klasse (0,0) nicht leer ist, dann sind wir fertig.

Ansonsten gibt es eine Klasse, die zwei Perlen enthält (verteile 4 Perlen auf 3 Schubfächer).
Die Perlen bedeutet zwei (ungeordnete) Punktepaare (P,A) und (P,B).
Da beide in der gleichen Klasse sind, gilt:
p1 + a1 = p1 + b1 mod 2
p2 + a2 = p2 + b2 mod 2
Daraus ersieht man, daß
a1 = b1 mod 2
a2 = b2 mod 2
und schließlich:
a1 + b1 = 0 mod 2
a2 + b2 = 0 mod 2
Das heißt aber nichts anderes, als daß die Punkte A und B einen Gitterpunkt in der Mitte der Verbindungsstrecke haben.
Das ist ein Widerspruch zur Annahme, daß die Schublade (0,0) leer ist.
qed Lemma 2.

[Anmerkung: Die Verbindungsstrecke zweier zusammenfallender Punkte besteht nur aus dem Punkt. Ihr Mittelpunkt ist wiederum der Punkt selbst.]

Zurück zum Beweis für Schwerpunkte.
Sobald 5 verschiedene Punkte in der Ebene gewählt werden, ist der Mittelpunkt mindestens einer Verbindungsstrecke zweier Punkte ein Gitterpunkt.
Wir müssen aber in {0,1,2}² 9 mal einen Punkt auswählen, davon (mindestens) 5 verschiedene (wegen 1.).

Wenn wir genau 5 Punkte wählen, und kein Punkt dreifach ausgewählt wird (weil ja (0,0) leer ist), dann werden 4 Punkte doppelt und einer einfach gewählt.
Wir finden dann immer 3 Punkte (einen doppelt), die auf einer Geraden liegen.
Wählen wir 6 oder mehr Punkte, dann gilt das gleiche, aber möglicherweise sind dann die drei Punkte auf einer Geraden sogar verschieden.

In {0,1,2}² können wir folglich nicht umhin, mit der Wahl von 9 Punkten, darunter mindestens 5 verschiedene, mindestens drei Punkte auf einer Geraden zu wählen, in deren Mitte ein Gitterpunkt liegt. Dieser Gitterpunkt ist aber der Schwerpunkt von x', y', z'.
Dies steht im Widerspruch zum Lemma 1.
QED

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Schüler aufwärts :: Beweistechnik :: Leicht verständlich :: Mathematik :: Schubfachprinzip :
Dirichlets Schreibtisch [von matroid]  
Man kann es sich vorstellen: Johann Peter Gustav Lejeune Dirichlet, (1805 bis 1859), sitzt an seinem Schreibtisch in seinem Berliner Arbeitszimmer und sucht nach einem überzeugenden Argument, mit dem er einen Beweis abschliessen kann. Es gelingt aber nicht recht, und schließlich lehnt er sich
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 5272
 
Aufrufstatistik des Artikels
Insgesamt 119 externe Besuche in 2013 [Anzeigen]
DomainAnzahlProz
http://google.de9277.3%77.3 %
http://www.gutefrage.net65%5 %
http://www.sweetpacks-search.com54.2%4.2 %
http://google.nl21.7%1.7 %
http://google.com32.5%2.5 %
http://de.search.yahoo.com10.8%0.8 %
http://www.ecosia.org10.8%0.8 %
http://ch.search.yahoo.com10.8%0.8 %
http://images.google.de10.8%0.8 %
http://google.at21.7%1.7 %
http://search.conduit.com10.8%0.8 %
http://google.ch10.8%0.8 %
http://suche.web.de21.7%1.7 %
http://suche.t-online.de10.8%0.8 %

Häufige Aufrufer in früheren Monaten
Insgesamt 87 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2016 (34x)http://google.de/url?sa=t&rct=j&q=
2015.01 (11x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCIQFjAB
2012.01 (8x)http://google.de/url?sa=t&rct=j&q=schubfach summe durch 3
2013.01 (6x)http://google.de/url?sa=t&rct=j&q=schubfachprinzip 5 socken
2014-2016 (6x)http://www.gutefrage.net/frage/mathe-formeln-verstehen-
2012.04 (5x)http://google.de/url?sa=t&rct=j&q=punkte ebene verbindungsstrecken
2014.11 (5x)http://google.de/url?sa=t&source=web&cd=10&ved=0CDIQFjAJ
2015.04 (4x)http://google.de/url?sa=t&source=web&cd=2&ved=0CB8QFjAB
2013.10 (4x)http://www.sweetpacks-search.com/search.asp?q=dirichlet's schreibtisch&ln=de&...
2012.06 (4x)http://google.de/url?sa=t&rct=j&q=schubfachprinzip einheitskreis

[Seitenanfang]

" Stern Mathematik: Dirichlets Schreibtisch" | 3 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Dirichlets Schreibtisch
von SchuBi am So. 20. Juli 2003 20:48:20


Hallo, Matroid!
Ich habe gerade durch Zufall im Chat diese Perle entdeckt.
Toll.

 [Bearbeiten]

Re: Dirichlets Schreibtisch
von Ex_Mitglied_40986 am Sa. 11. Oktober 2014 17:22:03


Hallo Matroid,

alles schöne Aufgaben! Nur in der 6. Aufgabe "Unter je fünf Punkten, die in einem Quadrat der Seitenlänge 4 liegen, gibt es zwei, die einen Abstand <= 2 haben." scheint ein Tippfehler zu sein - statt "Seitenlänge 4" sollte wohl "Seitenlänge 3" stehen, denn sonst bekomme ich problemlos sechs Punkte mit Abstand > 2 unter. Dabei habe ich das Schubfachprinzip aber nicht angewendet - ist bei dieser Aufgabe eventuell auch schwer erfolgreich anwendbar.

Viele Grüße
somi

 [Bearbeiten]

Re: Dirichlets Schreibtisch
von Ex_Mitglied_40986 am So. 12. Oktober 2014 13:32:36


Hallo Mandroid,

habe mich gestern geirrt, nicht die "4" war der Tippfehler sondern die "2" - für die wohl "3" stehen sollte.

Viele Grüße
somi

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]