Beispiellösungen zu Aufgabenblatt 52

aktualisiert: 31. Mai 2006

$drucken$ Zum Ausdrucken als pdf-File oder als ps-File

Aufgabe 1

Vor kurzem gelang Andrew Wiles der Beweis des großen Fermatschen Satzes. Dieser besagt, dass die Gleichung

xⁿ + yⁿ = zⁿ

keine Lösung mit positiven ganzen Zahlen x, y, z hat, wenn n $\geq$ 3 ist. Über mehrere Jahrhunderte hinweg hatten sich die Mathematiker an diesem Problem erfolglos versucht.

Zeige den ,,sehr kleinen`` Fermatschen Satz: Die Gleichung

n^x + n^y = n^z

hat keine Lösung mit positiven ganzen Zahlen x, y, z, wenn n $\geq$ 3 ist.

Lösung:

Da nach Voraussetzung x > 0 und y > 0 ist und außerdem n $\geq$ 3 gelten soll, muss z > x und z > y sein und wir können die Gleichung n^x + n^y = n^z durch n^z teilen. Wir erhalten

n^x-z + n^y-z = 1.

Nun zeigen wir, dass die linke Seite der Gleichung für n $\geq$ 3 immer kleiner als 1 ist, die Gleichung also für n $\geq$ 3 keine Lösung besitzt: Weil x - z und y - z nach obiger Überlegung jeweils höchstens gleich -1 sein können und die Summe n^x-z + n^y-z um so größer wird, je größer x - z und y - z werden, ist sie also maximal für x - z = y - z = - 1. Dann ist n^x-z + n^y-z = n^-1 + n^-1. Der Term n^-1 + n^-1 = ${\frac{{1}}{{n}}}$ + ${\frac{{1}}{{n}}}$ wiederum wird dann maximal, wenn n möglichst klein ist, also wenn n gerade gleich 3 ist. Wir erhalten, dass n^x-z + n^y-z maximal ${\frac{{1}}{{3}}}$ + ${\frac{{1}}{{3}}}$ = ${\frac{{2}}{{3}}}$ sein kann und damit in keinem Fall gleich 1 ist. Die Gleichung n^x + n^y = n^z hat also für n $\geq$ 3 keine Lösung.

Alternative Lösungsmöglichkeit:

Man kann ohne Beschränkung der Allgemeinheit annehmen, dass z > y $\geq$ x gilt. Dann erhält man durch Ausklammern von n^x:

n^{x .}(1 + n^y-x) = n^z

mit y - x $\geq$ 0. Die höchste Potenz von n, die die linke Seite der Gleichung teilt, ist n^x, weil (1 + n^y-x) wegen n $\geq$ 3 nicht durch n teilbar ist. Die rechte Seite der Gleichung ist aber durch n^z teilbar. Da z > x gilt, können die beiden Seiten nicht gleich sein.

Bemerkung: Für n = 2 hat die Gleichung n^x + n^y = n^z Lösungen mit positiven ganzen Zahlen, denn es gilt 2^x + 2^x = 2^x+1.

Aufgabe 2

An der Wand im Wohnzimmer von Oma Kruse hängt eine Uhr. Die Wand ist genau ${\frac{{\sqrt{3}}}{{2}}}$ -mal so hoch wie breit. Zum Frühstück schaut Oma Kruse auf die Uhr und stellt fest, dass der kleine Zeiger der Uhr genau in die linke obere Ecke der Wand zeigt. Drei Stunden später, zum Mittagessen, zeigt der kleine Zeiger in die rechte obere Ecke. Zum Kaffee schließlich, noch einmal zwei Stunden später, zeigt der kleine Zeiger in die rechte untere Ecke.

Wann hat Oma Kruse gefrühstückt?

Lösung:

Eine ganze Drehung des kleinen Zeigers der Uhr entspricht einer Zeitdauer von zwölf Stunden. Also entsprechen die drei Stunden zwischen Frühstück und Mittagessen einer Drehung um ${\frac{{3h}}{{12h}}}$ ^.360 = 90 Grad. Die zwei Stunden zwischen Mittagessen und Kaffee entsprechen einer Drehung um ${\frac{{2h}}{{12h}}}$ ^.360 = 60 Grad.

Sei nun mit U der Mittelpunkt der Uhr bezeichnet, mit A die rechte untere Ecke der Wand, mit B die rechte obere Ecke und mit C die linke obere Ecke. Der Zeiger zeigt also zum Frühstück in Richtung des Punktes C, zum Mittag in Richtung B und zum Kaffee in Richtung A.

