Beispiellösungen zu Aufgabenblatt 59

aktualisiert: 28. März 2007

drucken Zum Ausdrucken als pdf-File oder als ps-File
Aufgabe 1


\includegraphics[width=50mm]{deutschland_bunt7}

Nora muss im kooperativen Kunst- und Erdkundeunterricht die Karte der Bundesländer Deutschlands so färben, dass keine zwei benachbarten Länder gleich gefärbt sind. Im Atlas findet sie eine Version mit sechs Farben (siehe Abbildung oben). Weil das Auswaschen des Pinsels so lästig ist, möchte sie mit möglichst wenig Farben auskommen - wie viele Farben benötigt sie mindestens?

Johanna möchte so viele Länder wie möglich mit ihrer Lieblingsfarbe färben: Wie oft kann sie sie verwenden?


Lösung:


\includegraphics[width=50mm]{deutschland_bunt_invier}

Nora benötigt mindestens vier Farben.

Dass es nicht mit nur drei Farben geht, liegt quasi an Thüringen: Denn Thüringen liegt im Inneren von Deutschland und hat eine ungerade Anzahl an benachbarten Bundesländern. Nehmen wir also an, dass man zum Färben nur drei Farben bräuchte: Dann hat Thüringen eine Farbe A, Niedersachsen eine andere Farbe, B, und Sachsen-Anhalt eine weitere, C. Nun geht man im Kreis um Thüringen herum: Weil Sachsen-Anhalt mit C gefärbt ist, kann Sachsen nur Farbe B haben, entsprechend Bayern Farbe C. Hessen hat nun mit Bayern, Thüringen und Niedersachsen bereits alle drei Farben in den Nachbarländern, es ergibt sich daher ein Widerspruch.

Mit vier Farben hingegen ist eine Färbung problemlos möglich, ein Beispiel ist in der Abbildung dargestellt.


Bemerkung: Man kann diese Teilantwort auch rein theoretisch begründen: Wie viele von euch sicherlich schon gehört und teils auch geschrieben haben, gilt der berühmte VIERFARBENSATZ: Jede Landkarte (einer Ebene oder einer Kugel), deren Länder zusammenhängende Flächen darstellen, kann mit höchstens vier Farben gefärbt werden.

Und dass das Land Bremen da keine Probleme macht, ist offensichtlich.


Nun zur zweiten Frage: Wie man am Beispiel sieht, ist es mindestens möglich, acht Länder mit einer vorgegebenen Farbe zu versehen. Und dies ist auch die maximal mögliche Anzahl.

Beweisen kann man dies wie folgt: Wir teilen die Menge der Bundesländer in acht Teilmengen auf, bei denen sofort klar ist, dass in jeder Teilmenge höchstens ein Land mit Johannas Lieblingsfarbe gefärbt werden kann; denn jedes Land einer Teilmenge berührt jedes andere Land dieser Teilmenge:


1 Schleswig-Holstein (SH), Hamburg (HH)
2 Niedersachsen (NI), Bremen (HB)
3 Mecklenburg-Vorpommern (MV)
4 Berlin (BE), Brandenburg (BB)
5 Sachsen-Anhalt (ST), Sachsen (SN), Thüringen (TH)
6 Nordrhein-Westfalen (NW), Hessen (HE)
7 Rheinland-Pfalz (RP), Saarland (SL)
8 Baden-Württemberg (BW), Bayern (BY)


Da wir jedes Land in der Tabelle verwendet haben, ist klar, dass höchstens acht nach Johannas Wunsch gefärbt werden können. Damit ist der Beweis an sich schon fertig.


Zusätzliche Überlegungen

Bleibt zum Beispiel die Frage: Wie viele Möglichkeiten einer solchen Färbung gibt es? Wo hat man noch Freiheiten in der Gestaltung? Dazu machen wir eine neue Tabelle (die obere der beiden folgenden):


1 SH, HH, NI
2 HB, NI
3 MV, BB
4 BE, BB
5 ST, SN, TH
6 NW, HE, RP
7 RP, SL
8 BW, BY, HE
                
