www.wikidata.de-de.nina.az

Schubfachprinzip In der Mathematik ist das engl pigeonhole principle daher auch Taubenschlagprinzip eine einfache intuit

Schubfachprinzip

In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache, intuitive und oftmals hilfreiche Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip wird oft in der diskreten Mathematik verwendet.

Ein Taubenschlag mit Tauben in Sitzen: Weil 10 größer als 9 ist, besagt das Taubenschlagprinzip, dass auf mindestens einem Sitz mehr als eine Taube sitzt.

Das Prinzip Bearbeiten

Das Prinzip kann informell folgendermaßen formuliert werden:

bzw. äquivalent

Der Name kommt von einer bildhaften Vorstellung dieses Vorgangs: Falls man eine bestimmte Anzahl von Schubfächern hat, und man mehr Objekte in die Fächer legt als Fächer vorhanden sind, dann landen in irgendeinem Schubfach mindestens zwei Objekte.

Es geht wahrscheinlich auf Peter Dirichlet zurück, der es 1834 angewandt hat. In vielen Sprachen (z. B. Bulgarisch, Tschechisch, Dänisch, Isländisch, Kasachisch, Lettisch, Polnisch, Rumänisch und Russisch) wird es daher auch „Dirichlet-Prinzip“ genannt.

Beweis Bearbeiten

Der Beweis dieses Prinzips ist trivial und kann zum Beispiel indirekt geführt werden: Falls das Prinzip nicht stimmt, dann enthält jedes Schubfach höchstens ein Objekt. Damit gibt es höchstens so viele Objekte wie Schubfächer. Das steht aber im Widerspruch zur Voraussetzung, dass es mehr Objekte als Schubfächer gibt.

Beispiele Bearbeiten

Trotz seiner Einfachheit kann man mit dem Schubfachprinzip bestimmte Aussagen treffen, zum Beispiel die, dass es in München mindestens zwei Personen gibt, die exakt dieselbe Anzahl von Haaren auf dem Kopf haben. Beweis: Man teilt alle Bewohner Münchens nach der Anzahl ihrer Haare in „Schubfächer“ ein. Typischerweise hat der Mensch etwa 100.000 bis 200.000, jedoch sicher weniger als 1 Million Haare, damit gibt es maximal eine Million Schubfächer (von 0 bis 999.999). Da es aber etwa 1,4 Millionen Einwohner in München gibt, hat man mehr Einwohner als Schubfächer, damit landen in mindestens einem Schubfach zwei oder mehr Personen. Diese haben nach Definition der Schubfächer dieselbe Anzahl Haare auf dem Kopf. Das Schubfachprinzip sagt jedoch nichts darüber aus, welches Schubfach zwei oder mehr Personen enthält, es besagt nur, dass es ein solches Schubfach gibt.

Ein weiteres Beispiel ist die Aussage, dass in einer Gruppe von 13 Personen mindestens zwei im selben Monat Geburtstag haben (weil es nur 12 Monate gibt).

Ein weiteres, etwas komplexeres Beispiel, bei dem das Schubfachprinzip verwendet wird, ist folgendes: Wählt man zwölf paarweise verschiedene zweistellige Zahlen, so gibt es mindestens zwei unter ihnen, deren Differenz eine zweistellige Zahl ist, deren beide Ziffern gleich sind. Beweis: Die Darstellung einer zweistelligen Zahl, die ein Vielfaches von Elf ist, besteht aus zwei gleichen Ziffern. Nun überlegt man, welche Reste die Division einer Zahl durch 11 ergeben kann (siehe Restklasse). Es ergibt sich, dass die Zahlen 0 bis 10 die möglichen Reste sind. Wenn zwei Zahlen denselben Rest lassen, ist ihre Differenz ein Vielfaches von 11. Es gibt also 11 „Schubfächer“, aber 12 zweistellige Zahlen, die darauf verteilt werden. Nach dem Schubfachprinzip befinden sich in einem Fach also zwei Zahlen; wie oben erklärt, ist ihre Differenz ein Vielfaches von 11, hat also die gewünschte Form.

Verschärfung des Prinzips Bearbeiten

Eine „schärfere“ Fassung des Schubfachprinzips lautet wie folgt:

Beispiel der Verschärfung:

Damit kann man jetzt beweisen, dass es mindestens 82 Einwohner Deutschlands mit gleicher Haaranzahl gibt, wenn man voraussetzt, dass es in Deutschland mindestens 81.000.001 Einwohner gibt und alle weniger als 1.000.000 Haare besitzen: Wir verteilen 81.000.001 Objekte (Einwohner) auf 1.000.000 Mengen (die die Haaranzahl ihrer Elemente [Objekte] wiedergeben), also gibt es mindestens eine Menge mit mindestens Objekten.

Verwandte Themen Bearbeiten

Mit kombinatorischen Verallgemeinerungen des Prinzips befasst sich die Ramseytheorie, siehe z. B. Satz von Van der Waerden.

Literatur und Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger: Bachelor und Lehramt. 5. erw. Auflage. Springer Fachmedien Wiesbaden, Wiesbaden 2014, ISBN 978-3-658-05781-7, S. 1–10.
  2. Manon Bischoff: Die fabelhafte Welt der Mathematik: Das einfachste Theorem der Welt. In: Spektrum.de. 3. März 2023, abgerufen am 6. August 2023.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik ist das Schubfachprinzip engl pigeonhole principle daher auch Taubenschlagprinzip eine einfache intuitive und oftmals hilfreiche Methode um gewisse Aussagen uber eine endliche Menge zu machen Das Prinzip wird oft in der diskreten Mathematik verwendet Ein Taubenschlag mit n 10 displaystyle n 10 Tauben in m 9 displaystyle m 9 Sitzen Weil 10 grosser als 9 ist besagt das Taubenschlagprinzip dass auf mindestens einem Sitz mehr als eine Taube sitzt Inhaltsverzeichnis 1 Das Prinzip 1 1 Beweis 1 2 Beispiele 2 Verscharfung des Prinzips 3 Verwandte Themen 4 Literatur und Weblinks 5 EinzelnachweiseDas Prinzip BearbeitenDas Prinzip kann informell folgendermassen formuliert werden Falls man n displaystyle n nbsp Objekte auf m displaystyle m nbsp Mengen mit m gt 0 displaystyle m gt 0 nbsp verteilt und n displaystyle n nbsp grosser als m displaystyle m nbsp ist dann wird mindestens eine Menge mehrere Objekte enthalten 1 bzw aquivalent Falls man n displaystyle n nbsp Objekte auf m displaystyle m nbsp Mengen verteilt und n displaystyle n nbsp kleiner als m displaystyle m nbsp ist und die Mengen disjunkt sind also jedes Objekt nur einer Menge angehort dann bleibt mindestens eine dieser Mengen leer Der Name kommt von einer bildhaften Vorstellung dieses Vorgangs Falls man eine bestimmte Anzahl von Schubfachern hat und man mehr Objekte in die Facher legt als Facher vorhanden sind dann landen in irgendeinem Schubfach mindestens zwei Objekte Es geht wahrscheinlich auf Peter Dirichlet zuruck der es 1834 angewandt hat In vielen Sprachen z B Bulgarisch Tschechisch Danisch Islandisch Kasachisch Lettisch Polnisch Rumanisch und Russisch wird es daher auch Dirichlet Prinzip genannt Beweis Bearbeiten Der Beweis dieses Prinzips ist trivial und kann zum Beispiel indirekt gefuhrt werden Falls das Prinzip nicht stimmt dann enthalt jedes Schubfach hochstens ein Objekt Damit gibt es hochstens so viele Objekte wie Schubfacher Das steht aber im Widerspruch zur Voraussetzung dass es mehr Objekte als Schubfacher gibt Beispiele Bearbeiten Trotz seiner Einfachheit kann man mit dem Schubfachprinzip bestimmte Aussagen treffen zum Beispiel die dass es in Munchen mindestens zwei Personen gibt die exakt dieselbe Anzahl von Haaren auf dem Kopf haben Beweis Man teilt alle Bewohner Munchens nach der Anzahl ihrer Haare in Schubfacher ein Typischerweise hat der Mensch etwa 100 000 bis 200 000 jedoch sicher weniger als 1 Million Haare damit gibt es maximal eine Million Schubfacher von 0 bis 999 999 Da es aber etwa 1 4 Millionen Einwohner in Munchen gibt hat man mehr Einwohner als Schubfacher damit landen in mindestens einem Schubfach zwei oder mehr Personen Diese haben nach Definition der Schubfacher dieselbe Anzahl Haare auf dem Kopf Das Schubfachprinzip sagt jedoch nichts daruber aus welches Schubfach zwei oder mehr Personen enthalt es besagt nur dass es ein solches Schubfach gibt 2 Ein weiteres Beispiel ist die Aussage dass in einer Gruppe von 13 Personen mindestens zwei im selben Monat Geburtstag haben weil es nur 12 Monate gibt Ein weiteres etwas komplexeres Beispiel bei dem das Schubfachprinzip verwendet wird ist folgendes Wahlt man zwolf paarweise verschiedene zweistellige Zahlen so gibt es mindestens zwei unter ihnen deren Differenz eine zweistellige Zahl ist deren beide Ziffern gleich sind Beweis Die Darstellung einer zweistelligen Zahl die ein Vielfaches von Elf ist besteht aus zwei gleichen Ziffern Nun uberlegt man welche Reste die Division einer Zahl durch 11 ergeben kann siehe Restklasse Es ergibt sich dass die Zahlen 0 bis 10 die moglichen Reste sind Wenn zwei Zahlen denselben Rest lassen ist ihre Differenz ein Vielfaches von 11 Es gibt also 11 Schubfacher aber 12 zweistellige Zahlen die darauf verteilt werden Nach dem Schubfachprinzip befinden sich in einem Fach also zwei Zahlen wie oben erklart ist ihre Differenz ein Vielfaches von 11 hat also die gewunschte Form Verscharfung des Prinzips BearbeitenEine scharfere Fassung des Schubfachprinzips lautet wie folgt Verteilt man n displaystyle n nbsp Objekte auf k displaystyle k nbsp Mengen n k gt 0 displaystyle n k gt 0 nbsp so gibt es mindestens eine Menge in der sich zumindest n k displaystyle lceil tfrac n k rceil nbsp Objekte befinden displaystyle nbsp dabei bedeutet das Symbol n k displaystyle left lceil tfrac n k right rceil nbsp die kleinste ganze Zahl welche grosser oder gleich n k displaystyle tfrac n k nbsp ist displaystyle nbsp Beispiel der Verscharfung Damit kann man jetzt beweisen dass es mindestens 82 Einwohner Deutschlands mit gleicher Haaranzahl gibt wenn man voraussetzt dass es in Deutschland mindestens 81 000 001 Einwohner gibt und alle weniger als 1 000 000 Haare besitzen Wir verteilen 81 000 001 Objekte Einwohner auf 1 000 000 Mengen die die Haaranzahl ihrer Elemente Objekte wiedergeben also gibt es mindestens eine Menge mit mindestens 81 000 001 1 000 000 81 000 001 82 displaystyle left lceil tfrac 81 000 001 1 000 000 right rceil lceil 81 000 001 rceil 82 nbsp Objekten Verwandte Themen BearbeitenMit kombinatorischen Verallgemeinerungen des Prinzips befasst sich die Ramseytheorie siehe z B Satz von Van der Waerden Literatur und Weblinks BearbeitenMartin Aigner Gunter M Ziegler Das BUCH der Beweise Berlin Springer 2002 Pigeon Principle bei cut the knot engl mit math Beispielen Daniel Schwenter Zu erweisen dass es wol muglich ja auch seyn musse dass vnter zweyen Menschen einer so viel Haar an seinem Leib habe als der ander in Deliciae physico mathematicae Nurnberg 1636 S 86Einzelnachweise Bearbeiten Albrecht Beutelspacher Marc Alexander Zschiegner Diskrete Mathematik fur Einsteiger Bachelor und Lehramt 5 erw Auflage Springer Fachmedien Wiesbaden Wiesbaden 2014 ISBN 978 3 658 05781 7 S 1 10 Manon Bischoff Die fabelhafte Welt der Mathematik Das einfachste Theorem der Welt In Spektrum de 3 Marz 2023 abgerufen am 6 August 2023 Abgerufen von https de wikipedia org w index php title Schubfachprinzip amp oldid 236188478