$\includegraphics[width=7cm]{loes52_2_a.eps}$

Deshalb ist $\angle$ BUC = 90^o und $\angle$ AUB = 60^o. Sei E der Fußpunkt des Lotes von U auf die Strecke CB. Dann ist $\alpha$ : = $\angle$ EUC der Winkel zwischen Frühstücksstellung und 12-Uhr-Stellung des kleinen Zeigers. Da die beiden Dreiecke CUB und CUE in zwei Winkeln übereinstimmen, ist auch der dritte Winkel identisch, also $\angle$ CBU = $\alpha$ . Aus $\angle$ AUB = 60^o und $\angle$ UBA = 90^o - $\alpha$ ergibt sich: $\angle$ BAU = 180^o - 60^o - (90^o - $\alpha$ ) = 30^o + $\alpha$ .

Sei a die Länge der Strecke CB und b die Länge der Strecke UB. Damit hat nach Voraussetzung die Strecke AB die Länge ${\frac{{\sqrt{3}}}{{2}}}$ ^.a. Im rechtwinkligen Dreieck UBC gilt: sin(90^o - $\alpha$ ) = ${\frac{{b}}{{a}}}$ $\iff$ b = a^.sin(90^o - $\alpha$ ). Nach dem Sinussatz gilt im Dreieck ABU: ${\frac{{\sin(30^\circ +\alpha)}}{{b}}}$ = ${\frac{{\sin(60^\circ )}}{{\frac{\sqrt{3}}{2}\cdot a}}}$ . Ersetzen von b liefert mit Hilfe von sin(60^o) = ${\frac{{\sqrt{3}}}{{2}}}$ :

$\displaystyle {\frac{{\sin(30^\circ +\alpha)}}{{a\cdot \sin(90^\circ -\alpha)}}}$ = $\displaystyle {\frac{{\sin(60^\circ )}}{{\frac{\sqrt{3}}{2}\cdot a}}}$ = $\displaystyle {\frac{{1}}{{a}}}$ $\displaystyle \iff$ sin(30^o + $\displaystyle \alpha$ ) = sin(90^o - $\displaystyle \alpha$ )

Da $\alpha$ zwischen 0^o und 90^o liegen muss, folgt: $\alpha$ + 30^o = 90^o - $\alpha$ $\iff$ $\alpha$ = 30^o. Eine Drehung des kleinen Zeigers um den Winkel 30 Grad entspricht einer Zeitdauer von ${\frac{{30}}{{360}}}$ ^.12 = 1 Stunde.

Oma Kruse hat also eine Stunde vor 12 Uhr, d. h. genau um 11 Uhr gefrühstückt.

Eine alternative Lösung (fast) ohne Verwendung von Winkelfunktionen ergibt sich zum Beispiel wie folgt:

$\includegraphics[width=7cm]{loes52_2_b.eps}$

Wie oben überlegt man sich, dass $\angle$ BUC = 90^o und $\angle$ AUB = 60^o gelten muss. Nun sei N der Mittelpunkt von BC. Dann ist aufgrund des gewählten Seitenverhältnisses im Rechteck das Dreieck ABN ein ,,halbes`` gleichseitiges Dreieck (beachte hierzu: Die Höhe in einem gleichseitigen Dreieck der Seitenlänge x hat die Länge ${\frac{{\sqrt{3}}}{{2}}}$ ^.x). Also ist $\angle$ ANB = 60^o. Nach dem Peripheriewinkelsatz ist also U gerade der (neben B zweite) Schnittpunkt des Umkreises des Dreiecks ABN mit dem Thaleskreis über BC. Sei D der Mittelpunkt von NA und damit der Mittelpunkt des Umkreises vom Dreieck ABN.

Weil das Dreieck DBN gleichseitig ist (gleichschenklig mit | ND| = | BD| und Basiswinkel 60^o), ist dann | BD| = | NB| = | ND| = | NU| = | NC| = ${\frac{{1}}{{2}}}$ ^.a. Aus Symmetriegründen (Spiegelachse ND) ist auch das Dreieck DNU gleichseitig und damit dann auch das Dreieck UNC. Hieraus folgt schließlich, dass das Lot von U auf NC mit dem Strahl UC einen 30^o-Winkel einschließt; die Oma frühstückt also um 11 Uhr.

Aufgabe 3