1 SH, HH
2 HB
3 MV
4 BE
5 ST, SN, TH
6 NW
7 SL
8 BW, BY


Wiederum kann in jeder Teilmenge nur ein Land lieblingsgefärbt werden. Außerdem wurde jedes Land mindestens einmal eingetragen, manche aber auch zweimal. Jetzt sei angenommen, ein Land, das in zwei Teilmengen enthalten ist, könne gefärbt werden. Dann ,,belegt`` es die beiden Zeilen in der Tabelle, kann insgesamt aber ja nur einmal gezählt werden - womit nur noch höchstens sieben Länder die Wunschfarbe erhalten können, ein Widerspruch. Damit fallen schon einmal NI, BB, RP und HE weg.

Die Teilmengen reduzieren sich somit auf die Mengen in der unteren der beiden Tabellen.


Andererseits müssen dann, um überhaupt noch acht Länder lieblingsfärben zu können, HB, MV, BE, NW und SL so gefärbt werden. Weil MV gefärbt wurde, fällt auch SH weg, so dass auch HH gefärbt werden muss.

Bemerkung: Man hätte alternativ auch Teilmenge 3 als MV, SH wählen können, dann wäre zuerst SH und dann BB weggefallen. Oder man hätte Teilmenge 3 auch als MV lassen können, dann wären SH und BB beide im zweiten Schritt ausgeschlossen worden.

Bleiben die Teilmengen 5 und 8. Hier kann man tatsächlich noch wählen: Nimmt man TH in Menge 5, so muss man BW nehmen; bei ST oder SN kann man bei Teilmenge 8 frei wählen. Es ergeben sich daher genau fünf Möglichkeiten, von denen die gezeigte den größten Flächenanteil aufweist.


Dass die vorige Betrachtung überhaupt eine Lösung liefert, liegt daran, dass die Teilmengen geschickt gewählt waren. Bei größeren Karten wird man das nicht so schnell sehen. Hier wird man zunächst heuristisch herangehen, indem man zuerst Länder färbt, die möglichst wenig Nachbarn haben, um sich nicht zu viel zu verbauen. In den allermeisten Fällen wird das zu einem ziemlich guten Ergebnis führen, in sehr vielen sicherlich auch zum Optimum.

Aber: An diesem Beispiel kann man gut klarmachen, worin der Unterschied zwischen einer Heuristik, das heißt einer Vorgehensweise, die der Erfahrung nach in den meisten Fällen das Gewünschte liefert, und einer erwiesenermaßen optimalen Strategie liegt.

Wohl jeder, der sich die Deutschlandkarte anschaut, wird intuitiv zuerst BE, SL und HB mit Johannas Farbe färben, vielleicht auch gleich HH. Das ist auch völlig ,,richtig``, denn es gilt folgende Aussage:

Satz. Hat ein Land nur ein Nachbarland oder zwei Nachbarländer, die sich gegenseitig berühren, so ist unter allen Färbungen mit der maximalen Zahl an Lieblingsfarben auch eine, bei der dieses Land gefärbt ist.

Das ist schnell einzusehen: Sollte in einer solchen Färbung eines der anderen beteiligten Länder gefärbt sein, so kann man die Färbung ohne Weiteres austauschen, da es mit Sicherheit keine Konflikte mit Nachbarländern gibt; dass gar keines der zwei oder drei Länder gefärbt wird, kann gar nicht vorkommen, denn dann könnte man das betroffene Land noch zusätzlich färben.


\includegraphics[width=40mm]{loes59_1a}

Hat man jedoch ein Land, das zwei Nachbarn hat, die sich nicht berühren, so gibt es bereits ein Beispiel, bei dem man dieses Land nicht färben darf, um die maximale Zahl zu erhalten - siehe Abbildung (mit dem Land links unten).




\includegraphics[width=40mm]{loes59_1b}

