Beweis des Schubfachprinzips durch Widerspruch

Beim Beweis durch Widerspruch geht man davon aus, dass eine geeignete Aussage wahr ist, und leitet daraus einen Widerspruch ab. Daraus schließen Sie, dass die ursprüngliche Aussage falsch ist.

Hier versuchen Sie zu beweisen, dass mindestens eine Box enthalten sein muss$\left \lceil \dfrac{n}{m} \right \rceil$Artikel. Der normale Weg wäre also anzunehmen, dass dies falsch ist und dass keine der Boxen so viele Elemente enthält.

Als Hinweis zur Vorgehensweise – wie viele Artikel dürfen maximal in jeder Box enthalten sein, wenn keine mindestens enthalten ist$\left \lceil \dfrac{n}{m} \right \rceil$? Kannst du das mit der Tatsache in Verbindung bringen, die du verwenden sollst?

Lassen$L$sei die Gesamtzahl der Gegenstände, die du platzieren kannst, ohne sie zu haben$\left \lceil \dfrac{n}{m} \right \rceil$oder mehr in einem der$m$Boxen.

Annehmen, dass$L\ge n$damit du passen kannst$n$Gegenstände in die Kisten.

Die maximale Anzahl, die Sie in ein Feld legen können, ist

$\left \lceil \dfrac{n}{m} \right \rceil-1$.

Die maximale Anzahl an$m$Boxen ist daher

$L=m\cdot\left \lceil \dfrac{n}{m} \right \rceil-m$.

Verwenden Sie nun die gegebene Ungleichung damit$\left \lceil \dfrac{n}{m} \right \rceil\lt \dfrac nm+1$was gibt

$L\lt m\cdot\left (\dfrac nm+1\right)-m$was sich reduziert auf$L\lt n$

Nun sind wir am Anfang davon ausgegangen$L\ge n$, das ist also ein Widerspruch. Da können wir nicht haben$L\ge n$Wir müssen haben$L\lt n$.

Nehmen wir zum Zwecke des Widerspruchs an, dass wir die platzieren können$n$Artikel in den Kartons so, dass die maximale Anzahl von Artikeln in einem Karton ist$\left\lceil\frac nm \right\rceil-1 = \left\lceil\frac nm -1\right \rceil$.

Dann mit$n'$um die Gesamtzahl der Artikel zu zählen, die in den angezeigten Kartons platziert sind$n'\leq m\cdot\left\lceil\frac nm -1\right \rceil$und aus der gegebenen Ungleichung haben wir$n'< m\cdot\left(\frac nm -1 +1\right) = m\cdot\frac nm =n$Und$n'<n$ist ein Widerspruch, da wir alles angenommen haben$n$Gegenstände platziert wurden.

Daher muss die Anzahl der Elemente in einer Kiste größer sein als die Annahme$\left\lceil\frac nm \right\rceil$nach Bedarf.