Beispiellösungen zu Aufgabenblatt 11

aktualisiert: 13. Juli 2001

Aufgabe 1

In dem folgenden Diagramm steht jeder Buchstabe für eine der Ziffern 0, 1,..., 9, wobei verschiedene Buchstaben auch verschiedene Ziffern bezeichnen. Finde alle möglichen Lösungen, für die sämtliche Gleichungen erfüllt sind!

Lösung:

Zur Lösung der Aufgabe konzentrieren wir uns zunächst ganz auf die Buchstaben N, A, B und E. Aus den Einerstellen der ersten Spalte ( NENA : EN = RAN) ergibt sich, dass A die Einerstelle von N^.N ist. Ebenso ergibt sich aus der dritten Zeile, dass B die Einerstelle von N^.A ist. Mit der Wahl von N sind also B und A festgelegt, dafür fertigen wir uns eine Tabelle an:

N	0	1	2	3	4	5	6	7	8	9
A	0	1	4	9	6	5	6	9	4	1
B	0	1	8	7	4	5	6	3	2	9
	-	-	+	+	-	-	-	+	+	-

Verschiedene Buchstaben stehen für verschiedene Ziffern, deshalb scheiden alle mit ,,-`` gekennzeichnete Spalten aus.
Als Nächstes betrachten wir die zweite Zeile. Dort wird die zweistellige Zahl EN zu BASE hinzuaddiert, dabei kann sich die Hunderterstelle höchstens um eins erhöhen. Also ist E = A + 1 . Wir können somit unsere Tabelle noch um eine Zeile erweitern, wobei wir jetzt nur die oben noch nicht ausgeschlossenen Spalten berücksichtigen:

N	2	3	7	8
A	4	9	9	4
B	8	7	3	2
E	5	0	0	5
	+	-	-	+

E darf nicht 0 sein, z.B. wegen der Einerstelle in der ersten Zeile, deshalb sind die beiden mit Minus gekennzeichneten Spalten nicht möglich. Somit ist E = 5 und A = 4.
Schließlich betrachten wir noch die Tausenderstellen in der ersten Zeile und der letzten Spalte des Kryptogramms. Wegen der letzten Spalte ist O größer als B und T und damit mindestens 2. Aus dem gleichen Grund ist wegen der ersten Zeile N größer als O, also ist N $\ge$ 3. Damit scheidet auch die erste Spalte der Tabelle aus. Übrig bleiben damit N = 8 und B = 2.
Den Rest kann man leicht vervollständigen, indem man die schon bestimmten Buchstaben durch die entsprechenden Zahlen ersetzt und die sich dadurch ergebenden Operationen ausführt. Es ergibt sich als einzige Lösung:

8	5	8	4	-	2	4	9	9	=	6	0	8	5
:					-					-
		5	8	+	2	4	7	5	=	2	5	3	3
=					=					=
	1	4	8	*			2	4	=	3	5	5	2

Die abschließende Probe zeigt, dass auch wirklich alle sechs Gleichungen des Kryptogramms erfüllt sind. (Die Probe ist wichtig, denn wenn z.B. aus einer Gleichung N = 8 folgt, heißt das ja noch nicht, dass dies nicht in einer anderen Gleichung zu einem Widerspruch führt, deshalb muss man am Ende überprüfen, ob auch wirklich alle Gleichungen wahre Aussagen sind.)

Aufgabe 2

Fahrradkurier Rudi Hurtig ist wieder in Neu Weende unterwegs. (Der hier wesentliche Stadtplanausschnitt ist unten abgebildet.) Er muss ein Dokument von A nach B bringen und möchte dies selbstverständlich auf dem kürzestmöglichen Weg erledigen. Wie viele Möglichkeiten hat er dafür? Und wie lang ist dieser Weg dann?

$\includegraphics[width=12cm]{neuweende.eps}$