Und auch andersherum gibt es ein Beispiel, in dem ausgerechnet das Land gefärbt werden muss, das die meisten Nachbarn hat (das zentrale):


Man muss sich also immer überlegen, ob Naheliegendes auch wirklich richtig ist.


Bei allen diesen Betrachtungen haben wir aus den Augen verloren, ob man nach der Auswahl der Länder mit der Lieblingsfarbe die Karte insgesamt noch mit vier Farben färben kann - um ehrlich zu sein: Für Deutschland geht es, aber im allgemeinen Fall wissen es (noch) nicht, würden uns jedoch über Hinweise freuen.


Aufgabe 2


Ist die Zahl

$\displaystyle \sqrt{{1+\sqrt{2+\sqrt{3+\ldots+\sqrt{2006+\sqrt{2007}}}}}}$

kleiner oder größer als 2?


Lösung:


Da 462 = 2116 ist, gilt $ \sqrt{{2007}}$ < 46, $ \sqrt{{2006+\sqrt{2007}}}$ < $ \sqrt{{2006 +46}}$ < 46, $ \sqrt{{2005+\sqrt{2006+\sqrt{2007}}}}$ < $ \sqrt{{2005 +46}}$ < 46 usw. bis

$\displaystyle \sqrt{{4+\sqrt{5+\sqrt{6+\ldots+\sqrt{2006+\sqrt{2007}}}}}}$ < 46.

Daraus folgt dann aber

$\displaystyle \sqrt{{1+\sqrt{2+\sqrt{3+\ldots+\sqrt{2006+\sqrt{2007}}}}}}$ < $\displaystyle \sqrt{{1+\sqrt{2+\sqrt{3+46}}}}$ = 2.

Der Wurzelausdruck ist also kleiner als 2.


Bemerkung: Man kann sogar zeigen, dass allgemein die Folge

an = $\displaystyle \sqrt{{1+\sqrt{2+\sqrt{3+\ldots+\sqrt{n-1+\sqrt{n}}}}}}$

monoton wachsend (das ist sofort klar) und nach oben beschränkt durch 2 ist:

Wir nehmen hierzu an, dass an für irgendein n größer oder gleich 2 ist: Wiederholtes Quadrieren und Isolieren des verbleibenden Wurzelausdruckes liefern uns:

$\displaystyle \sqrt{{1+\sqrt{2+\sqrt{3+\ldots+\sqrt{n-1+\sqrt{n}}}}}}$ $\displaystyle \geq$ 2    
$\displaystyle \Rightarrow$ $\displaystyle \sqrt{{2+\sqrt{3+\ldots+\sqrt{n-1+\sqrt{n}}}}}$ $\displaystyle \geq$ 3    
$\displaystyle \Rightarrow$ $\displaystyle \sqrt{{3+\ldots+\sqrt{n-1+\sqrt{n}}}}$ $\displaystyle \geq$ 7   usw.    

Diesem Vorgehen entsprechend definieren wir eine Folge bk ganzer Zahlen durch b1 = 2 und bk+1 : = bk2 - k. Das k-te Folgeglied gibt also an, wie groß die k-te geschachtelte Wurzel mindestens sein muss, damit unsere Annahme zutrifft.

Nun zeigen wir durch vollständige Induktion, dass stets bk $ \geq$ k + 1 gilt:

Induktionsanfang: Es ist b1 = 2 $ \geq$ 1 + 1.

Induktionsannahme: Es gelte bk $ \geq$ k + 1 für ein bestimmtes k $ \geq$ 1.

Induktionsschluss: Wegen bk $ \geq$ k + 1 gilt nun für bk+1:

bk+1 = bk2 - k $\displaystyle \geq$ (k + 1)2 - k = k + 1 + k2 $\displaystyle \geq$ k + 2.

Allerdings ist bn = $ \sqrt{{n}}$ $ \leq$ n, was im Widerspruch zum gerade Gezeigten steht.

Die Annahme ist damit falsch und damit ist die Folge der an nach oben beschränkt durch 2.

Sie konvergiert also gegen einen Grenzwert, der irgendwo zwischen a1 = 1 und 2 liegt. Den genauen Wert1 kennen wir aber leider auch nicht ...


Aufgabe 3


\includegraphics[width=45mm]{moendchen2}

Das nebenstehende Bild zeigt ein Sehnenviereck, bei dem eine Seite ein Durchmesser seines Umkreises ist. Über den anderen drei Seiten wurden nach außen hin Halbkreise gezeichnet. Diese bilden zusammen mit den jeweiligen Abschnitten des Umkreises drei ,,Möndchen``. Ist die Fläche der drei Möndchen zusammen dann größer, kleiner oder gleich der Fläche des Sehnenvierecks?


Lösung:


\includegraphics[width=55mm]{moendchen_loes1}

Die gesamte, vom Durchmesser d und den drei Halbkreisbögen über a, b und c eingeschlossene Fläche setzt sich einmal zusammen aus der Fläche F des Sehnenvierecks und den drei Halbkreisflächen, andererseits ist sie auch gleich der Summe der Flächen der drei Möndchen Fa, Fb und Fc und der (großen) Halbkreisfläche über d. Es gilt also:

F + $\displaystyle {\frac{{1}}{{8}}}$$\displaystyle \pi$a2 + $\displaystyle {\frac{{1}}{{8}}}$$\displaystyle \pi$b2 + $\displaystyle {\frac{{1}}{{8}}}$$\displaystyle \pi$c2 = Fa + Fb + Fc + $\displaystyle {\frac{{1}}{{8}}}$$\displaystyle \pi$d2

bzw.

F - (Fa + Fb + Fc) = $\displaystyle {\frac{{1}}{{8}}}$$\displaystyle \pi$$\displaystyle \left(\vphantom{d^2-\left(a^2+b^2+c^2\right)}\right.$d2 - $\displaystyle \left(\vphantom{a^2+b^2+c^2}\right.$a2 + b2 + c2$\displaystyle \left.\vphantom{a^2+b^2+c^2}\right)$$\displaystyle \left.\vphantom{d^2-\left(a^2+b^2+c^2\right)}\right)$.

Nach Satz des Thales ist das Dreieck ADC rechtwinklig. Es gilt demnach

e2 + c2 = d2.

Da auch das Dreieck ADB nach Satz des Thales rechtwinklig ist, ist das Dreieck ACB stumpfwinklig mit stumpfem Winkel bei B. Deswegen2 gilt

a2 + b2 < e2.

Addiert man hierzu die letzte Gleichung, so folgt a2 + b2 + c2 < d2. Das bedeutet aber, dass

F > Fa + Fb + Fc

ist; die drei Möndchen sind also zusammen stets kleiner als das Sehnenviereck.


In den entarteten Fällen, dass zwei der Punkte A, B, C und D zusammenfallen, würde übrigens Gleichheit gelten. Die dabei entstehende Figur ist unter dem Namen ,,Möndchen des Hippokrates`` bekannt.


Aufgabe 4


Finde eine positive reelle Zahl a so, dass $ \lfloor$a$ \rfloor$, $ \lfloor$2 . a$ \rfloor$, $ \lfloor$4 . a$ \rfloor$, $ \lfloor$8 . a$ \rfloor$, $ \lfloor$16 . a$ \rfloor$ und $ \lfloor$32 . a$ \rfloor$ alles Primzahlen sind.

Gibt es eine positive reelle Zahl a so, dass $ \left\lfloor\vphantom{ 2^n\cdot a }\right.$2n . a$ \left.\vphantom{ 2^n\cdot a }\right\rfloor$ für alle n $ \geq$ 0 eine Primzahl ist?

Hinweis: Hierbei ist $ \lfloor$x$ \rfloor$ die größte ganze Zahl kleiner oder gleich x.


Lösung:


Setzt man a = 89, 99, dann gilt

