Polynom erraten [gelöst]

10.10.2005, 15:23

toaster

Auf diesen Beitrag antworten »

Polynom erraten [gelöst]

Alice: Ich denke mir ein Polynom mit nichtnegativen ganzzahligen Koeffizienten. Kannst du es erraten?

Bob: Nein, dazu brauche ich weitere Angaben. Darf ich dich nach ein paar Funktionswerten fragen?

Alice: Ja natürlich. Wie viele hättest du denn gerne?

Bob: Nun, n+1 wären nicht schlecht, wenn n der Grad deines Polynoms ist. Dann hätte ich n+1 Gleichungen für die n+1 Koeffizienten.

Alice: Das wäre mir viel zu aufwendig. Außerdem kennst du den Grad nicht, und ich werde ihn dir nicht verraten. Aber ich kann dir für zwei ganzzahlige Argumente, die du wählen kannst, jeweils den Wert des Polynoms angeben.

Kann Bob damit das Polynom von Alice bestimmen?

viel glück
Hammer

Hammer

10.10.2005, 16:48

AD

Auf diesen Beitrag antworten »

Antwort: Ja, sofern er den ersten Funktionswert erfährt, bevor er das zweite Argument nennen muss. smile

smile

10.10.2005, 23:45

pimaniac

Auf diesen Beitrag antworten »

hm interessant... is das sowas alla

1,1010010001000010000010000001000000010000000010000000001 usw?

10.10.2005, 23:48

JochenX

Auf diesen Beitrag antworten »

hmmm, ADs hinweis im anderen rätsel lockt noch mehr leute an Augenzwinkern

Augenzwinkern

deinen hinweis verstehe ich gar nicht, pi
deine zahl ist nicht sonderlich ganzzahlig verwirrt

verwirrt

bleibt natürlich die frage, ob das mit allen polynomen dieses types machbar ist, oder ob nur bei alices spezieller polynomwahl erratbar ist
nur das erstere macht an sich sinn..... denke ich.....
aber nur für zweiteres würden mir ansätze einfallen (ein Teufel

Teufel

skreis )

also weiterdenken.....

edit: ich sag schon mal uffa, wrgl, ist ja eigentlich ganz leicht, muss aber noch mal nachdenken, nicht dass ich was dummes sage
hihi, ja raffiniert

10.10.2005, 23:51

pimaniac

Auf diesen Beitrag antworten »

oh ganzzahlige argumente.... dass is natürlich was anderes.... :-)

10.10.2005, 23:52

AD

Auf diesen Beitrag antworten »

Also doch nicht zu einfach - schön. Teufel

Teufel

Man muss natürlich alle Voraussetzungen richtig ausnutzen, soviel sollte ja klar sein.

Anzeige

10.10.2005, 23:52

pimaniac

Auf diesen Beitrag antworten »

ah ganzzahlige Argumente, na gut

mir is die Lösung aber trotzdem grad eingefallen

Ist die erste Zahl vielleicht 1 und die zweite die Antwort vom ersten?

Unter der Vorraussetzung dass es sich um ein brauchbares Polynom handelt reicht mir sogar eine Zahl 10^10^10^10^10^10^10^10 sollte im normalfall reichen

10.10.2005, 23:59

JochenX

Auf diesen Beitrag antworten »

oh, pi, was ist denn ein "brauchbares polynom" Augenzwinkern

Augenzwinkern

erste antwort sollte so aber passen, genau das war auch mein vierte gedanke
wobei ich am überlegen bin, ob das so reicht, oder ob man die zweite zahl nicht um eins erhöhen sollte

10.10.2005, 23:59

AD

Auf diesen Beitrag antworten »

Ich denke, das reicht nicht ganz. Meine Lösung weicht etwas davon ab:

x_1 = 1
x_2 = f(x_1)+1 = f(1)+1

EDIT: Da war der Jochen 5 Sekunden schneller...

11.10.2005, 00:03

pimaniac

Auf diesen Beitrag antworten »

ja stimmt natürlich.... ich hab mit 2 als erstes argument begonnen funktioniert natürlich auch dann reicht halt f(2).... wie ich ann eins runtergegangen bin hab ich das natürlich vergessen

11.10.2005, 00:05

JochenX

Auf diesen Beitrag antworten »

aber ich war mir nicht ganz sicher
ich hatte nur im blut, das zweitere müsste auf jeden fall reichen Augenzwinkern

Augenzwinkern

und dann eben die alte weisheit: "lieber einmal zuviel nach rechts und links geschaut als einmal zu wenig" oder so ähnlich

heute ist rätseltag

07.11.2005, 17:37

Mathe-Student

Auf diesen Beitrag antworten »

Bin nach 1jaehriger Abwesenheit auch mal wieder hier...

Zuerst mal sollten wir davon ausgehen, dass das Polynom nicht unendlich-dimensional ist, sonst klappts naemlich nicht.

Dies ausgeschlossen, ist es loesbar und ich wuerde die Funktionswerte 1 und 10^j vorschlagen mit j:=Anzahl der Dezimalstellen von f(1).
Anschliessend kann man die Koeffizienten alle j-Stellen ablesen.

/EDIT: So nu is es klein und ich verrate nix

11.11.2005, 23:20

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von Mathe-Student
Zuerst mal sollten wir davon ausgehen, dass das Polynom nicht unendlich-dimensional ist, sonst klappts naemlich nicht.

