Beispiellösungen zu Aufgabenblatt 39

aktualisiert: 24. November 2004

Aufgabe 1


Zu Ehren des 39. Aufgabenblattes betrachten wir alle Vielfachen der Zahl 39. Was ist die Menge aller Quersummen dieser Zahlen?


Lösung:


Als Quersummen kommen genau die Vielfachen von 3 vor: 3, 6, 9, 12,...


(Um Missverständnissen vorzubeugen: In dieser Aufgabe verstehen wir unter den natürlichen Zahlen $ \mathbbm$N die positiven ganzen Zahlen ohne Null, und ebenso betrachten wir die Zahl Null nicht als Vielfaches einer natürlichen Zahl.)


Da 39 = 3 . 13 ist, sind alle Vielfachen von 39 auch Vielfache von 3, ihre Quersumme ist also jeweils durch 3 teilbar.

Umgekehrt kommen auch alle Vielfachen von 3 als Quersumme eines Vielfachen von 39 vor:

Es ist 10101 = 39 . 259 ein Vielfaches von 39, das die Quersumme 3 hat. Mit seiner Hilfe können wir nun systematisch alle Vielfachen von 3 als Quersumme eines Vielfachen von 39 erzeugen. Indem wir die 10101 zweimal hintereinander schreiben, erhalten wir eine Zahl 1010110101 mit Quersumme 6, die ebenfalls ein Vielfaches von 39 ist:

1010110101 = 1010100000 + 10101 = 10101 . 105 + 10101    
  = 39 . 259 . 105 + 39 . 259 = 39 . (259 . 105 + 259).    

Genauso hat 101011010110101 die Quersumme 9 und ist Vielfaches von 39:

101011010110101 = 10101 . 105 . 2 + 10101 . 105 + 10101    
  = 39 . (259 . 105 . 2 + 259 . 105 + 259).    

Setzen wir das so fort, erhalten wir, dass k . 3 Quersumme der Zahl

10101 . 105 . (k-1) + 10101 . 105 . (k-2) +...+ 10101 . 105 . 1 + 10101      
= 39 . (259 . 105 . (k-1) + 259 . 105 . (k-2) +...+ 259 . 105 . 1 + 259)      

ist, also ebenfalls Quersumme eines Vielfachen von 39.


Ein paar Anmerkungen zur Aufgabe (und zur Zahl 39):

Vielfache von 39 mit Quersummen 6 und 9 - und damit nach dem oben beschriebenen Prinzip des Voreinandersetzens auch mit allen größeren durch 3 teilbaren Zahlen - finden sich mit 312 und 117 recht schnell, die 10101 als kleinstes Vielfaches mit Quersumme 3 zugegebenermaßen nicht.

Wie findet man so ein Vielfaches mit kleiner Quersumme im Allgemeinen? Ganz kurz gesagt: Man muss die Reste betrachten, die die Potenzen von 10 beim Teilen durch die zu untersuchende Zahl lassen, und dann schauen, ob man es schafft oder nicht, wenige dieser Reste zu einer durch die Zahl teilbaren Summe zu addieren. (Das Addieren der Reste entspricht dem Erhöhen der entsprechenden Ziffern!)

Und wie sieht die (Gesamt-)Lösung dieser Aufgabe im Allgemeinen aus? Das ist schwierig. Klar ist sofort: Für eine durch 9 teilbare Zahl kommen nur Zahlen aus 9$ \mathbbm$N in Frage (also Vielfache von 9), für eine durch 3, aber nicht durch 9 teilbare Zahl nur Zahlen aus 3$ \mathbbm$N. Für alle anderen Zahlen hat man, wenn man nur Teilbarkeit durch 3 betrachtet, keine Einschränkung.

Jedoch ergibt sich schnell eine andere Einschränkung, indem man sich Folgendes überlegt: Eine Quersumme 1 kann nur eine Zahl der Form 10k haben. Und diese Zahlen können nur Vielfache von Zahlen sein, die von der Form 2i5j mit i, j $ \in$ $ \mathbbm$N0 sind. Weitere Einschränkungen zu finden ist schon schwieriger und geht mehr oder weniger in die Tiefen der Zahlentheorie.