$\displaystyle \left\lfloor\vphantom{ a }\right.$a$\displaystyle \left.\vphantom{ a }\right\rfloor$ = 89    
$\displaystyle \left\lfloor\vphantom{2\cdot a }\right.$2 . a$\displaystyle \left.\vphantom{2\cdot a }\right\rfloor$ = 179    
$\displaystyle \left\lfloor\vphantom{4\cdot a }\right.$4 . a$\displaystyle \left.\vphantom{4\cdot a }\right\rfloor$ = 359    
$\displaystyle \left\lfloor\vphantom{8\cdot a }\right.$8 . a$\displaystyle \left.\vphantom{8\cdot a }\right\rfloor$ = 719    
$\displaystyle \left\lfloor\vphantom{16\cdot a }\right.$16 . a$\displaystyle \left.\vphantom{16\cdot a }\right\rfloor$ = 1439    
$\displaystyle \left\lfloor\vphantom{32\cdot a }\right.$32 . a$\displaystyle \left.\vphantom{32\cdot a }\right\rfloor$ = 2879.    

Da dies alles Primzahlen sind, ist a = 89, 99 ein Beispiel für eine im ersten Aufgabenteil gesuchte Zahl.


Wie kommt man auf die 89 als Startzahl?

Anfangs muss man etwas probieren; als Erstes stellt man fest, dass entweder

$\displaystyle \left\lfloor\vphantom{2^{k+1}\cdot a }\right.$2k+1 . a$\displaystyle \left.\vphantom{2^{k+1}\cdot a }\right\rfloor$ = 2 . $\displaystyle \left\lfloor\vphantom{2^k\cdot a }\right.$2k . a$\displaystyle \left.\vphantom{2^k\cdot a }\right\rfloor$    oder    $\displaystyle \left\lfloor\vphantom{2^{k+1}\cdot a }\right.$2k+1 . a$\displaystyle \left.\vphantom{2^{k+1}\cdot a }\right\rfloor$ = 2 . $\displaystyle \left\lfloor\vphantom{2^k\cdot a }\right.$2k . a$\displaystyle \left.\vphantom{2^k\cdot a }\right\rfloor$ + 1

gilt. Im ersten Fall ist die Zahl jedoch gerade, daher muss immer der zweite Fall eintreten.

Dann erkennt man vielleicht, dass jede Zahl, die durch 3 teilbar ist, nach zwei Schritten wieder eine durch drei teilbare Zahl liefert, die dann also keinesfalls eine Primzahl ist. Ebenso liefert jede Zahl, die bei Division durch 3 den Rest 1 lässt, im nächsten Schritt eine durch 3 teilbare Zahl. Also braucht man nur Zahlen zu betrachten, die bei Division durch 3 den Rest 2 lassen.

Auf analoge Art stellt man fest, dass man sich auf Zahlen beschränken kann, die bei Division durch 5 den Rest 4 lassen. Außerdem müssen alle Startzahlen ungerade sein (2 als Startzahl geht auch nicht). Damit bleiben nur noch 29, 59, 89, 119, ... als Kandidaten übrig. Und auch 29 und 59 fallen nach zwei bzw. einem Schritt weg, weil die Zahlen dann durch 7 teilbar sind.


Zum zweiten Teil der Aufgabe: Es gibt keine Zahl a so, dass $ \left\lfloor\vphantom{ 2^n\cdot a }\right.$2n . a$ \left.\vphantom{ 2^n\cdot a }\right\rfloor$ für alle n eine Primzahl ist. Um das einzusehen, betrachten wir die Binärdarstellung eines solchen a, wenn es denn existiert:

a = $\displaystyle \sum_{{k=-\infty}}^{m}$ak2k = $\displaystyle \left(\vphantom{a_ma_{m-1}\ldots a_1a_0,a_{-1}a_{-2}\ldots}\right.$amam-1...a1a0, a-1a-2...$\displaystyle \left.\vphantom{a_ma_{m-1}\ldots a_1a_0,a_{-1}a_{-2}\ldots}\right)_{2}^{}$,