Anmerkung: Die Wege in Neu Weende sind nicht allzu breit (es fahren keine Autos), so dass man sie getrost als Striche zeichnen und auch so rechnen darf. Die Gitterbreite des Quadratgitters, auf dem die Wege angelegt wurden, beträgt 60m. Die Abbiegekurven zum angenehmeren Abbiegen haben sämtlich einen Radius von 20m.

Lösung:

Der Zielpunkt B liegt nordöstlich von A, und zwar 3^.60m = 180m (3 Rastereinheiten) nördlich und 7^.60m = 420m (7 Rastereinheiten) östlich von A. In der Summe von Ost- und Nord-Richtung muss Rudi also 600m zurücklegen. Es ist an sich klar, dass es für Rudi nur Sinn macht, sich im Raster der Stadt in nördlicher oder in östlicher Richtung zu bewegen. (Am Ende wird das noch einmal kritisch untersucht.)
Grundsätzlich gibt es für einen beliebigen Abschnitt von Rudis Fahrtstrecke zwei Möglichkeiten:

Entweder befindet er sich auf einem geraden Abschnitt in Nord- oder Ost-Richtung. Dann legt er pro gefahrenen Meter auch genau einen Meter in der Summe von Ost- und Nord-Richtung zurück.
Oder er befährt eine der Abbiegekurven, die ihn zwischen diesen Richtungen wechseln lässt. Diese haben eine Länge von ${\frac{1}{4}}$ (2 $\pi$ ^.20 m) $\approx$ 31, 416m, und er legt dabei je 20m in Nord- und in Ost-Richtung zurück, in der Summe der beiden Richtungen also 40m und demnach mehr, als er gefahren ist.

Er sollte daher so viele Kurven wie möglich befahren.
Nun liegt an jeder Kurve, die Rudi sinnvoll befahren kann, im Raster der Stadt ein gerader Abschnitt in nördlicher Richtung und einer in östlicher Richtung. Da er drei Rasterabschnitte nach Norden fahren muss, kann er also maximal sechs Kurven befahren, denn an jeden Abschnitt stoßen ja höchstens zwei Kurven.

Der Stadtsee bildet im Verkehrsnetz ein natürliches Hindernis. Fährt Rudi südlich daran vorbei, so muss er vorher zwei Kurven befahren haben (wofür es zwei Möglichkeiten gibt) und hat danach, wie man leicht durch Probieren feststellen kann, drei Möglichkeiten, um mit vier weiteren Kurven zum Ziel zu kommen. Die verschiedenen Verzweigungen sind in der Skizze unten verzeichnet, deren Darstellungsweise der Lösung von Julia Brandes entnommen wurde. Auf der südlichen Route hat Rudi also 2^.3 = 6 Varianten.

Wenn Rudi nördlich am See vorbeifahren will, kann er danach nur noch geradeaus fahren. Davor kann er aber maximal vier Kurven genutzt haben, also ist dieser Weg grundsätzlich länger.

$\includegraphics[width=12cm]{loesneuweende.eps}$

Er hat also 6 Möglichkeiten für einen kürzestmöglichen Weg, und diese haben eine Länge von ca. 600 m - 6^.40 m + 6^.31, 416 m $\approx$ 548, 5 m.

Um deutlich zu machen, dass es sich lohnt, sich noch einmal Gedanken über die grundsätzlichen Fahrtmöglichkeiten von Rudi zu machen, sei ein anderes Straßennetz gezeigt:

$\includegraphics[width=12cm]{komischestadt.eps}$

Hier existiert zwar ein Weg, der der kürzeste wäre, wenn die Ecken im Straßengitter nicht abgerundet wären (über C Länge: 1062,8m). Aber wegen der vielen Kurven ist der Weg über D (1045,5m) tatsächlich kürzer, auch wenn er im nicht-abgerundeten Fall offensichtlich länger als der andere wäre.

Man muss also Folgendes betrachten:

Wenn Rudi eine der Kurven, die für ihn eigentlich günstig wären, in der Gegenrichtung befährt, verliert er 40m in der Entfernungssumme, obwohl sich seine Fahrtstrecke um weitere 31,416m verlängert.
Auf den übrigen Kurven gewinnt er in der einen Richtung zwar 20m, verliert diese aber dafür in der anderen Richtung.
Fährt er auf einem geraden Abschnitt in südlicher oder westlicher Richtung, verliert er pro gefahrenem Meter in der Summe von Ost- oder Westrichtung genau einen Meter.

Alle diese Möglichkeiten sind also ungünstiger als die oben angeführten. Aber es kann unter Umständen sein (wie oben), dass solche ,, schlechten`` Abschnitte durch viele Nord-Ost-Kurven wieder ausgeglichen werden.
In Neu Weende ist nun die Situation auf die Art ,,angenehm``, dass es Wege gibt, die sowohl auf dem Quadratgitter minimal kurz wären als auch die (auf dem vollständigen Gitter) maximal mögliche Zahl von Abbiegevorgängen enthalten (hier also sechs, dadurch gegeben, dass Rudi nur drei Rasterabschnitte nach Norden fahren muss). Wenn er hier mehr Kurven in nordöstlicher Richtung fahren wollte, so müsste er nach den obigen Überlegungen also noch einen Abschnitt mehr in nördlicher Richtung fahren. Dafür muss er dann aber irgendwann einmal zum Ausgleich einen Abschnitt nach Süden fahren und braucht dafür natürlich auch noch zwei Kurven, um dorthin ein- und wieder auszuschwenken. Das ergibt also zumindest vier Kurven, die zu fahren sind, um noch maximal zwei Kurven mit dem besten Entfernungsgewinn-zu-Streckenlängen-Verhältnis zu benutzen. Diese bedeuten einen Fahrweg von 125,7m, Rudi gewinnt dabei aber maximal 80m Entfernung (in östlicher Richtung). Also macht es in Neu Weende keinen Sinn, mehr als sechs Kurven zu benutzen.

Aufgabe 3

Yvonne und Zacharias spielen ein Hölzchenspiel.
a) Sie haben einen Haufen mit 100 Hölzchen und ziehen abwechselnd mindestens ein und höchstens sieben Hölzchen, wobei Yvonne beginnt (Ladies first). Verloren hat, wer das letzte Hölzchen ziehen muss.
Wer von den beiden kann den Sieg erzwingen?

b) Jetzt spielen sie mit zwei Haufen à 100 Hölzchen, wobei ein Spieler wieder ein bis sieben Hölzchen von einem der zwei Haufen zieht. Wieder darf Yvonne anfangen und wieder verliert derjenige, der das letzte Hölzchen ziehen muss.
Wer kann diesmal den Sieg erzwingen?

Lösung:

a) Yvonne kann den Gewinn erzwingen.

Wir betrachten zuerst Spielvarianten mit weniger Hölzchen. Bei einem Hölzchen verliert natürlich der Spieler, der am Zug ist (d.h. der anziehende Spieler), weil er das Hölzchen wegnehmen muss. Bei zwei bis acht Hölzchen gewinnt der anziehende Spieler, da er gerade so viel wegnehmen kann, dass noch ein Hölzchen übrig bleibt, das dann der andere wegnehmen muss. Bei neun Hölzchen verliert dagegen der Anziehende wieder. Er kann ja nur ein bis sieben Hölzchen wegnehmen und dann entsteht die Situation mit zwei bis acht Hölzchen, die wir gerade hatten, nur dass diesmal der andere in dieser Situation beginnt. Man sieht hier schon, dass man die Situation rekursiv bewerten kann, und zwar folgendermaßen: Bei n Hölzchen verliert der Anziehende (im Folgenden Verluststellung genannt), wenn er nur Situationen herstellen kann, in denen der Anziehende (der ja dann der andere ist) gewinnt. Andererseits gewinnt der Anziehende (so genannte Gewinnstellung), wenn man die Möglichkeit hat, in eine Verluststellung zu ziehen. Die folgende Tabelle zeigt die Bewertungen für ein bis 26 Hölzchen. (G bedeutet Gewinnstellung, V bedeutet Verluststellung.)

Hölzchen	1	2	3	4	5	6	7	8	9	10	11	12	13
Stellung	V	G	G	G	G	G	G	G	V	G	G	G	G

Hölzchen	14	15	16	17	18	19	20	21	22	23	24	25	26
Stellung	G	G	G	V	G	G	G	G	G	G	G	V	G

Wir haben also immer eine Verluststellung und dann sieben Gewinnstellungen, dann wieder eine Verluststellung und so weiter. Also haben wir genau dann eine Verluststellung, wenn die Anzahl der Hölzchen geteilt durch 8 den Rest 1 lässt.
Daraus können wir dann folgern, dass bei 100 Hölzchen (die in der Aufgabe vorgegeben sind) Yvonne gewinnt, da 100 : 8 = 12 Rest 4, und zwar nimmt sie am Anfang 3 Hölzchen und dann immer 8 minus die Anzahl der Hölzchen, die Zacharias genommen hat.

b) Hier kann Zacharias den Gewinn erzwingen.

Wir finden eine Gewinnstrategie ähnlich wie in Teil a). Es wird nur ein bisschen schwieriger, weil wir jetzt zwei Haufen haben. Wenn ein Haufen kein Hölzchen enthält, haben wir die Situationen von Teil a), bei denen wir schon wissen, ob es Gewinn- oder Verluststellungen sind. Nach den gleichen Überlegungen wie in Teil a) (Verluststellung, wenn man nur in Gewinnstellungen ziehen kann, und Gewinnstellung, wenn man die Möglichkeit hat, in eine Verluststellung zu ziehen) erhalten wir unten stehende Tabelle, wobei die Zahlen in der ersten Zeile für die Anzahl der Hölzchen des einen Haufens und die Zahlen in der ersten Spalte für die Anzahl der Hölzchen im anderen Haufen stehen:

Man muss hier natürlich beachten, dass man bis zu 7 Hölzchen vom einen oder vom anderen Haufen ziehen kann, d.h. wir setzen ein V an eine Stelle, wenn sowohl an den sieben Stellen darüber als auch an den sieben Stellen links davon nur G's stehen, und falls an einer dieser Stellen ein V steht, setzen wir ein G. Wieder kann man erkennen, dass sich die Verlust- und Gewinnstellungen in Achterschritten wiederholen, und zwar sowohl nach rechts als auch nach unten.

Als Ergebnis erhält man, dass man sich in einer Verluststellung befindet, wenn die Reste der Hölzchenanzahl der Haufen beim Teilen durch 8 gleich sind und eine der Zahlen 2, 3,..., 7 oder wenn der eine Rest gleich 0 und der andere gleich 1 ist.
In der Aufgabe haben beide Haufen die Größe 100 = 8^.12 + 4, d.h. beide Anzahlen geben beim Teilen durch 8 den Rest 4. Wir haben somit eine Verluststellung. Da Yvonne anfängt, kann Zacharias den Gewinn erzwingen. Hier gibt es mehrere Spielstrategien für Zacharias. Eine wäre nach unserer Überlegung folgende: Solange Yvonne von einem Haufen zieht, der mehr als 8 Hölzchen enthält, zieht Zacharias vom gleichen Haufen gerade 8 minus die Anzahl der von Yvonne gezogenen Hölzchen. Auf diese Weise tritt irgendwann die Situation ein, dass ein Haufen 4 Hölzchen und der andere 4 + 8k Hölzchen enthält (wir hatten ja zu Anfang je 100 = 4 + 8^.12 Hölzchen).
Zieht Yvonne von dem 4er-Haufen nun 1 oder 2 Hölzchen, so zieht Zacharias 1 bzw. 2 Hölzchen von dem anderen Haufen und sie gelangen in eine Situation wie (3, 11) bzw. (2, 10). Zieht Yvonne von dem 4er-Haufen aber 3 oder 4 Hölzchen, so zieht Zacharias von dem anderen Haufen 4 bzw. 3 Hölzchen, so dass sie in eine Situation wie (1, 8) bzw. (0, 9) gelangen. Zieht Yvonne von dem größeren Haufen (mit mehr als acht Hölzchen), so zieht Zacharias auch wieder vom gleichen Haufen den Rest zu 8 Hölzchen. Usw.