Es gibt anscheinend (so genau wissen wir das im Allgemeinen auch nicht) viele Zahlen, bei denen in der Tat die Menge der Quersummen ihrer Vielfachen eine der sich aus dem oben Gesagten ergebenden Mengen $ \mathbbm$N, $ \mathbbm$N $ \setminus$ {1}, 3$ \mathbbm$N oder 9$ \mathbbm$N ist. Jedoch gibt es auch viele, die nicht alle diese Zahlen als Quersummen ihrer Vielfachen zulassen, z. B. die 11: Sie hat nur Vielfache mit Quersummen aus der Menge {2, 4, 6, 8, 10, 11, 12, 13,...}. Oder die 33: Bei ihr ist es die Menge {6, 12, 15, 18, 21,...}. Schließlich hat 41 die 5 als kleinste Quersumme eines Vielfachen, danach kommt erst die 10 und dann alle weiteren natürlichen Zahlen. (Zum Teil ist dies sogar nicht allzu schwer einzusehen - sei dies eine Aufforderung, sich damit auseinanderzusetzen ...)

Es gibt sogar Zahlen, bei denen eine beliebig vorgegebene Anzahl von den ersten natürlichen Zahlen in dieser Liste fehlt! Andererseits ist für jede Zahl in der Liste der Quersummen der Vielfachen ab irgendeinem Wert jeder größere Wert vorhanden, bzw. je nach Teilbarkeit durch 3 jeder größere durch 3 bzw. 9 teilbare Wert.

Im ,,Lexikon der Zahlen``1 steht unter dem Stichwort 39: ,,Anscheinend die erste uninteressante Zahl (was diese Zahl natürlich besonders interessant macht, weil sie die erste Zahl mit dieser Eigenschaft ist).`` Da nun die Menge der Quersummen gleich der nach recht einfachen Überlegungen maximal möglichen Menge ist, ist die 39 auch unter diesem Gesichtspunkt nicht sonderlich interessant; allenfalls ist bemerkenswert, dass man für keine andere durch 3 und nicht durch 9 teilbare Zahl kleiner 57 so weit suchen muss, um ein Vielfaches mit Quersumme 3 zu finden. Das aber rechtfertigt sicherlich nicht einen Eintrag in besagtem Buch. Tut uns Leid für die 39; immerhin hat sie jetzt hier Beachtung gefunden.


Aufgabe 2


Katrin und Wolfgang spielen folgendes Spiel: Sie markieren auf einem Blatt Papier die Ecken eines regelmäßigen 2004-Ecks. Nun dürfen sie abwechselnd ziehen, wobei ein Zug darin besteht, zwei Ecken, die bisher noch nicht benutzt worden sind, durch eine Strecke zu verbinden. Dabei darf diese Strecke allerdings keine der bisher schon gezeichneten Strecken schneiden.
Verloren hat, wer keinen erlaubten Zug mehr machen kann. Wenn Katrin den ersten Zug macht, wer kann dann den Gewinn erzwingen?


Lösung:


Katrin kann den Sieg erzwingen.

Als Erstes verbindet sie zwei diametral gegenüberliegende Ecken, d. h. wenn wir die Ecken reihum von 1 bis 2004 durchnummerieren, so verbindet sie die Ecken 1 und 1003. Damit hat sie die Figur in zwei gleich geformte 1003-Ecke zerlegt, die wie Spiegelbilder zueinander sind. Alle weiteren Strecken müssen entweder in der einen oder in der anderen Hälfte gezogen werden, denn keine neue Strecke darf die erste schneiden.

Wenn Wolfgang dann einen Zug macht (er ist nach Katrins erstem Zug dran), kann Katrin denselben Zug in der anderen Hälfte ausführen, nur spiegelbildlich. Da danach die beiden Teile wieder Spiegelbilder voneinander sind (mitsamt allen eingezeichneten Strecken), kann Katrin auch weiterhin Spiegelbilder von Wolfgangs Zügen malen. Irgendwann kann dann Wolfgang keinen Zug mehr machen und hat verloren.


Aufgabe 3


Auf einem Holzbrett sind n Nägel eingeschlagen (n $ \geq$ 2). Jemand möchte ein geschlossenes Gummiband so entlang der Nägel spannen, dass jeder Nagel vom Gummiband berührt wird und sich das Band nirgends selbst überkreuzt.
Ist dies stets möglich oder gibt es ungünstige Verteilungen der Nägel, bei denen das nicht der Fall ist?


Lösung:


Es ist immer möglich, ein Gummiband so zu spannen, dass es alle Nägel berührt.

\includegraphics[height=35mm]{nagel1.eps} \includegraphics[height=35mm]{nagel2.eps} \includegraphics[height=35mm]{nagel3.eps}