wobei die ai alle entweder gleich 1 oder gleich 0 sind. Dann ist

$\displaystyle \left\lfloor\vphantom{ 2^n\cdot a }\right.$2n . a$\displaystyle \left.\vphantom{ 2^n\cdot a }\right\rfloor$ = $\displaystyle \left\lfloor\vphantom{ \left(a_ma_{m-1}\ldots a_{1-n}a_{-n},a_{-(n+1)}a_{-(n+2)}\ldots\right)_2}\right.$$\displaystyle \left(\vphantom{a_ma_{m-1}\ldots a_{1-n}a_{-n},a_{-(n+1)}a_{-(n+2)}\ldots}\right.$amam-1...a1-na-n, a-(n+1)a-(n+2)...$\displaystyle \left.\vphantom{a_ma_{m-1}\ldots a_{1-n}a_{-n},a_{-(n+1)}a_{-(n+2)}\ldots}\right)_{2}^{}$$\displaystyle \left.\vphantom{ \left(a_ma_{m-1}\ldots a_{1-n}a_{-n},a_{-(n+1)}a_{-(n+2)}\ldots\right)_2}\right\rfloor$    
  = $\displaystyle \left(\vphantom{a_ma_{m-1}\ldots a_{1-n}a_{-n}}\right.$amam-1...a1-na-n$\displaystyle \left.\vphantom{a_ma_{m-1}\ldots a_{1-n}a_{-n}}\right)_{2}^{}$.    

Dies kann nun aber nur eine Primzahl sein, wenn a-n = 1 ist, denn ansonsten wäre die Zahl ja gerade. Wenn nun für das gegebene a für alle n die Zahl $ \left\lfloor\vphantom{ 2^n\cdot a }\right.$2n . a$ \left.\vphantom{ 2^n\cdot a }\right\rfloor$ prim ist, dann ist also a-n = 1 für alle n $ \geq$ 1. Das bedeutet dann aber

a = $\displaystyle \left(\vphantom{a_ma_{m-1}\ldots a_1a_0,1111\ldots}\right.$amam-1...a1a0, 1111...$\displaystyle \left.\vphantom{a_ma_{m-1}\ldots a_1a_0,1111\ldots}\right)_{2}^{}$ = $\displaystyle \left(\vphantom{a_ma_{m-1}\ldots a_1a_0}\right.$amam-1...a1a0$\displaystyle \left.\vphantom{a_ma_{m-1}\ldots a_1a_0}\right)_{2}^{}$ + 1,

denn $ {\frac{{1}}{{2}}}$ + $ {\frac{{1}}{{4}}}$ + $ {\frac{{1}}{{8}}}$ +...= 1. Somit ist a aber eine ganze Zahl, was nicht sein kann, denn dann wäre schon $ \left\lfloor\vphantom{ 4\cdot a }\right.$4 . a$ \left.\vphantom{ 4\cdot a }\right\rfloor$ = 4 . a nicht prim.

Es kann demnach kein solches a geben.


Fußnoten

... Wert1
Mit einem genauen Wert meinen wir einen exakten Ausdruck wie $ {\frac{{3}}{{2}}}$ oder $ \sqrt{{3}}$ oder auch ln 2 . $ {\frac{{\pi}}{{e}}}$. Es ist natürlich einfach, die ersten Nachkommastellen des Dezimalbruchs zu berechnen: 1,75793...
... Deswegen2
Dies folgt entweder mathematisch exakt aus dem Kosinus-Satz e2 = a2 + b2 - 2ab cos($ \angle$ABC) > a2 + b2, oder aber einfach durch den anschaulichen Vergleich mit einem rechtwinkligen Dreieck mit den Katheten a und b, in dem die Hypothenuse dann kleiner als e sein muss. Oder man konstruiert einen exakten Vergleich: Dazu verlängere man die Höhe über der Grundseite e, bis man ein rechtwinkliges Dreieck erhält. Dessen Katheten sind dann länger als a und b.
drucken Zum Ausdrucken als pdf-File oder als ps-File