nanana

Augenzwinkern

das ist zum einen mathematisch unsinnig, da ein polynom keine dimension hat, höchstens der polynomraum als vektorraum.
zum anderen ist bei einem polynom auch vorausgesetzt, dass nur endlich viele koeffizienten ungleich 0 sind....

öhm, aber das ist OT

12.11.2005, 01:30

Calvin

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ich denke, das reicht nicht ganz. Meine Lösung weicht etwas davon ab:

x_1 = 1
x_2 = f(x_1)+1 = f(1)+1

Entweder ich habe die Aufgabe nicht verstanden, oder ich sehe den Trick nicht. Wieso reicht das aus, um das Polynom zu erraten?

Wie kommt man z.B. von f(1)=10 und f(11)=410 auf f(x)=3x²+4x+3 verwirrt

verwirrt

12.11.2005, 01:59

JochenX

Auf diesen Beitrag antworten »

es gilt: da die koeffizeinten >0 sind, ist der wert restpolynom (ohne das größtgradige glied) <10*11=110

dein höchster grad ist 2, koeffizient davor sei a
bahauptung: a ist eindeutig
klar: a nach oben beschränkt (in deinem fall eben 3 größter wert, den man einsetzen kann)
dann muss aber a=3 sein, denn wäre a<3, oE 2, dann würden ja schon mehr als 11^2=121 fehlen.....

damit 3 eindeuti bestimmt und dann rekursiv auflösen

das war jetzt gemisch aus einem versuchten beweis und erklärung am beispiel
Hammer

Hammer

man verzeihe es mir wegen icq-gespräh nebenher und später zeit

klarer?

12.11.2005, 08:17

AD

Auf diesen Beitrag antworten »

Ich schreib's nochmal im ganzen auf (du mögest mir verzeihen, Jochen, aber du kennst ja meinen Hang zu klaren geschlossenen Darstellungen - zumindest was ich subjektiv als klar empfinde Big Laugh

Big Laugh

).

Wir sollen ein Polynom $\begin{eqnarray*} f(x)=a_0+a_1x+\cdots+a_nx^n \end{eqnarray*}$ erraten, d.h., wir kennen weder den Grad $\begin{eqnarray*} n \end{eqnarray*}$ noch die Koeffizienten $\begin{eqnarray*} a_0,a_1,\ldots,a_n \end{eqnarray*}$ . Zumindest wissen wir, dass die Koeffizienten nichtnegativ ganzzahlig sind.

Als erstes Argument wählen wir 1, und erfahren $\begin{eqnarray*} f(1)=a_0+a_1+\cdots+a_n \end{eqnarray*}$ . Als zweites Argument können wir nun eine beliebige ganze Zahl $\begin{eqnarray*} b\geq f(1)+1 \end{eqnarray*}$ wählen, denn für jeden Index $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq n \end{eqnarray*}$ können wir wegen der Nichtnegativität aller Koeffizienten folgendermaßen $\begin{eqnarray*} a_k \end{eqnarray*}$ abschätzen:

$\begin{eqnarray*} 0 \leq a_k \leq a_0+a_1+\ldots+a_n = f(1) \leq b-1 \end{eqnarray*}$ .

Wenn wir nun $\begin{eqnarray*} f(b)=a_0+a_1b+\cdots+a_nb^n \end{eqnarray*}$ betrachten, dann ist $\begin{eqnarray*} f(b) \end{eqnarray*}$ im Zahlensystem zur Basis $\begin{eqnarray*} b \end{eqnarray*}$ schlicht und einfach $\begin{eqnarray*} f(b)=[a_n\ldots a_1a_0]_b \end{eqnarray*}$ , d.h., man erhält die Koeffizienten direkt als "Ziffern". Diese $\begin{eqnarray*} b \end{eqnarray*}$ -Zahlensystemdarstellung ist bekanntlich eindeutig und ist hier anwendbar, weil eben alle Koeffizienten durch $\begin{eqnarray*} 0 \leq a_k \leq b-1 \end{eqnarray*}$ beschränkt sind.

Der Bequemlichkeit wegen ist es natürlich anratsam, für b gleich eine Zehnerpotenz zu wählen, so wie von Mathe-Student vorgeschlagen. Auf das Beispiel f(x)=3x²+4x+3 von Calvin angewandt, erfahren wir ja f(1)=10 und würden da zweckmäßig b=100 wählen:

f(100) = 30403

P.S. (off-topic): Schade, dass man hier im Board LaTeX-Formeln nicht einfärben kann...

12.11.2005, 15:10

Calvin

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Wenn wir nun $\begin{eqnarray*} f(b)=a_0+a_1b+\cdots+a_nb^n \end{eqnarray*}$ betrachten, dann ist $\begin{eqnarray*} f(b) \end{eqnarray*}$ im Zahlensystem zur Basis $\begin{eqnarray*} b \end{eqnarray*}$ schlicht und einfach $\begin{eqnarray*} f(b)=[a_n\ldots a_1a_0]_b \end{eqnarray*}$ , d.h., man erhält die Koeffizienten direkt als "Ziffern".

Aha, das hat mir also gefehlt. Danke für die Erklärung. Durchaus interessant, was man noch so alles Lernen kann smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »