Tauben und Beschichtungen

Die drei letzte Woche gestellten „Tauben“-Probleme haben trotz ihrer relativen Einfachheit zahlreiche und interessante Kommentare hervorgerufen.

Die erste ist die einfachste: Wenn wir einen Würfel 12 Mal werfen, könnte es passieren, obwohl es unwahrscheinlich ist (wie unwahrscheinlich?), dass jede der sechs Zahlen zweimal kommt. Wir müssten also 13 Mal werfen, um absolut sicher zu sein, dass irgendeine Zahl mindestens dreimal kommt.

Das zweite Problem kann auf verschiedene Weise angegangen werden. So hat Luis Ortiz es gemacht:

Das 12-stellige Problem wird anhand einer Tabelle anschaulich dargestellt. Wir ordnen die 100 möglichen zweistelligen Zahlen in Reihen zu je 11 aufeinanderfolgenden Zahlen, beginnend bei 00, wie folgt an:

00 01 02 03 04 05 06 07 08 09 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

· · ·

88 89 90 91 92 93 94 95 96 97 98

99

In dieser Tabelle ist die Differenz zwischen zwei Zahlen in derselben Spalte ein Vielfaches von 11, d. h. beide Ziffern sind gleich. Wenn wir 12 beliebige Zahlen aus der Tabelle wählen, müssen mindestens zwei davon in derselben Spalte stehen, d. h. ihre Differenz muss beide Ziffern gleich haben. Tatsächlich handelt es sich letztendlich um einen Taubenschlag mit 11 Nisten und 12 Tauben.

Ich habe am Ende des vorherigen Beitrags gesagt, dass das Schubfachprinzip es uns ermöglicht, einige Probleme effektiv anzugehen, indem wir es mit der Graphentheorie kombinieren, und die von Manuel Amorós für das dritte Problem der letzten Woche bereitgestellte Lösung ist ein gutes Beispiel dafür:

Das Freundschaftsproblem lässt sich gut in einem farbigen Graphen erkennen, in dem die Punkte Personen darstellen und die Kanten die Beziehungen ausdrücken: eine blaue Kante, wenn die Personen sich kennen, und eine rote, wenn nicht. Ziel ist es, die Existenz eines monochromen Graphen zu beweisen. Von jedem Knoten P gehen fünf Kanten aus, blaue oder rote. Unbedingt müssen drei die gleiche Farbe haben, sagen wir blau. Die drei entsprechenden Knoten sind wiederum miteinander verbunden, und es sind zwei Fälle möglich: Entweder sind alle drei Kanten des Dreiecks rot (wir hätten ein monochromes Dreieck), oder es gibt eine blaue Kante. Diese Kante bildet zusammen mit den beiden Kanten, die von ihren Enden in Richtung P ausgehen, ein blaues Dreieck.

Beschichtungen mit ähnlichen Werten

Ohne unseren konzeptionellen Taubenschlag zu verlassen (obwohl die Beziehung möglicherweise nicht offensichtlich ist), schlug Salva Fuster das folgende Überdeckungsproblem vor:

„Wie viele kleinere gleichseitige Dreiecke sind mindestens erforderlich, um ein gleichseitiges Dreieck abzudecken?“

Diese kleineren Dreiecke müssen nicht gleich groß sein und können sich überlappen (sonst wäre die Antwort offensichtlich 4).

Das Problem lässt interessante Variationen und Verallgemeinerungen zu: Wie viele kleinere Quadrate braucht man mindestens, um ein Quadrat zu bedecken? Lässt sich das Kriterium auf andere regelmäßige Polygone verallgemeinern? Und auf unregelmäßige Polygone? Und auf den Kreis?

Und schließlich noch ein weiteres Problem (das subtil mit dem SF-Problem verwandt ist), bei dem das gleichseitige Dreieck und das Schubfachprinzip zusammenlaufen:

Können 5 beliebige Punkte in einem gleichseitigen Dreieck mit einer Seitenlänge von 1 Meter mehr als 50 cm voneinander entfernt sein?