Beispiellösungen zu Aufgabenblatt 31

aktualisiert: 17. Dezember 2003

Aufgabe 1

An einer langen Lichterkette gibt es 2003 Glühlampen, die von 1 bis 2003 durchnummeriert sind und alle einen eigenen An/Aus-Schalter besitzen. Zu Beginn sind alle Lampen aus.
Nun geht eine erste Person alle Lampen durch und betätigt die Schalter aller Lämpchen, deren Nummer durch 1 teilbar ist (das sind natürlich alle). Dann geht eine zweite Person die Lichterkette entlang und betätigt alle Schalter, deren Lampennummer durch 2 teilbar ist usw. Zum Schluss geht die 2003. Person entlang und betätigt alle Schalter, deren Lampennummern durch 2003 teilbar sind (das ist dann nur noch das letzte Lämpchen). Wie viele Lämpchen sind nach dieser Prozedur angeschaltet?

Lösung:

Der Schalter der Lampe mit der Nummer n wird während der gesamten Prozedur offenbar genau so oft betätigt, wie n Teiler hat, denn die k-te Person betätigt den Schalter n genau dann, wenn k| n gilt.
Bei einer natürlichen Zahl n, die keine Quadratzahl ist, treten die Teiler aber immer in Paaren auf. Zu einem Teiler k gibt es immer einen so genannten komplementären Teiler k', für den k^.k' = n ist, und dabei ist k $\neq$ k', denn ansonsten wäre n = k² eine Quadratzahl. Wir können also die Teiler einer Nicht-Quadratzahl n in Paare komplementärer Teiler aufteilen. Eine solche Zahl hat also stets geradzahlig viele Teiler. (Beispiel: 12 = 1^.12 = 2^.6 = 3^.4).
Genauso sieht man, dass Quadratzahlen n = k² stets ungeradzahlig viele Teiler haben, denn auch ihre Teiler lassen sich wieder in Paare komplementärer Teiler aufteilen, wobei nur k als einziger übrig bleibt (denn er ist sein eigener komplementärer Teiler).
Daher werden Schalter, deren Nummer keine Quadratzahl ist, geradzahlig oft betätigt und die zugehörigen Lampen sind somit am Ende der Prozedur genau wie zu Beginn aus. Schalter, deren Nummer eine Quadratzahl ist, werden ungeradzahlig oft betätigt und somit sind die entsprechenden Lampen nach der Prozedur angeschaltet.
Wegen 44² = 1936 < 2003 < 2025 = 45² gibt es genau 44 unter den 2003 Lampen, deren Nummer eine Quadratzahl ist, so dass also am Ende der Prozedur genau 44 Lampen an sind.

Aufgabe 2

Angenommen, für zwei reelle Zahlen x und y gilt 2x² - 2xy + y² = 0. Welche(n) Wert(e) kann dann (x + 41)² + (y - 17)² + 33 annehmen?

Lösung:

Wenn für zwei reelle Zahlen x, y die Gleichung 2x² - 2xy + y² = 0 gilt, so kann man dies umschreiben zu x² + (x - y)² = 0. Da Quadrate von null verschiedener Zahlen positiv sind, muss also x = 0 und x - y = 0 gelten. Daraus folgt aber auch y = 0. Demnach kann (x + 41)² + (y - 17)² + 33 nur einen Wert annehmen, nämlich (0 + 41)² + (0 - 17)² + 33 = 2003.
Diesen Wert nimmt der Term auch an, denn in der Tat ist x = y = 0 Lösung von 2x² - 2xy + y² = 0.

Aufgabe 3

Zeige, dass es für alle natürlichen Zahlen n $\geq$ 10 zwischen n und 3^.n eine Kubikzahl gibt.

Lösung:

Angenommen, es gäbe für ein solches n $\geq$ 10 keine Kubikzahl zwischen n und 3^.n.
Dann gäbe es eine natürliche Zahl k mit k³ $\leq$ n und (k + 1)³ $\geq$ 3n. Daraus folgt dann k $\leq$ $\sqrt[3]{{n}}$ und k + 1 $\geq$ $\sqrt[3]{{3n}}$ = $\sqrt[3]{{3}}$ ^. $\sqrt[3]{{n}}$ . Hieraus folgt für n $\geq$ 27 weiter:

1	=	(k + 1) - k
	$\displaystyle \geq$	$\displaystyle \sqrt[3]{{3}}$ ^. $\displaystyle \sqrt[3]{{n}}$ - $\displaystyle \sqrt[3]{{n}}$
	=	$\displaystyle \left(\vphantom{\sqrt[3]{3}-1}\right.$ $\displaystyle \sqrt[3]{{3}}$ - 1 $\displaystyle \left.\vphantom{\sqrt[3]{3}-1}\right)$ ^. $\displaystyle \sqrt[3]{{n}}$
	$\displaystyle \geq$	$\displaystyle \left(\vphantom{\sqrt[3]{3}-1}\right.$ $\displaystyle \sqrt[3]{{3}}$ - 1 $\displaystyle \left.\vphantom{\sqrt[3]{3}-1}\right)$ ^.3
	>	1.

Die letzte Abschätzung folgt aus 81 > 64, was nach Ziehen der dritten Wurzel zu 3^. $\sqrt[3]{{3}}$ > 4 wird.
Also erhält man für n $\geq$ 27 einen Widerspruch zur obigen Annahme. Damit gibt es in diesem Fall stets eine Kubikzahl zwischen n und 3^.n.
Für die übrigen Fälle 10 $\leq$ n < 27 ist offenbar 27 = 3³ eine Kubikzahl zwischen n und 3^.n. Damit ist die Aussage auch hier bewiesen.

Aufgabe 4

Auf dem Tisch liegt ein Kartenstapel mit 52 Karten, nummeriert und geordnet von 1 bis 52, wobei die Karte mit der Nummer 1 ganz oben liegt. Der Stapel soll nun gemischt werden durch wiederholtes Ausführen der folgenden Operation: Teile den Stapel durch Abheben in zwei Teilstapel und nimm von diesen in beliebiger Reihenfolge die Karten von oben, um einen neuen gemeinsamen Stapel zu formen.
Für acht Karten 1, 2, 3, 4, 5, 6, 7, 8 könnte man zum Beispiel die beiden Stapel 1, 2, 3, 4, 5 und 6, 7, 8 bilden und dann daraus den neuen Stapel 6, 1, 2, 3, 7, 8, 4, 5.
Gib eine Folge solcher Operationen an, die den Anfangsstapel von 52 Karten ,,umdreht``, ihn also in 52, 51,..., 3, 2, 1 überführt!
Geht dies mit fünf oder weniger Operationen?

Lösung:

Die übersichtlichste Prozedur ist wohl diejenige, bei der in jedem Schritt genau eine Karte neu eingeordnet wird. Dazu wird der Stapel in 1 und 2, 3,..., 52 getrennt und dann zum Stapel 2, 3,..., 52, 1 gemacht. Im n-ten Schritt ( n $\in$ {2,..., 51}) wird der vorhandene Stapel n, n + 1, n + 2,..., 52, n - 1, n - 2,..., 1 in die Stapel n + 1, n + 2,..., 52, n - 1, n - 2,..., 1 und n getrennt und zum Stapel n + 1, n + 2,..., 52, n, n - 1, n - 2,..., 1 zusammengefügt. Nach der 51. Operation liegt der gewünschte Stapel 52, 51,..., 3, 2, 1 vor.

Es geht also zumindest mit 51 Operationen.

Dagegen geht es nicht mit weniger als 6 Operationen. Zur Begründung: Wir definieren einen Block von Karten als eine Folge von Karten i, i + 1, i + 2,..., i + j, die in dieser Reihenfolge im Stapel vorhanden ist, und die Folge soll zu keiner Seite fortsetzbar sein, also maximal gewählt sein. So hat zum Beispiel der Stapel 2, 1, 3, 4, 6, 5, 7 die Blöcke 1 und 2, 3, 4, 5 und 6, 7.
Am Anfang unserer Umordnungsaktion liegt somit genau ein Block vor. Wir machen die folgende Beobachtung: Die Karten in jedem der beiden Teilstapel, die bei der ersten Operation gebildet werden, können beim Zusammlegen ihre Reihenfolge nicht ändern. Es werden nur die beiden Blöcke von Zahlen 1,..., k und k + 1,..., 52 ineinandergefügt. Bei der zweiten Operation können durch das Teilen in zwei Stapel bestenfalls beide Blöcke aus der ersten Teilung wiederum in je zwei Blöcke getrennt werden, so dass maximal vier Blöcke entstehen. Es ist unschwer zu erkennen, dass nach n Operationen höchstens 2ⁿ Blöcke vorliegen können. Zur vollständigen Umordnung des Stapels ist es jedoch nötig, 52 Blöcke gebildet zu haben. Da 2⁵ = 32 < 52 ist, kann dies mit fünf Operationen noch nicht erfolgt sein.