Zum Beweis dieser Aussage geben wir zunächst ein Verfahren an, welches in jedem Fall eine gesuchte Umspannung erzeugt und zeigen anschließend, dass dieses Verfahren auch wirklich stets zum gewünschten Ergebnis führt.
Zunächst sei also das Verfahren beschrieben (man verfolge die Beschreibung am besten anhand der Abbildungen). Die Nagelpositionen seien durch eine Menge M von Punkten gegeben. Im ersten Schritt betrachte man die konvexe Hülle von M. Die konvexe Hülle ist die kleinste konvexe2 Menge, die alle Punkte von M enthält. Da M eine endliche Menge von Punkten ist, ist dies hier ein konvexes k-Eck mit 2 $ \leq$ k $ \leq$ n (damit wir nicht umständlich Fälle unterscheiden müssen, bezeichnen wir für k = 2 eine Strecke als Zweieck). Sei E1 die Menge derjenigen Punkte aus M, die auf dem Rand dieses k-Ecks liegen (das können durchaus mehr als nur die Ecken des k-Ecks sein!).
Wähle nun zwei beliebige, auf dem Rand des k-Ecks im Uhrzeigersinn benachbarte Punkte A1 und B1 aus E1 und spanne das (bisher offene) Gummiband zunächst entlang des k-Ecks von B1 nach A1. Dabei berührt das Gummiband alle Punkte aus E1. Gibt es nun weitere, noch unberührte Punkte, ist also M $ \setminus$ E1 nicht leer, so fahre man im zweiten Schritt mit der Restmenge an Punkten M2 = (M $ \setminus$ E1) $ \cup$ {A1, B1} fort.
Allgemein verfährt man nun im i-ten Schritt (i $ \geq$ 2) folgendermaßen: Betrachte alle Punkte Ei auf dem Rand der konvexen Hülle von Mi. Insbesondere sind Ai-1 und Bi-1 auf dem Rand. Wähle zwei im Uhrzeigersinn benachbarte Punkte Ai und Bi auf diesem Rand, wobei {Ai, Bi} $ \neq$ {Ai-1, Bi-1} sein soll. Dies ist stets möglich, weil der Rand von Mi mehr als zwei Punkte enthält. Spanne das Gummiband weiter von Bi-1 entlang des Randes der konvexen Hülle von Mi bis zum Punkt Ai und (das andere offene Ende des Bandes) gegen den Uhrzeigersinn von Ai-1 bis Bi. Gibt es jetzt noch weitere, unberührte Punkte, so fahre im nächsten Schritt mit der Menge Mi+1 = (Mi $ \setminus$ Ei) $ \cup$ {Ai, Bi} fort.
Gibt es keine unberührten Punkte mehr, dann verbinde Ai mit Bi und schließe somit das Gummiband. An welcher Seite der Nägel das Band jeweils herumgeführt werden muss, ergibt sich automatisch.


Da sich in jedem Schritt die Menge der vom Gummiband noch nicht berührten Punkte um wenigstens eins verringert, endet das Verfahren irgendwann mit einem geschlossenen Gummiband, das alle Punkte berührt.
Da die konvexe Hülle von Mi bis auf die Strecke Ai-1Bi-1 echt im Inneren der konvexen Hülle von Mi-1 liegt, kommt es beim beschriebenen Verfahren auch nie zu Überschneidungen das Gummibandes. Demnach endet das Verfahren stets mit dem gewünschten Ergebnis.


Aufgabe 4


Welche Paare (x, y) reeller Zahlen erfüllen die Gleichung

$\displaystyle \sqrt{{x^2+y^2+4x+4y+8}}$  +  $\displaystyle \sqrt{{x^2+y^2-2x-4y+5}}$  =  5 ?


Erste Lösung:


Angenommen, ein Paar (x, y) erfüllt die Gleichung. Dann gilt sicher auch

$\displaystyle \sqrt{{x^2+y^2+4x+4y+8}}$ = 5 - $\displaystyle \sqrt{{x^2+y^2-2x-4y+5}}$ (1)

bzw. nach Quadrieren

x2 + y2 + 4x + 4y + 8 = 25 - 10$\displaystyle \sqrt{{x^2+y^2-2x-4y+5}}$ + x2 + y2 - 2x - 4y + 5.

Weiter folgt nach Wegkürzen gleicher Terme auf beiden Seiten und Umordnen

10$\displaystyle \sqrt{{x^2+y^2-2x-4y+5}}$ = 22 - 6x - 8y; (2)

und hieraus folgt nach Quadrieren

100x2 + 100y2 - 200x - 400y + 500 = 484 + 36x2 + 64y2 - 264x - 352y + 96xy. (3)

Der Übersichtlichkeit halber kann und sollte man alle Terme auf eine Seite bringen und erhält

64x2 + 36y2 - 96xy + 64x - 48y + 16 = 0.

Mit geübtem Adlerauge erkennt man hier ein vollständiges Quadrat, so dass die letzte Gleichung äquivalent zu

(8x - 6y + 4)2 = 0        bzw.        8x - 6y + 4 = 0

ist. Demnach muss y = $ {\frac{{2}}{{3}}}$(2x + 1) sein.