Früher mussten bei der Eisenbahn die Dampflokomotiven oft gewendet werden. Dazu benutzte man auch so genannte Gleisdreiecke oder Gleisdreisterne, vgl. Abbildung. Zum Wenden muss man offensichtlich jede Weiche genau einmal stellen. In Mals in Südtirol gibt es sogar einen Gleisfünfstern, der braucht weniger Platz, aber man muss mehr Weichen stellen.

$\includegraphics[width=12cm]{gleisdreifuenf}$

Interessant wird es, wenn man einen Wagen wenden will (auch das kommt vor), denn auf die kurzen Gleisabschnitte hinter den Weichen an den Sternspitzen passt nur ein Wagen oder eine Lok. Wie oft muss man beim Gleisdrei- bzw. -fünfstern eine Weiche stellen, um einen Wagen mit Hilfe einer Lok zu wenden? Bringt es Erleichterung, wenn man eine zweite Lok in das ,,Gleislabyrinth`` schickt? Und schließlich: Wie lauten die Anzahlen allgemein für einen (2n + 1)-Stern?

Bemerkung: Jede Weiche soll zu Beginn so gestellt sein, wie sie beim ersten Befahren gebraucht wird.

Lösung:

Wir wenden zunächst einen Wagen im Gleisdreistern mit einer Lok. Sie schiebt ihn zuerst auf z. B. das obere Endstück, was nach Voraussetzung noch ohne Weichenstellen geht. Um den Wagen dann weiterzubewegen, muss die Lokomotive von der anderen Seite der Weiche an dieses Ende heranfahren. Dazu muss sie einmal fast ganz um den Stern herumfahren, wobei jede Weiche (also drei) einmal gestellt wird.

Wenn die Lok den Wagen aus dem Gleisende herausgezogen hat, kann sie ihn natürlich nicht auf das nächste Ende abstellen. Dazu muss sie wieder auf die andere Seite des Wagens fahren - was wieder drei Weichenumstellungen plus eine weitere kostet, weil die Weiche, von der der Wagen gerade heruntergezogen wurde, ,,falsch`` stand. Und auch zum Einschieben des Wagens muss noch die Weiche gestellt werden, über die zuvor die Lok gewendet hatte. Zum Herausholen des Wagens muss die Lok nun erneut um den Stern fahren (drei Weichenumstellungen), dann ist sie aber schon fertig - insgesamt wurden elf Weichenumstellungen benötigt.

$\includegraphics[width=12cm]{loes_gleisdrei}$

Für das Wenden eines Wagens auf einem Gleis-k-Stern mit k = 2n + 1 erkennt man nun folgendes Prinzip: Wir betrachten den Aufwand, um den Wagen, nachdem er in ein Gleisende geschoben wurde, in das nächste Gleisende zu bringen. Zuerst muss also wie oben die Lok von der anderen Weichenseite an den Wagen heranfahren, um ihn herausziehen zu können. Dazu muss sie einmal durch den gesamten Stern fahren, das braucht also k Weichenumstellungen. Nach dem Rausziehen muss sie wieder herumfahren, um ihn in das nächste Ende hineinschieben zu können, das braucht wieder k plus eine Weichenumstellungen plus eine Umstellung zum Hereinschieben in das Gleisende.

Der komplette Wendevorgang setzt sich nun zusammen aus dem Einschieben in die erste Spitze, das kein Weichenstellen erfordert; dann muss der Wagen von der ersten zu der (k - 1)-ten Spitze gebracht werden, das ist ((k - 1) - 1) = (k - 2) Mal der oben beschriebene Ablauf und man braucht (k - 2)^.(2k + 2) Stellvorgänge. Dann steht die Lok noch am falschen Ende der Weiche, muss also noch einmal komplett durch den Stern und kann dann den Wagen herausziehen.

Zusammen muss man (k - 2)^.(2k + 2) + k = 2k² - k - 4 Mal eine Weiche stellen.

Nun zu der Frage, ob man mit einer zweiten Lokomotive Zeit sparen kann. Im Prinzip sieht es recht vielversprechend aus: Man kann die eine Lok vor den Wagen stellen, so dass diese ihn immer aus einem Gleisende herauszieht und die andere ihn immer hineindrückt. Der Vorgang, den Wagen von einem Gleisende zum nächsten zu bringen, erfordert dann folgende Rangiermanöver: Die Lok, die den Wagen in das Gleisende geschoben hat, fährt wieder ein Stück zurück, um die Weiche freizugeben. Die Weiche wird gestellt und die andere Lok, die weiter davor gewartet hat, zieht den Wagen heraus. Sie lässt ihn in der Mitte des Gleises stehen, fährt auf das nächste Gleisende (dort steht die Weiche passend, weil die Lok zu Anfang von dort gekommen ist, vgl. unten) und von diesem Ende (Weichenumstellen!) zur anderen Seite heraus, um wieder zu warten. Die schiebende Lok fährt nun über das erste Gleisende an den Wagen heran (dafür muss die Weiche zweimal gestellt werden) und drückt ihn in das nächste Ende - auch dafür muss die Weiche dort noch einmal gestellt werden, weil die vordere Lok dieses Ende in die andere Richtung verlassen hatte.

Für einen solchen Schritt muss also fünfmal eine Weiche gestellt werden.

$\includegraphics[width=12cm]{loes_zweilokgut}$

Zu Anfang muss die eine Lok jedoch noch in die vordere Position gebracht werden; eine Möglichkeit dazu ist, dass sie einfach vorausfährt, quasi um die erste Ecke herum, und es muss dafür zweimal die Weiche am ersten Ende gestellt werden.

Nach diesem Anfang folgen wie oben k - 2 Schritte, den Wagen ein Gleisende weiterzubringen.

Zum Schluss muss wieder die letzte Weiche gestellt werden, um den Wagen herausziehen zu können, dazu noch die erste Weiche, die ja noch vom Anfang anders steht. Außerdem muss die schiebende Lok aus dem Stern herausfahren, das kostet zwei weitere Umstellungen.

Insgesamt braucht man bei diesem Verfahren also 2 + (k - 2)^.5 + 4 = 5k - 4 Weichenumstellungen.

Die andere Möglichkeit zu beginnen, ist, die ziehende Lok andersherum in den Stern einfahren zu lassen. Wenn man zuerst mit der einen Lok den Wagen einschiebt und dann die andere Lok einfahren lässt, erfordert das k - 1 Weichenumstellungen. Der Vorteil dabei ist, dass die erste Weiche dann am Ende nicht umgestellt zu werden braucht. Oder man lässt analog am Ende die schiebende Lok andersherum herausfahren. Man erhält eine Gesamtzahl von k - 1 + (k - 2)^.5 + 3 = 6k - 8 Stellvorgängen. Für k = 3 bringt das mit 6^.3 - 8 = 10 gegen 2 + 1^.5 + 4 = 11 Weichenumstellungen einen Gewinn von einer Umstellung, für größere k bringt das keinen Vorteil.

$\includegraphics[width=12cm]{loes_zweilok}$

Für k = 3 ist 2k² - k - 4 = 11 > 10, daher ist hier das zweite Verfahren einfacher, jedoch nur knapp. Für k $\geq$ 5 hat man die Abschätzung 2k² - k - 4 = (2k - 1)^.k - 4 $\geq$ 9k - 4 > 5k - 4. Hier ist der Unterschied schon deutlicher, weswegen man dann wirklich zwei Lokomotiven einsetzen sollte.

Aufgabe 4

Zwei verschiedene Geraden in der Ebene können sich entweder in keinem oder in einem Punkt schneiden, je nachdem, ob sie parallel sind oder nicht.

Wie viele verschiedene mögliche Schnittpunktanzahlen gibt es für zehn verschiedene Geraden in der Ebene, wenn keine drei Geraden durch einen gemeinsamen Punkt gehen sollen?

Lösung:

Zunächst kann man die Geraden in Gruppen paralleler Geraden so einteilen, dass zwei Geraden genau dann in einer Gruppe sind, wenn sie parallel sind.

Wenn zum Beispiel keine zwei der Geraden parallel sind, dann gibt es genau zehn Gruppen mit jeweils einer Gerade. In Kurzform notieren wir dies als (1, 1, 1, 1, 1, 1, 1, 1, 1, 1).

Gibt es hingegen eine Gruppe mit sechs parallelen Geraden, dann eine andere Gruppe mit drei Parallelen und schließlich eine einzelne Gerade, die zu keiner der vorigen parallel ist, so notieren wir dies als (6, 3, 1). Wir schreiben also stets die Größen der vorkommenden Gruppen in abnehmender Reihenfolge hintereinander. Da die Summe der Gruppengrößen stets genau 10 ist, spricht man hierbei auch von Partitionen der Zahl 10.

**Abbildung:** Zwei mögliche Konstellationen zur selben Partition (5, 3, 1, 1)
$\includegraphics[width=7cm]{loes52_4.eps}$

