Welches Polynom?
Das folgende Problem stammt im Kern aus Peter Winklers hervorragendem Buch "Mathematical Mind-Benders".
"Ich denke mir ein Polynom aus, und Du sollst es erraten."
"Wie soll ich es erraten?"
"Du nennst mir eine Zahl, ich setze sie in mein Polynom ein und sage Dir das Ergebnis. Das wiederholen wir so lange, bis Du mein Polynom kennst. Die Herausforderung besteht darin, es möglichst schnell zu schaffen."
"Verstehe. Ich habe auch schon eine Idee. Wir werden uns sicherlich auf den maximalen Grad verständigen, den Dein Polynom haben darf, sonst habe ich ja keine Chance."
"Falsch. Ich werde Dir nichts über den Grad des Polynoms verraten. Statt dessen vereinbaren wir ein paar andere Einschränkungen:
- Es soll nur um reelle Polynome gehen,
- und alle Koeffizienten sind natürliche Zahlen oder Null.
- Für Dich gibt es auch eine kleine Bedingung:
Deine Eingabewerte sollen rational sein."
"Das finde ich ziemlich schwierig und aufwändig."
"Nein, es ist ganz einfach. Möchtest Du einen Tipp?"
Lösung
Die Lösung mag erstaunlich klingen:
Zwei Zahlen reichen als Eingabewerte, um das Polynom zu bestimmen.
Der Grund dafür ist, dass keine negativen Koeffizienten zugelassen sind. Die Lösungsidee ist im Wesentlichen das Einsetzen genügend großer Zahlen in das Polynom. Hier ist ein Beispiel:
p(x) = 19 x3 + x2 + 95 x + 623
p(1000) = 19.001.095.623
Durch das Einsetzen der Zehnerpotenz können wir die Koeffizienten am Ausgabewert direkt ablesen. Dabei spielt der Grad des Polynoms keine Rolle. Allerdings muss die Zehnerpotenz größer sein als der größte Koeffizient. Um das sicherzustellen, gibt es eine einfache Möglichkeit: p(1) ist sicherlich mindestens so groß wie der größte Koeffizient. Wir fassen die Strategie des Polynomraters zusammen:
- Nenne x = 1 → erhalte p(1)
- Nenne x = 10n > p(1) → erhalte p(10n) → diese Zahl zeigt die Koeffizienten von p in Blöcken der Länge n
Damit ist das Problem gelöst.
Wir haben in diesem Lösungsweg 10n als "Basis" für die Lösung genommen. Peter Winkler bedient sich in seinem Buch nicht dieser naheliegenden Lösung, sondern wählt eine beliebige Basis b > p(1). Dann muss man in einem letzten Schritt p(b) als b-adische Zahl schreiben. Ein Beispiel dazu:
p(x) = x6 + x3 + 11 x2 + 1
p(1) = 14 → wähle b = 16
p(16) = 16784129
Wegen b = 16 wandeln wir p(16) in eine Hexadezimalzahl um: p(16) = 1678412910 = 1001B0116
B16 steht für 1110 , also können wir alle Koeffizienten von p ablesen.
1. Bemerkung: Warum soll der Polynomrater keine irrationalen Zahlen nennen?
Der Problemsteller hatte wohl nicht-algebraische Zahlen wie e im Sinn. Falls sein Polynom beispielsweise p(x) = 21 x3 + 11 lautet und der Polynomrater x = e nennt, so stellt sich die Frage, wie man 21 e3 + 11 zurückgeben soll, ohne dabei e zu nennen (sonst würde man sogar mit einem einzigen Eingabewert auskommen). Näherungswerte helfen hier nicht weiter.
2. Bemerkung: Der Polynomrater sagt, bevor er die genauen Regeln kennt: "Ich habe auch schon eine Idee." Welche Idee könnte das sein?
Der Polynomrater geht davon aus, dass er vorab über den Grad q des Polynoms informiert wird. Vermutlich wollte er die Lösung über ein Gleichungssystem finden, indem er q + 1 verschiedene Eingabewerte nennt und durch die zurückgegebenen Werte q + 1 lineare Gleichungen für die q + 1 Koeffizienten erhält. Beispielsweise könnten die ersten q + 1 natürlichen Zahlen als Eingabewerte dienen.
Publiziert 2011-03-27 Stand 2010-10-02
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem
Manfred Börgens |
zur Leitseite