Die Kunst, einen Drachen zu enthaupten

Mathematische Knobelei: Die Kunst, einen Drachen zu enthaupten

So manche Schülerin und so mancher Schüler träumt während der Mathestunden von einem Job, in dem sie oder er nie wieder mit Zahlen und Rechenaufgaben zu tun haben. Burgfräulein oder Ritter – das wäre etwas Feines, denken sie sich. Wir wissen ja nicht, wie es mit den Burgfräuleins aussieht. Einen Ritter können mangelnde mathematische Kenntnisse jedenfalls in arge Bedrängnis bringen.

Da gibt es nämlich die gefürchteten Drachen mit mehreren Köpfen und Schwänzen. Ein erfahrener Ritter vermag mit einem einzigen Schlag ein oder zwei Köpfe zugleich vom geschuppten Rumpf zu trennen. Doch was ein rechter Drache ist, der verfügt über Zauberkräfte: Wird ihm nur ein Kopf abgehauen, wächst stattdessen sogleich ein neuer. Nur wenn mit einem Schlag zwei Häupter zu Boden fallen, sprießt keines nach. Noch komplizierter wird es bei den Schwänzen: Für einen abgetrennten Schwanz kommen zwei neue nach, werden zwei Schwänze zugleich abgeschlagen, wächst dafür ein Kopf. Um mehr als zwei Köpfe oder Schwänze zugleich vom Drachen zu lösen, ermangelt es selbst Spitzenrittern an Kraft. Als Ausgleich gibt es keine Fehlschläge, jeder Hieb führt unausweichlich zur Amputation. Erfahrungsgemäß dauern Kämpfe so lange, bis der Ritter dem Drachen alle Köpfe und Schwänze abgeschlagen hat oder selbst erschöpft verspeist wurde.

Ein Ritter tut also gut daran, sich eine optimale Strategie zu überlegen, bevor er in die Schlacht geht. Vor allem drei Fragen sollte er beantworten können:

Wieviele Hiebe muß ein Ritter wenigstens austeilen, um den tyischen Anfängerdrachen mit drei Köpfen und drei Schwänzen zu besiegen?
Gibt es unbesiegbare Drachen, von denen ein Ritter lieber die Finger lassen sollte? Welche?
Wieviel Schläge sind mindestens vonnöten, um einen Drachen mit n Köpfen und m Schwänzen zu besiegen?

Es sind neun Hiebe nötig, um einen Drachen mit drei Köpfen und drei Schwänzen zu besiegen. Werden die Köpfe mit K und die Schweife mit S bezeichnet, so könnte der Ritter die in Klammern angegebenen Schläge ausführen:
KKKSSS (-KK)
KSSS (-S)
KSSSS (-S)
KSSSSS (-S)
KSSSSSS (-SS)
KKSSSS (-SS)
KKKSS (-SS)
KKKK (-KK)
KK (-KK)
toter Drache

Das Problem wird für den Ritter unlösbar, wenn er sich einem Drachen mit einer ungeraden Anzahl von Köpfen und keinem einzigen Schwanz gegenübersieht. Solche Feuerspeier sind unbesiegbar.

Die allgemeine Lösung des Problems für Drachen mit n Köpfen und m Schwänzen:
Offensichtlich nützt es nichts, einen einzelnen Köpf abzutrennen, weil sofort ein neuer nachwächst. Darum sei x die Anzahl der Schläge, mit denen ein Schwanz abgeschlagen wird, und y die Anzahl der Hiebe gegen zwei Schwänze. Mit z wird die Anzahl der Doppelenthauptungen bezeichnet.
Da für je zwei abgeschlagene Schwänze ein neuer Kopf entsteht, hat der Drache im Verlaufe des Kampfes n+y Köpfe. Diese werden stets in Paaren amputiert, womit gilt: 2*z=n+y.
Der Drache verfügt über die anfangs vorhandenen Schwänze und jene, die neu entstanden sind: m+2*x. Abgeschlagen werden sie entweder einzeln oder zu zweit: x+2*y. Damit zum Schluß keiner mehr übrig ist, müssen beide Terme gleich groß sein: x+2*y=m+2*x.
Die Anzahl der Hiebe überhaupt, soll C heißen: C=x+y+z. Werden x und y durch Funktionen von z ersetzt (x=4*z-2*n-m und y=2*z-n), errechnet sich C nach: C=7*z-3*n-m.
Da x und y nur positiv oder Null sein können, gilt für z einschränkend: z >= (2*n+m)/4. Das führt im Minimum zu: C=7*[(2*n+m)/4]-3*n-m.
Diese Formel berücksichtigt allerdings nicht, ob m von Null verschieden ist oder m gerade ist für den Fall, daß n gleich Null ist (der unbesiegbare Drache). Die Strategie muß darum erweitert werden:
a) Man hacke so viele Kopfpaare ab, daß der Drache nur noch einen oder keinen Kopf mehr besitzt.
b) Man trenne reichlich Schwänze ab, bis bei einem Drachen ohne Kopf noch 4*k bzw. bei einem einköpfigen Drachen noch 4*k+2 Schwänze übrig sind.
c) Man wandle mit dem Schwert die Schwänze paarweise in Köpfe um und haue anschließend jeweils zwei Köpfe zugleich ab.
Bleibt noch zu beweisen, daß diese Vorgehensweise wirklich die minimale Anzahl von Hieben nutzt. Dabei sind acht Fälle zu berücksichtigen, je nachdem, wie sich n gegen den Rest der Division von m durch 4 verhält. Hier sei nur das Beispiel des dreiköpfigen und -schwänzigen Drachens noch einmal durchgespielt. Er gehört zu einer Klasse, deren Köpfe und Schwänze mit (2*k+1 , 4*l+3) dargestellt werden kann. k ist in diesem Falle 1 und l ist 0. In runden Klammern steht links die Anzahl der Köpfe, rechts jene der Schwänze. Der Ausdruck in eckigen Klammern gibt an, wieviele Schwerthiebe nötig sind, um einen Drachen in den folgenden zu überführen:

(2*k+1 , 4*l+3)
[k]
(1 , 4*l+3)
[3]
(1 , 4*l+6)
[2*l+3]
(2*l+4 , 0)
[l+2]
(0 , 0)
Somit braucht der Ritter k+3*l+8=9 Schläge, was wunderbar oberhalb des durch C vorgeschriebenen Minimums liegt.

Das mathematische Problem stammt von Univ.-Prof. Dr. Gerd Baron und Dr. Richard F. Mischak. Weitere Aufgaben finden Sie auf den Seiten des Wettbewerbs Jagd auf Zahlen und Figuren. Die erzählerische "Verpackung" gestaltete Dr. Olaf Fritsche.