Bemerkung: Es ist nicht der richtige Weg, seine Gewinnstrategie auf Grund von Annahmen über die Spielstrategie seines Gegners zu machen. Die Gewinnstrategie muss so sein, dass der Gegner bei jeglicher Spielweise verliert.

Aufgabe 4

Nachtwächter Paul Sorglos soll im Museum für Moderne Kunst den Raum mit den wertvollsten Bildern beaufsichtigen. Der Raum hat nur gerade Wände, ist aber von einem dieser ,,modernen Architekten`` entworfen und hat somit sehr viele Ecken und ist sehr verwinkelt. Paul Sorglos sitzt nun jeden Abend auf einem Stuhl und beobachtet von dort aus, was rundherum passiert.

Obwohl Paul in einer der Nächte nicht eine Sekunde unaufmerksam war, fehlen am nächsten Morgen Bilder, und zwar von jeder Wand des Raumes eines.

Ihm wird vorgeworfen, dass er die Diebe gesehen und daher mit ihnen zusammengearbeitet haben muss. Aber Paul betont, dass er von seinem Sitzplatz aus die nun fehlenden Bilder gar nicht sehen konnte. Die folgenden Untersuchungen ergeben, dass Pauls Aussage tatsächlich stimmt.

Zeichne einen Grundriss eines Raumes, bei dem dies möglich ist, und markiere einen möglichen Sitzplatz.

Lösung:

Es gibt viele Möglichkeiten, wie der Raum aussehen könnte und an welcher Stelle Paul Sorglos sitzt. Eine Möglichkeit ist in der Abbildung dargestellt.

$\includegraphics[width=\textwidth]{raum.eps}$

Ein möglicher Raum

An jeder Wand dieses Raumes ist die Position eines Bildes angedeutet, die Paul von seinem Sitzplatz im Zentrum des Raumes nicht einsehen kann.
Damit ist die Aufgabe gelöst. Es gibt aber eine Reihe interessanter Fragestellungen, die sich anschließen könnten:

Man sieht schnell, dass die abgebildete Variante mit zwölf Wänden (also zwölf entwendeten Bildern) nicht der Raum mit der kleinsten Anzahl an Wänden ist, den man sich denken kann - zum Beispiel kann man in obigem Bild in den vier ,,kleinen Seitenräumen`` die ,,kleinen`` Außenwände immer kleiner machen, bis die Seitenräume nur noch Spitzen sind. Der resultierende Raum hat dann nur noch acht Wände. Geht man von einer gleichseitig dreieckigen Grundform des Raumes aus, so kann man eine ähnliche Konstruktion machen und der entstehende Raum hat nur noch sechs Wände.
Kann man einen solchen Raum mit weniger als sechs Wänden finden?
Kann man den Raum so bauen, dass zusätzlich folgende Aussage gilt:
Es gibt innerhalb des Raumes einen Weg, auf dem die Diebe ihre Beute einsammeln konnten, ohne dass Paul Sorglos sie bemerken konnte.
Wieviele Wände muss ein solcher Raum dann mindestens haben?
In einer fernen Zukunft ,,schweben`` die Besucher durch die beliebig verwinkelten dreidimensionalen Räume, das heißt, es gibt in diesen Museen keine Decke und keinen Boden mehr - an jeder Innenfläche der räumlichen Gebilde hängen Bilder.
Ist es möglich, dass ein Enkel von Paul Sorglos dasselbe Unheil wie sein Opa erlebt? Oder: Gibt es einen Polyeder (also einen Vielflächner im Raum), in dessen Innerem es einen Punkt gibt, von dem aus man keine der Seitenflächen vollständig sieht? Und wieviele Flächen muss solch ein Polyeder dann mindestens haben?

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