Wichtig ist nun, dass es für die Anzahl der Schnittpunkte unter den Geraden nicht auf die genaue Lage der Geraden, sondern einzig auf die ihnen zugeordnete Partition ankommt!

Dies liegt einfach daran, dass es für das Vorhandensein eines Schnittpunktes nur darauf ankommt, ob zwei Geraden parallel sind oder nicht, und nicht, wie ünparallelßie sind.

Für eine Partition der Form (n₁, n₂,..., n_k) schneidet dabei jede Gerade einer Gruppe genau jede Gerade der anderen Gruppen; das sind also genau n₁^.(10 - n₁) + n₂^.(10 - n₂) +...+ n_k^.(10 - n_k) Überschneidungen. Hierbei haben wir aber jeden Schnittpunkt zweimal gezählt (nämlich den Schnittpunkt von Gerade g und h einmal als ,, g schneidet h`` und einmal als ,,h schneidet g``.)

Also gibt es für die Konstellation (Partition) (n₁, n₂,..., n_k) genau

S =	$\displaystyle {\frac{{1}}{{2}}}$ ^. $\displaystyle \left(\vphantom{n_1\cdot (10-n_1)+n_2\cdot(10-n_2)+\ldots+n_k\cdot(10-n_k) }\right.$ n₁^.(10 - n₁) + n₂^.(10 - n₂) +...+ n_k^.(10 - n_k) $\displaystyle \left.\vphantom{n_1\cdot (10-n_1)+n_2\cdot(10-n_2)+\ldots+n_k\cdot(10-n_k) }\right)$
	= 5^.(n₁ + n₂ +...+ n_k) - $\displaystyle {\frac{{1}}{{2}}}$ $\displaystyle \left(\vphantom{n_1^2+n_2^2+\ldots+n_k^2}\right.$ n₁² + n₂² +...+ n_k² $\displaystyle \left.\vphantom{n_1^2+n_2^2+\ldots+n_k^2}\right)$
	= 50 - $\displaystyle {\frac{{1}}{{2}}}$ $\displaystyle \left(\vphantom{n_1^2+n_2^2+\ldots+n_k^2}\right.$ n₁² + n₂² +...+ n_k² $\displaystyle \left.\vphantom{n_1^2+n_2^2+\ldots+n_k^2}\right)$

Schnittpunkte. Die folgende Tabelle enthält nun alle möglichen Partitionen und die zugehörigen Schnittpunktanzahlen.

Partition	S	Partition	S	Partition	S
(10)	0	(5, 3, 2)	31	(3, 3, 3, 1)	36
(9, 1)	9	(5, 3, 1, 1)	32	(3, 3, 2, 2)	37
(8, 2)	16	(5, 2, 2, 1)	33	(3, 3, 2, 1, 1)	38
(8, 1, 1)	17	(5, 2, 1, 1, 1)	34	(3, 3, 1, 1, 1, 1)	39
(7, 3)	21	(5, 1, 1, 1, 1, 1)	35	(3, 2, 2, 2, 1)	39
(7, 2, 1)	23	(4, 4, 2)	32	(3, 2, 2, 1, 1, 1)	40
(7, 1, 1, 1)	24	(4, 4, 1, 1)	33	(3, 2, 1, 1, 1, 1, 1)	41
(6, 4)	24	(4, 3, 3)	33	(3, 1, 1, 1, 1, 1, 1, 1)	42
(6, 3, 1)	27	(4, 3, 2, 1)	35	(2, 2, 2, 2, 2)	40
(6, 2, 2)	28	(4, 3, 1, 1, 1)	36	(2, 2, 2, 2, 1, 1)	41
(6, 2, 1, 1)	29	(4, 2, 2, 2)	36	(2, 2, 2, 1, 1, 1, 1)	42
(6, 1, 1, 1, 1)	30	(4, 2, 2, 1, 1)	37	(2, 2, 1, 1, 1, 1, 1, 1)	43
(5, 5)	25	(4, 2, 1, 1, 1, 1)	38	(2, 1, 1, 1, 1, 1, 1, 1, 1)	44
(5, 4, 1)	29	(4, 1, 1, 1, 1, 1, 1)	39	(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)	45

Man sieht somit, dass es genau die folgenden 27 möglichen Schnittpunktanzahlen gibt: 0, 9, 16, 17, 21, 23, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45.

$drucken$ Zum Ausdrucken als pdf-File oder als ps-File