Bemerkung: Mit sechs Operationen ist die Umordnung möglich, und der vorangehende Absatz liefert auch einen Hinweis, wie man dies (nur) erreichen kann: Man muss die Blöcke so spalten und ineinanderfügen, dass man in den nachfolgenden Schritten immer noch weiter so viele Blöcke wie möglich spalten kann (ungefähr jedenfalls, weil wir nur 52 und nicht 64 Karten haben). Man muss sie also insbesondere so weit wie möglich ineinander verschränken. (Auf diese Weise bekommt man mit sechs Operationen tatsächlich bis zu 2⁶ = 64 Karten umgeordnet.) Eine Möglichkeit dazu ist die folgende, sie ist direkt von der einzigen Möglichkeit für 64 Karten abgeleitet:

Zu Beginn	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52
1. Teilen	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32 und
	33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52
Nach erster Operation	33, 1, 34, 2, 35, 3, 36, 4, 37, 5, 38, 6, 39, 7, 40, 8, 41, 9, 42, 10, 43, 11, 44, 12, 45, 13, 46, 14, 47, 15, 48, 16, 49, 17, 50, 18, 51, 19, 52, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32
2. Teilen	33, 1, 34, 2, 35, 3, 36, 4, 37, 5, 38, 6, 39, 7, 40, 8, 41, 9, 42, 10, 43, 11, 44, 12, 45, 13, 46, 14, 47, 15, 48, 16 und
	49, 17, 50, 18, 51, 19, 52, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32
Nach zweiter Operation	49, 33, 17, 1, 50, 34, 18, 2, 51, 35, 19, 3, 52, 36, 20, 4, 37, 21, 5, 38, 22, 6, 39, 23, 7, 40, 24, 8, 41, 25, 9, 42, 26, 10, 43, 27, 11, 44, 28, 12, 45, 29, 13, 46, 30, 14, 47, 31, 15, 48, 32, 16
3. Teilen	49, 33, 17, 1, 50, 34, 18, 2, 51, 35, 19, 3, 52, 36, 20, 4, 37, 21, 5, 38, 22, 6, 39, 23, 7, 40, 24, 8 und
	41, 25, 9, 42, 26, 10, 43, 27, 11, 44, 28, 12, 45, 29, 13, 46, 30, 14, 47, 31, 15, 48, 32, 16
Nach dritter Operation	49, 41, 33, 25, 17, 9, 1, 50, 42, 34, 26, 18, 10, 2, 51, 43, 35, 27, 19, 11, 3, 52, 44, 36, 28, 20, 12, 4, 45, 37, 29, 21, 13, 5, 46, 38, 30, 22, 14, 6, 47, 39, 31, 23, 15, 7, 48, 40, 32, 24, 16, 8
4. Teilen	49, 41, 33, 25, 17, 9, 1, 50, 42, 34, 26, 18, 10, 2, 51, 43, 35, 27, 19, 11, 3, 52, 44, 36, 28, 20, 12, 4 und
	45, 37, 29, 21, 13, 5, 46, 38, 30, 22, 14, 6, 47, 39, 31, 23, 15, 7, 48, 40, 32, 24, 16, 8
Nach vierter Operation	49, 45, 41, 37, 33, 29, 25, 21, 17, 13, 9, 5, 1, 50, 46, 42, 38, 34, 30, 26, 22, 18, 14, 10, 6, 2, 51, 47, 43, 39, 35, 31, 27, 23, 19, 15, 11, 7, 3, 52, 48, 44, 40, 36, 32, 28, 24, 20, 16, 12, 8, 4
5. Teilen	49, 45, 41, 37, 33, 29, 25, 21, 17, 13, 9, 5, 1, 50, 46, 42, 38, 34, 30, 26, 22, 18, 14, 10, 6, 2 und
	51, 47, 43, 39, 35, 31, 27, 23, 19, 15, 11, 7, 3, 52, 48, 44, 40, 36, 32, 28, 24, 20, 16, 12, 8, 4
Nach fünfter Operation	51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2
6. Teilen	51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1 und
	52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2
Nach sechster Operation	52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

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