Aber Achtung! Nicht jedes Paar (x, y) mit y = $ {\frac{{2}}{{3}}}$(2x + 1) ist auch Lösung der gegebenen Gleichung. In obiger Herleitung haben wir zweimal quadriert, und da Quadrieren keine Äquivalenzumformung ist, kann sich dabei die Lösungsmenge vergrößern. Schauen wir uns also die Rechnung an den besagten Stellen genauer an.
Jedes Paar (x, y) mit y = $ {\frac{{2}}{{3}}}$(2x + 1) erfüllt die Gleichung (3), denn danach folgen nur Äquivalenzumformungen. Eine Lösung von Gleichung (3) ist aber genau dann Lösung von Gleichung (2), wenn 22 - 6x - 8y $ \geq$ 0 ist, denn die Wurzel auf der linken Seite von (2) ist nicht negativ. Wegen y = $ {\frac{{2}}{{3}}}$(2x + 1) ist dies äquivalent zu 22 - 6x - $ {\frac{{16}}{{3}}}$(2x + 1) $ \geq$ 0 bzw. x $ \leq$ 1.
Analog ist ein Paar (x, y) mit y = $ {\frac{{2}}{{3}}}$(2x + 1) und x $ \leq$ 1 genau dann Lösung von Gleichung (1), wenn $ \sqrt{{x^2+y^2-2x-4y+5}}$ $ \leq$ 5 ist. Setzt man wieder y = $ {\frac{{2}}{{3}}}$(2x + 1) ein, so bedeutet dies

5 $\displaystyle \geq$ $\displaystyle \sqrt{{x^2+\frac{16}{9}x^2+\frac{16}{9}x+\frac{4}{9}-2x-\frac{16}{3}x-\frac{8}{3}+5}}$ = $\displaystyle {\frac{{5}}{{3}}}$$\displaystyle \sqrt{{(x-1)^2}}$.

Wegen x $ \leq$ 1 ist dies nun aber gleichbedeutend mit 5 $ \geq$ $ {\frac{{5}}{{3}}}$(1 - x) bzw. nach Umstellen x $ \geq$ - 2.
Wir haben also gezeigt, dass genau die Paare (x,$ {\frac{{2}}{{3}}}$(2x + 1)) mit -2 $ \leq$ x $ \leq$ 1 die Gleichung lösen.


Macht man übrigens die Probe durch Einsetzen, so erhält man auf der linken Seite den Ausdruck

    /3$\displaystyle \sqrt{{(5x+10)^2}}$ + 1/3$\displaystyle \sqrt{{(5x-5)^2}}$  
    = $\displaystyle \left\{\vphantom{ \begin{array}{ll@{\quad}l} 1/3 (-5x-10\ -5x+5) ... ...q x \leq 1,\\ 1/3 (+5x+10\ +5x-5) & = 10/3 x+5/3, & x>1\\ \end{array}}\right.$$\displaystyle \begin{array}{ll@{\quad}l} 1/3 (-5x-10\ -5x+5) & = -10/3 x-5/3, &... ...& -2 \leq x \leq 1,\\ 1/3 (+5x+10\ +5x-5) & = 10/3 x+5/3, & x>1\\ \end{array}$  

und ebenso die Lösung.


Zweite Lösung:


Eine elegante Variante zur Lösung erhalten wir mit geometrischen Überlegungen: Die gegebene Gleichung ist äquivalent zu

$\displaystyle \sqrt{{(x+2)^2+(y+2)^2}}$ + $\displaystyle \sqrt{{(x-1)^2+(y-2)^2}}$ = 5.

Die Punkte A = (- 2, - 2) und B = (1, 2) haben in einem kartesischen Koordinatensystem genau den Abstand 5 und für einen gegebenen Punkt C = (x, y) beschreibt die erste Wurzel genau den Abstand von C zu A und die zweite Wurzel den Abstand zu B . Somit ist die Gleichung äquivalent zu

| AC| + | BC| = | AB|.

Nach der Dreiecksungleichung gilt aber stets | AC| + | BC| $ \geq$ | AB| und Gleichheit gilt genau dann, wenn C auf der Strecke AB liegt. Beschreibt man die Punkte dieser Strecke in Koordinaten, so ergibt sich genau dieselbe Lösungsmenge wie in der ersten Lösung.


Fußnoten

...1
von David Wells (Fischer Taschenbuch, 1990)
... konvexe2
Eine Menge von Punkten in der Ebene heißt konvex, wenn sie für jedes Paar A, B von Punkten in M auch die gesamte Strecke AB zwischen diesen Punkten enthält. Die Menge enthält also keine Löcher oder Einbuchtungen.
drucken Zum Ausdrucken als pdf-File oder als ps-File