Leider führte das automatische Konvertieren in das HTML-Format zu einigen Darstellungsfehlern, die wir nicht beheben können. Die HTML-Darstellung auf dieser Seite ist daher nur im nicht formelhaltigen Text korrekt und somit nur für einen Überblick über die Lösungen geeignet. Für korrekte Formeln und Bilder verweisen wir auf die PDF- oder PS-Version - und bitten um Verständnis.
Aufgabe 1
Welche regelmäßigen n-Ecke der Seitenlänge 1 kann man in kleinere
regelmäßige Vielecke (nicht unbedingt n-Ecke!) der Seitenlänge 1
zerlegen und auf welche Art und Weisen ist dies gegebenenfalls machbar?
Lösung:
Wir betrachten ein regelmäßiges n-Eck (n 3):
für das regelmäßige Dreieck: | 60o | ||
für das regelmäßige Viereck: | 90o | ||
für das regelmäßige Fünfeck: | 108o | ||
für das regelmäßige Sechseck: | 120o | ||
für das regelmäßige Zwölfeck: | 150o | ||
für das regelmäßige 30-Eck: | 168o | . |
Da für m 3 jeder Punkt eines regelmäßigen m-Ecks einen Innenwinkel von mindestens 60o, jeder Punkt eines n-Eck jedoch einen Innenwinkel von weniger als 180o hat, können wir in A maximal zwei Vielecke zusammenlegen (wobei wir bei nur einem Vieleck das n-Eck selbst erhalten).
Wir beginnen mit zwei regelmäßigen Dreiecken. In diesem Fall erhalten wir als = 60o + 60o = 120o den Innenwinkel eines Eckpunktes eines regelmäßigen Sechsecks.
Tatsächlich lässt sich das regelmäßige Sechseck in sechs regelmäßige Dreiecke zerlegen:
Nun versuchen wir es mit einem regelmäßigen Dreieck und einem regelmäßigen Viereck. In diesem Fall erhalten wir als = 60o + 90o = 150o den Innenwinkel eines Eckpunktes eines regelmäßigen Zwölfecks.
Wir setzen also auf jede Kante eines regelmäßigen Zwölfecks abwechselnd ein Drei- und ein Viereck. Nach innen hin schließt jeweils eine Kante eines Vierecks ab und wir erhalten ein Sechseck. An jedem Punkt dieses Sechsecks liegen außen zwei Vierecke und ein Dreieck an, wodurch wir als Innenwinkel jeweils 360o - 2 . 90o - 60o = 120o erhalten. Das Sechseck ist also regelmäßig und hat die Seitenlänge 1 (denn jedes der verwendeten Vierecke hat die Seitenlänge 1).
Es ergibt sich daher:
Natürlich lässt sich das innere regelmäßige Sechseck wiederum in sechs Dreiecke zerlegen. Man erhält dann eine Zerlegung in sechs Vier- und zwölf Dreiecke:
Als Nächstes testen wir das Zusammensetzen eines Dreiecks und eines Fünfecks. Es ergibt sich dann als Innenwinkel = 60o + 108o = 168o. Dies ist der Innenwinkel eines Punktes eines regelmäßigen 30-Ecks. Setzen wir nun wie oben auf jede Kante eines regelmäßigen 30-Ecks abwechselnd ein regelmäßiges Dreieck und ein Fünfeck, so erhalten wir innen (wo jeweils zwei Kanten eines Fünfecks abschließen) ein (nicht konvexes) 30-Eck. An jedem zweiten Eckpunkt dieses 30-Ecks liegen ein Dreieck und zwei Fünfecke an und wir erhalten den Innenwinkel 360o - 2 . 108o - 60o = 84o. Dieser Winkel ist jedoch weder selbst Innenwinkel eines regelmäßigen n-Ecks noch ist er Summe zweier solcher Innenwinkel. Demnach ist eine solche Zerlegung nicht möglich.
Auch lassen sich keine weiteren Zerlegungen realisieren, da sich sowohl beim
Zusammensetzen zweier Vierecke als auch eines Drei- und eines Sechsecks ein
Winkel von 180o ergibt. Alle Innenwinkel eines n-Ecks (n 3) sind
jedoch kleiner als 180o. Bei allen anderen Kombinationen würde der
Innenwinkel noch größer werden.
Es lassen sich also nur das regelmäßige Sechs- und Zwölfeck in andere regelmäßige Vielecke gleicher Kantenlänge zerlegen.
Aufgabe 2
Käpt'n Sperling hat elf Kandidaten für seine Piratentruppe gefunden. Zu
Beginn muss er sie aber in piratöser Lebensweise
unterrichten. Heute steht das Lügen auf dem Programm - das soll ja nicht etwa
plump sein!
Der Käpt'n sagt: ,,Jungs, ich weiß, dass ihr alle aus Schwarzdorf oder aus Knochenbrück kommt, aber ich weiß nicht, wer woher ist. Sagt mir, woher ihr kommt - aber denkt daran: Keiner darf die Wahrheit sagen.``
Die Nr. 1 (alle anderen Neuen stehen in schöner Reihe links von ihm) sagt: ,,Die Zahl der Männer aus Schwarzdorf ist eine Quadratzahl.`` Nr. 2, 3, 6, 7 und 9 sagen: ,,Ich komme nicht aus derselben Stadt wie mein rechter Nachbar.`` Hingegen behaupten Nr. 4, 5, 10 und 11: ,,Ich komme aus derselben Stadt wie mein rechter Nachbar.`` Schließlich stellt Nr. 8 fest: ,,Aus Knochenbrück kommt eine ungerade Zahl Männer.``
Der Käpt'n ist zufrieden mit seinen neuen Mannen - wer kommt woher?
Lösung:
Der Einfachheit halber benutzen wir im Folgenden das Symbol
, das nichts
anderes bedeuten soll, als ,,wohnt in derselben Stadt wie``.
1 2 bedeutet also, dass Nr. 1 in derselben Stadt wohnt wie Nr. 2, und 2 3 steht dafür, dass Nr. 2 nicht in derselben Stadt wohnt wie Nr. 3.
Betrachten wir zunächst die Aussagen von Nr. 2, 3, 6, 7 und 9: Da alle gelogen haben, wissen wir, dass jeder von ihnen aus derselben Stadt kommt wie sein rechter Nachbar. Es gilt also 1 2 3, 5 6 7 sowie 8 9.
Unseren momentanen Informationsstand können wir folgendermaßen darstellen, wobei ein gleicher Buchstabe bedeutet, dass die Jungs aus derselben Stadt kommen, verschiedene Buchstaben aber nicht unbedingt eine unterschiedliche Heimat bedeuten. Ein leeres Feld heißt, dass wir noch nichts über diese Nummer wissen:
|
Auch Nr. 4, 5, 10 und 11 haben geschwindelt. Jeder von ihnen kommt daher nicht aus derselben Stadt wie sein rechter Nachbar. Also: 4 3, 2, 1 und 7, 6, 5 4. Da es nur zwei mögliche Städte gibt, folgt 1 2 3 5 6 7 4. Aus den Aussagen von Nr. 10 und 11 können wir schließen, dass 8 9 11 10 gilt.
Nun gibt es folgende zwei Möglichkeiten:
|
Durch die Aussagen von Nr. 1 und 8 wissen wir, dass die Anzahl der Männer aus Schwarzdorf keine Quadratzahl ist und dass die Anzahl der Männer aus Knochenbrück gerade sein muss.
Angenommen, Nr. 1 kommt aus Knochenbrück, so gibt es folgende Möglichkeiten:
|
In beiden Fällen wäre die Anzahl der aus Knochenbrück kommenden Männer ungerade. Pirat Nr. 1 muss also aus Schwarzdorf kommen. Wir erhalten:
|
Bei der ersten Möglichkeit ist die Anzahl der aus Schwarzdorf kommenden Männer 9 und also eine Quadratzahl. Diese Möglichkeit scheidet daher auch aus.
Es bleibt nur noch die zweite Möglichkeit, in der tatsächlich alle Bedingungen erfüllt sind:
|
Aufgabe 3
Ein ,,Pythagorasbaum`` entsteht, wenn man auf ein Quadrat der Seitenlänge 1 als Stamm ein rechtwinkliges Dreieck mit seiner Hypotenuse aufsetzt, dann die beiden Kathetenquadrate zeichnet und dann weiter beliebig (aber endlich) oft auf irgendein schon gezeichnetes Quadrat wieder ein dem ursprünglichen rechtwinkligen Dreieck ähnliches rechtwinkliges Dreieck aufsetzt (der Ästhetik zuliebe gleichorientiert zum ersten) und dann wieder die beiden Kathetenquadrate einzeichnet usw.
Die ,,äußeren`` Quadrate am Baum werden ,,Blätter`` des Baumes genannt. Die folgende Abbildung zeigt einen Baum mit drei verschieden großen Blättern.
Gibt es einen Pythagorasbaum mit mehr als 1000 Blättern, aber nur zwei verschiedenen Blattgrößen, bei dem das verwendete Dreieck nicht gleichschenklig ist?
Lösung:
Ja, solch einen Baum gibt es, nämlich eine Art
,,Goldener-Schnitt-Baum``, den wir im Folgenden konstruieren werden.
Wir wählen das Dreieck mit den Seitenlängen
c = 1 und a : = und b : = , |
wobei
= 0, 618... |
das Inverse des sogenannten Goldenen Schnittes ist. Dieses Dreieck ist nach der Umkehrung des Satzes des Pythagoras tatsächlich rechtwinklig, denn es erfüllt
a2 + b2 = + = + = 1 = c2. |
Zu diesem Zeitpunkt haben wir Blätter in den beiden Größen a2 = und b2 = . Die Anzahl der kleineren Blätter sei mit A1, die der größeren Blätter mit B1 bezeichnet. Es ist dann A1 = B1 = 1.
Jedes zum ersten Dreieck ähnliche Dreieck mit den Seiten
a', b', c' erfüllt
= = und = = , |
also
a' = . c' und b' = . c'. |
Wir setzen nun auf das Blatt mit der größeren Seitenlänge - das ist b -
ein neues Dreieck. Dieses hat dann die Seitenlängen
c2 = b = , a2 = . c2 = , b2 = . c2 = , |
und es liefert uns zwei neue Blätter, eines von Größe a22 = und eines von Größe b22 = . Von zuvor haben wir noch ein Blatt der Größe a2 = , das andere Blatt hingegen ist zu einem Teil des Stammes geworden.
Insgesamt haben wir nun A2 : = 1 = B1 Blätter der kleineren Größe und B2 : = 1 + 1 = B1 + A1 Blätter der größeren Größe .
Im nächsten Schritt setzen wir wiederum auf alle B2 Blätter der größeren
Sorte ein Dreieck. Diese haben die Seitenlängen
c3 = b2 = , a3 = . c3 = , b3 = . c3 = . . |
Die B2 ehemals großen Blätter werden ein Teil des Stammes und es entstehen B2 neue Blätter der Größe a32 = und B2 neue Blätter der Größe b32 = . Insgesamt haben wir dann A3 = B2 Blätter der kleineren Größe und B3 = B2 + A2 Blätter der größeren Größe .
cn+1 | = bn = , | |
an+1 | = . cn+1 = , | |
bn+1 | = . cn+1 = |
und erhalten zusätzlich zu den An ehemals kleinen Blättern der Größe an2 = noch je Bn Blätter der Größen bn+12 = und an+12 = hinzu. Insgesamt haben wir dann also wieder nur Blätter in zwei Größen, nämlich
Bn+1 | = Bn + An | /TD> | große Blätter der Größe | /TD> | bn+12 = | |
An+1 | = Bn | kleine Blätter der Größe | an+12 = . |
Unsere Konstruktion liefert demnach in jedem Schritt einen Pythagorasbaum, der
genau zwei verschiedene Blattgrößen hat.
Außerdem wird in jedem Schritt die Anzahl der Blätter größer, denn an jedes
Blatt, das zu einem Teil des Stammes wird, werden zwei neue Blätter
angehängt.
Mit einer ganz groben Abschätzung folgt, dass wir spätestens nach 1000 Schritten 1000 Blätter haben. Damit sind wir fertig.
Wir können die Anzahl der Blätter aber auch genau ausrechnen:
Nach dem ersten Schritt (d. h. wir haben genau ein Dreieck, das wir auf den
Stamm aufgesetzt hatten) haben wir
A1 + B1 = 1 + 1 = 2 Blätter. Nach dem
n-ten Schritt haben wir An + Bn Blätter.
Für die einzelnen Anzahlen gilt
B1 = 1, B2 = 2 und Bn+1 = Bn + An = Bn + Bn-1. |
Die Bn bilden die unter Mathematikern wohlbekannte Fibonacci-Folge:
(1,)1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,... |
Es gilt B15 = 987 und A15 = B14 = 610. Nach 15 Schritten haben wir demnach bereits 987 + 610 = 1597 Blätter.
Bemerkung: Dieser Goldener-Schnitt-Baum ist der einzige Baum, bei dem das
verwendete Dreieck nicht gleichseitig ist und der nur zwei verschiedene
Blattgrößen hat.
Beweisidee: An den ,,Enden`` jeder Verästelung entsteht ein Teil-Pythagorasbaum mit drei Blättern. Auch dieser darf dann nur zwei verschiedene Blattgrößen haben. Sind a, b, c die Seitenlängen des größeren Dreiecks, so haben die drei Blätter die Größen a2, und . Damit müssen die beiden Blätter mit den Größen a2 und gleich groß sein. Stellen wir dieses um und nutzen noch aus, dass a2 + b2 = c2 gilt, so erhalten wir, dass auch hier - wie bei dem oben konstruierten Baum - die Beziehungen = und = gelten.
Aufgabe 4
Auf wie viele Art und Weisen kann man Spielsteine so auf ein
3×10-Spielbrett setzen, dass keine zwei Steine horizontal, vertikal oder
diagonal benachbart sind?
Lösung:
Es gibt genau 47003 Möglichkeiten, Steine unter den erlaubten Regeln auf
das Spielbrett zu setzen.
Dabei haben wir auch die eine Möglichkeit mitgezählt, gar keinen Stein
auf das Brett zu setzen. Ob man diese Möglichkeit mitzählen möchte oder
nicht, ist eine Geschmacksfrage, auf jeden Fall macht sie unsere Rechnungen
einfacher.
Wir berechnen die Anzahl der Möglickeiten rekursiv, indem wir zuerst zählen,
wie viele Möglichkeiten es bei einer Spalte (d. h. bei einem 3×1-Spielbrett) gibt, dann, wie viele es bei zwei Spalten (d. h. bei einem
3×2-Spielbrett) gibt, und
so weiter bis zu einem
3×10-Spielbrett.
Rekursiv heißt dabei, dass wir immer die alte Anzahl nutzen wollen, um die Anzahl bei einer weiteren Spalte auszurechnen.
Dazu unterteilen wir die Gesamtanzahl in gewisse Unteranzahlen, je nachdem, wo
die Steine in der letzten Spalte liegen:
an | sei die Gesamtanzahl aller Möglichkeiten bei n Spalten, |
inklusive der Möglichkeit gar keinen Stein zu verteilen | |
die letzte (n-te) Spalte ist leer | |
mn | in der letzten Spalte liegt ein Stein in der Mitte |
bn | in der letzten Spalte liegt oben und unten je ein Stein |
on | in der letzten Spalte liegt nur oben ein Stein |
un | in der letzten Spalte liegt nur unten ein Stein |
Jetzt nehmen wir eine neue ((n + 1)-te) Spalte hinzu. Jede alte Möglichkeit
liefert eine neue, bei der die neue letzte Spalte leer bleibt. In die Mitte
oder gleichzeitig nach oben und unten der neuen letzten Spalte können wir nur dann
einen bzw. zwei Steine legen, wenn die n-te Spalte leer ist. Nach unten
können wir einen Stein legen, wenn die n-te Spalte leer ist oder wenn in der
n-ten Spalte nur oben ein Stein liegt. Wir erhalten die Formeln
= an | ||
mn+1 | = | |
bn+1 | = | |
un+1 | = + on = + un. |
Nutzen wir dabei aus, dass dann auch = an-1 gilt, so wird die letzte Formel zu
un+1 = + un = an-1 + un |
und die Gesamtanzahl berechnet sich als
an+1 | = + mn+1 + bn+1 + 2 . un+1 | |
= an + + + 2 . an-1 + 2 . un | ||
= an + 4 . an-1 + 2 . un. |
Um die Anzahl der Möglichkeiten dann tatsächlich auszurechnen, brauchen wir zusätzlich zu den beiden Rekursionsformeln für an+1 und un+1 noch einige Anfangswerte.
Haben wir nur eine Spalte, so ist = m1 = b1 = u1 = 1, was zusammen a1 = + m1 + b1 + 2u1 = 5 ergibt. Jetzt haben wir einen Anfangswert für un und einen für an. Da die Rekursionsformel für an+1 aber immer zwei vorhergende Werte benutzt, müssen wir noch an für einen zweiten Wert bestimmen. Wir könnten a2 ausrechnen; einfacher ist es aber, noch a0 hinzuzunehmen. Es ist a0 = 1, denn auf null Spalten kann man keinen Stein legen, aber gar keinen Stein zu verteilen, wollten wir ja auch als eine erlaubte Möglichkeit mitzählen. - Oder wir begründen den Wert a0 = 1 durch: Der Summand an-1 kam dadurch in die Formel, dass wir die Rekursionsformel = an auch für (n - 1) + 1 angewandt haben: = an-1. Umgekehrt ist dann aber auch a0 = a1-1 = = 1.
Nun haben wir alle Formeln zusammen.
Es gilt
a0 | = 1, | a1 | = 5, | u1 | = 1 |
für die Anfangswerte, und die benötigten Rekursionsformeln sind
an+1 | = an + 4 . an-1 + 2 . un | fürn 1, | ||
un+1 | = an-1 + un | fürn 1. |
Damit berechnen wir dann nacheinander
a2 | = a1 + 4a0 + 2u1 | u2 | = a0 + u1 | |
= 5 + 4 . 1 + 2 . 1 = 11 | = 1 + 1 = 2 | |||
a3 | = a2 + 4a1 + 2u2 | u3 | = a1 + u2 | |
= 11 + 4 . 5 + 2 . 2 = 35 | = 5 + 2 = 7 | |||
a4 | = 35 + 4 . 11 + 2 . 7 = 93 | u4 | = 11 + 7 = 18 | |
a5 | = 93 + 4 . 35 + 2 . 18 = 269 | u5 | = 35 + 18 = 53 | |
a6 | = 269 + 4 . 93 + 2 . 53 = 747 | u6 | = 93 + 53 = 146 | |
a7 | = 747 + 4 . 269 + 2 . 146 = 2115 | u7 | = 269 + 146 = 415 | |
a8 | = 2115 + 4 . 747 + 2 . 415 = 5933 | u8 | = 747 + 415 = 1162 | |
a9 | = 5933 + 4 . 2115 + 2 . 1162 = 16717 | u9 | = 2115 + 1162 = 3277 | |
a10 | = 16717 + 4 . 5933 + 2 . 3277 = 47003 |
Insgesamt gibt es somit 47003 Möglichkeiten, Steine nach den geforderten Regeln auf dem 3×10-Spielbrett zu verteilen.
Oder, falls man die Möglichkeit ohne Steine nicht mitzählen möchte: Es gibt 47002 Möglichkeiten, einen oder mehrere (mehr als 10 sind übrigens nicht möglich) Steine nach den geforderten Regeln auf dem 3×10-Spielbrett zu verteilen.
Zum Ausdrucken als pdf-File oder als ps-File