kad hat geschrieben: ↑09.09.2024, 16:12
Ein erstaunliches Resultat hat
Das Orakel in Delphi hat ein bestimmtes Polynom p (z. B. in der Variablen x) mit nichtnegativen (>0) ganzzahligen Koeffizienten im Sinn. Du kannst das Orakel mit einer beliebigen ganzen Zahl x abfragen, und das Orakel wird dir den Wert von p(x) mitteilen. Wie viele Abfragen musst du machen, um p zu bestimmen?
Na, das spar ich mir doch die Mühe noch drüber nachzudenken, ob N+2
in diesem speziellen Fall nicht doch reichen würde und wie man das zeigen könnte,
falls dem so wäre.
Die 2 sind mir aber völlig schleierhaft.
Die Polynome P1=(x+1), P2=(x^2+1)...Pn=(x^n+1) haben nichtnegativen (>0) ganzzahligen Koeffizienten (1,1)
und die beiden ganzzahligen Stützstellen/Stützwerte (0,1) und (1,2) gemeinsam.
Wie soll nun nur mit diesen beiden Stützstellen bestimmt werden, an welches Pi das Oraktel grad denkt?
Hab ich da was übersehen oder missverstanden?
Aber danke, war nett sich wieder mal mit Lagrange-Polynomen zu beschäftigen.
Ja, diese Polynome teilen diese beiden Stützstellen/Stützwerte.
Nur, das ist noch kein Argument.
Du hast, glaube ich, nichts missverstanden/übersehen: einfach noch nicht den richtigen Ansatz gewählt.
Wenn du die Zahl 0 ans Oracle schickst, bekommst du eine Zahl zurück. Was kannst du dann daraus für die Koeffizienten des Polynoms ableiten?
kad hat geschrieben: ↑09.09.2024, 16:12
Ein erstaunliches Resultat hat
Das Orakel in Delphi hat ein bestimmtes Polynom p (z. B. in der Variablen x) mit nichtnegativen (>0) ganzzahligen Koeffizienten im Sinn. Du kannst das Orakel mit einer beliebigen ganzen Zahl x abfragen, und das Orakel wird dir den Wert von p(x) mitteilen. Wie viele Abfragen musst du machen, um p zu bestimmen?
Für die Polynominterpolation brauch ich eine Stützstelle mehr als den Grad des Polynoms.
Nun weiss ich aber nicht welchen Grad das Polynom hat.
Grundlegend gilt, dass N+1 Stützstellen zur Interpolation eines Polynoms des Grads N zwar reichen würde,
diese N+1 Stützstellen aber auch eine Teilmenge der Stützstellen eines Polynoms noch höheren Grades sein könnten.
Insofern könnte man Polynome niedrigeren Grades zwar auschließen, aber keine höhergradigen.
Also grundsätzlich würde ich sagen, das geht gar nicht.
Allerdings steht oben "ganzzahlige" x und "positive ganzahlige" Koeffizienten.
Hier die Anzahl
2
Wieso reicht das?
Na, das spar ich mir doch die Mühe noch drüber nachzudenken, ob N+2
in diesem speziellen Fall nicht doch reichen würde und wie man das zeigen könnte,
falls dem so wäre.
Die 2 sind mir aber völlig schleierhaft.
Die Polynome P1=(x+1), P2=(x^2+1)...Pn=(x^n+1) haben nichtnegativen (>0) ganzzahligen Koeffizienten (1,1)
und die beiden ganzzahligen Stützstellen/Stützwerte (0,1) und (1,2) gemeinsam.
Wie soll nun nur mit diesen beiden Stützstellen bestimmt werden, an welches Pi das Oraktel grad denkt?
Hab ich da was übersehen oder missverstanden?
Aber danke, war nett sich wieder mal mit Lagrange-Polynomen zu beschäftigen.
Ja, diese Polynome teilen diese beiden Stützstellen/Stützwerte.
Nur, das ist noch kein Argument.
Du hast, glaube ich, nichts missverstanden/übersehen: einfach noch nicht den richtigen Ansatz gewählt.
Wenn du die Zahl 0 ans Oracle schickst, bekommst du eine Zahl zurück. Was kannst du dann daraus für die Koeffizienten des Polynoms ableiten?
Na, dann kenne ich k0 (Koeffizient bei x^0)
Daraus könnte man dann folgern.
Pn-k0= x*(kn-1*x^(n-1)+....+k1)
Selbst wenn diese Rekursion lösbar wäre, bräuchte ich n+1 Schritte für alle Koeffizienten
Hier noch mal das Edit von oben:
Hab ich da was übersehen oder missverstanden?
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Schauen wir uns das mal im einfachsten Fall an den Stellen 0 und 1 an.
Alle Koeffizienten sind 1.
x+1 -> 1,2
x^2+x+1 -> 1,3
x^3+x^2+x+1 -> 1,4
x^n...+1 -> 1,n+1
schön, aber
2x+1 -> 1,3
Ev. sind da die Stützstellen 0 und 2 geeigneter.
x+1 -> 1,3
x^2+x+1 -> 1,7
x^3+x^2+x+1 -> 1,15
x^n...+1 -> 1,(2^n+1)-1
Das sieht schon besser aus.
Wenn wir jetzt noch beweisen könnten, dass sich diese Polynome (mit beliebigen Koeffizienten >0) an der Stützstelle 2
eindeutig unterscheiden, könnten wir jedem dieser Polynome den Stützwert bei 2 als Kennung zuweisen und damit identifizieren.
Nein, das geht auch nicht.
Mit geeigneten 2'er Potenzen als Koeffizienten kann man nach belieben gleiche Ergebnisse erzielen.
2x^2+x+1=11
x^2+3x+1=11
Vermutlich kann man dieses Vertauschspiel für jedes Polynom und jede beliebige Stützstelle spielen.
Zuletzt geändert von giffi marauder am 10.09.2024, 09:53, insgesamt 1-mal geändert.
kad hat geschrieben: ↑09.09.2024, 16:12
Ein erstaunliches Resultat hat
Das Orakel in Delphi hat ein bestimmtes Polynom p (z. B. in der Variablen x) mit nichtnegativen (>0) ganzzahligen Koeffizienten im Sinn. Du kannst das Orakel mit einer beliebigen ganzen Zahl x abfragen, und das Orakel wird dir den Wert von p(x) mitteilen. Wie viele Abfragen musst du machen, um p zu bestimmen?
Für die Polynominterpolation brauch ich eine Stützstelle mehr als den Grad des Polynoms.
Nun weiss ich aber nicht welchen Grad das Polynom hat.
Grundlegend gilt, dass N+1 Stützstellen zur Interpolation eines Polynoms des Grads N zwar reichen würde,
diese N+1 Stützstellen aber auch eine Teilmenge der Stützstellen eines Polynoms noch höheren Grades sein könnten.
Insofern könnte man Polynome niedrigeren Grades zwar auschließen, aber keine höhergradigen.
Also grundsätzlich würde ich sagen, das geht gar nicht.
Allerdings steht oben "ganzzahlige" x und "positive ganzahlige" Koeffizienten.
Hier die Anzahl
2
Wieso reicht das?
Na, das spar ich mir doch die Mühe noch drüber nachzudenken, ob N+2
in diesem speziellen Fall nicht doch reichen würde und wie man das zeigen könnte,
falls dem so wäre.
Die 2 sind mir aber völlig schleierhaft.
Die Polynome P1=(x+1), P2=(x^2+1)...Pn=(x^n+1) haben nichtnegativen (>0) ganzzahligen Koeffizienten (1,1)
und die beiden ganzzahligen Stützstellen/Stützwerte (0,1) und (1,2) gemeinsam.
Wie soll nun nur mit diesen beiden Stützstellen bestimmt werden, an welches Pi das Oraktel grad denkt?
Hab ich da was übersehen oder missverstanden?
Aber danke, war nett sich wieder mal mit Lagrange-Polynomen zu beschäftigen.
Ja, diese Polynome teilen diese beiden Stützstellen/Stützwerte.
Nur, das ist noch kein Argument.
Du hast, glaube ich, nichts missverstanden/übersehen: einfach noch nicht den richtigen Ansatz gewählt.
Wenn du die Zahl 0 ans Oracle schickst, bekommst du eine Zahl zurück. Was kannst du dann daraus für die Koeffizienten des Polynoms ableiten?
Na, dann kenne ich k0 (Koeffizient bei x^0)
Daraus könnte man dann folgern.
Pn-k0= x*(kn-1*x^(n-1)+....+k1)
Selbst wenn diese Rekursion lösbar wäre, bräuchte ich n+1 Schritte für alle Koeffizienten
Ok, hier noch mal das Edit von oben:
Hab ich da was übersehen oder missverstanden?
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Schauen wir uns das mal im einfachsten Fall an den Stellen 0 und 1 an.
Alle Koeffizienten sind 1.
x+1 -> 1,2
x^2+x+1 -> 1,3
x^3+x^2+x+1 -> 1,4
x^n...+1 -> 1,n+1
schön, aber
2x+1 -> 1,3
Ev. sind da die Stützstellen 0 und 2 geeigneter.
x+1 -> 1,3
x^2+x+1 -> 1,7
x^3+x^2+x+1 -> 1,15
x^n...+1 -> 1,(2^n+1)-1
Das sieht schon besser aus.
Wenn wir jetzt noch beweisen könnten, dass sich diese Polynome (mit beliebigen Koeffizienten >0) an der Stützstelle 2
eindeutig unterscheiden, könnten wir jedem dieser Polynome den Stützwert bei 2 als Kennung zuweisen und damit identifizieren.
Nein, das geht auch nicht.
Mit geeigneten 2'er Potenzen als Koeffizienten kann man nach belieben gleiche Ergebnisse erzielen.
2x^2+x+1=11
x^2+4x+1=11
Vermutlich kann man dieses Vertauschspiel für jedes Polynom und jede beliebige Stützstelle spielen.
Hab ich da was übersehen oder missverstanden?
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Mir ist in der Aufgabenstellung ein Fehler unterlaufen. Ich hätte schreiben sollen „..mit nichtnegativen (>=0)..“
Weil, x^2+1. ist zulässig.
Mea culpa
Und jetzt frage dich das Oracle, was bei x=1 herauskommt… und was bedeutet das für die Koeffizienten?
Zuletzt geändert von kad am 10.09.2024, 09:54, insgesamt 1-mal geändert.
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Mir ist in der Aufgabenstellung ein Fehler unterlaufen. Ich hätte schreiben sollen „..mit nichtnegativen (>=0)..“
Weil, x^2+1. ist zulässig.
Mea culpa
Tja, dann.
Und jetzt frage dich das Oracle, was bei x=1 herauskommt… und was bedeutet das für die Koeffizienten?
Na ja f(0) ist k0
f(1) ist kn+..+k0
Da gibts aber immer noch viele Möglichekeiten für die ki i>0
f(0),f(1)
x^2+x+1 -> 1,3
2x+1 -> 1,3
2xi+1 -> 1,3
x^i+x^j+1= 1,3
...
Welches Schweinderl hättens denn gern?
Irgendwie steh ich auf dem Schlauch.
Wir wissen jetzt also dass alle Koeffizienten kleiner gleich f(1) sind (weil die Summer der Koeffizienten = f(1) ist).
Jetzt kannst du dem Orakel zb f(1) +1 schicken (oder irgendeine Zahl m grösser f(1)).
Wenn du das Resultat vom Orakel bekommst, musst du nur noch…..
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Mir ist in der Aufgabenstellung ein Fehler unterlaufen. Ich hätte schreiben sollen „..mit nichtnegativen (>=0)..“
Weil, x^2+1. ist zulässig.
Mea culpa
Tja, dann.
Und jetzt frage dich das Oracle, was bei x=1 herauskommt… und was bedeutet das für die Koeffizienten?
Na ja f(0) ist k0
f(1) ist kn+..+k0
Da gibts aber immer noch viele Möglichekeiten für die ki i>0
f(0),f(1)
x^2+x+1 -> 1,3
2x+1 -> 1,3
2xi+1 -> 1,3
x^i+x^j+1= 1,3
...
Welches Schweinderl hättens denn gern?
Irgendwie steh ich auf dem Schlauch.
Wir wissen jetzt also dass alle Koeffizienten kleiner gleich f(1) sind (weil die Summer der Koeffizienten = f(1) ist).
Jetzt kannst du dem Orakel zb f(1) +1 schicken (oder irgendeine Zahl m grösser f(1)).
Wenn du das Resultat vom Orakel bekommst, musst du nur noch…..
Ah jetzt.
Wären alle Koeffizienten<99 bräuchte ich f(100) und schon könnte ich sie nach belieben ablesen.
d.h.
Frage 1:
x1=1
y1=f(x1)
Frage 2:
x2=y1+1
y2=f(x2)
x2 ist dann die Zahlenbasis für y2 und muss noch in dezimal umberechnet werden,
oder alternativ
Frage 2:
x2=kleinstes 10^n > y1
y2=f(x2)
mit je n Ziffern pro Koeffizent.
Ev. dass x^2+1 gar nicht zulässig ist, weil dies auch als 1x^2+0x+1x geschrieben werden könnte
und der Koeffizient von x hier 0 ist?
Mir ist in der Aufgabenstellung ein Fehler unterlaufen. Ich hätte schreiben sollen „..mit nichtnegativen (>=0)..“
Weil, x^2+1. ist zulässig.
Mea culpa
Tja, dann.
Und jetzt frage dich das Oracle, was bei x=1 herauskommt… und was bedeutet das für die Koeffizienten?
Na ja f(0) ist k0
f(1) ist kn+..+k0
Da gibts aber immer noch viele Möglichekeiten für die ki i>0
f(0),f(1)
x^2+x+1 -> 1,3
2x+1 -> 1,3
2xi+1 -> 1,3
x^i+x^j+1= 1,3
...
Welches Schweinderl hättens denn gern?
Irgendwie steh ich auf dem Schlauch.
Wir wissen jetzt also dass alle Koeffizienten kleiner gleich f(1) sind (weil die Summer der Koeffizienten = f(1) ist).
Jetzt kannst du dem Orakel zb f(1) +1 schicken (oder irgendeine Zahl m grösser f(1)).
Wenn du das Resultat vom Orakel bekommst, musst du nur noch…..
Ah jetzt.
Wären alle Koeffizienten<99 bräuchte ich f(100) und schon könnte ich sie nach belieben ablesen.
d.h.
Frage 1:
x1=1
y1=f(x1)
Frage 2:
x2=y1+1
y2=f(x2)
x2 ist dann die Zahlenbasis für y2 und muss noch in dezimal umberechnet werden,
oder alternativ
Frage 2:
x2=kleinstes 10^n > y1
y2=f(x2)
mit je n Ziffern pro Koeffizent.
Ziemlich cool.
Genau: die Dezimalzahl y2 darstellen in der Basis x2 ergibt die Koeffizienten des Polynoms.
Du sagst, wenn du weitere Rätsel magst. Ich kann auch Pause machen. Oder es hat noch ein paar ungelöste…. Oder du kannst wieder eines stellen….
Comme vous voulez!
Und du hast nie gesagt, ob p=3/5. die richtige Lösung ist zur Bonusfrage
Barbara wechselt ihre Münze zu einer Trickmünze, die mit einer etwas höheren Wahrscheinlichkeit eine "1" münzelt.
Tim darf dafür die faire Münze alleine weiterbenutzen.
Dadurch annuliert sie den Vorteil von Tim und die Chance auf Sieg ist für beide wieder gleich hoch.
Wie hoch muss die Wahrscheinlichkeit dieser Trickmünze für eine "1" sein?
kad hat geschrieben: ↑10.09.2024, 10:47
Und du hast nie gesagt, ob p=3/5. die richtige Lösung ist zur Bonusfrage
Barbara wechselt ihre Münze zu einer Trickmünze, die mit einer etwas höheren Wahrscheinlichkeit eine "1" münzelt.
Tim darf dafür die faire Münze alleine weiterbenutzen.
Dadurch annuliert sie den Vorteil von Tim und die Chance auf Sieg ist für beide wieder gleich hoch.
Wie hoch muss die Wahrscheinlichkeit dieser Trickmünze für eine "1" sein?
Weil ich meinen Wert auf die Zusatzfrage von der falschen Antwort davor abgeleitet hatte.
Da muss ich selber noch mal ran.
Also ja, mit 3/5 wäre die Partei wieder ausgeglichen (mit leichtem Vorteil für Barbara 38,5% zu 37,8%)
Das ist aber ev. auch bloß ein Rundungsfehler in Excel.
Mit 7/10 hätte Barbara jetzt 50,7%, was ansonsten Tim durch den Vorteil des 6. Wurfes hätte.
Fritz will einen Fußball mit Durchmesser 30 cm und sechs Tennisbälle mit Durchmesser von je 8 cm in einer quaderförmigen Schachtel verpacken. Welches ist die Schachtel mit der kleinsten Oberfläche, für die dies möglich ist?
kad hat geschrieben: ↑10.09.2024, 10:47
Und du hast nie gesagt, ob p=3/5. die richtige Lösung ist zur Bonusfrage
Barbara wechselt ihre Münze zu einer Trickmünze, die mit einer etwas höheren Wahrscheinlichkeit eine "1" münzelt.
Tim darf dafür die faire Münze alleine weiterbenutzen.
Dadurch annuliert sie den Vorteil von Tim und die Chance auf Sieg ist für beide wieder gleich hoch.
Wie hoch muss die Wahrscheinlichkeit dieser Trickmünze für eine "1" sein?
Weil ich meinen Wert auf die Zusatzfrage von der falschen Antwort davor abgeleitet hatte.
Da muss ich selber noch mal ran.
Also ja, mit 3/5 wäre die Partei wieder ausgeglichen (mit leichtem Vorteil für Barbara 38,5% zu 37,8%)
Das ist aber ev. auch bloß ein Rundungsfehler in Excel.
Mit 7/10 hätte Barbara jetzt 50,7%, was ansonsten Tim durch den Vorteil des 6. Wurfes hätte.
Rechenfehler vorbehalten.
Danke. Ich kann alles Nachvollziehen. Das mit 7/10 ist hübsch. Und ja, das müssen Rundungsfehler sein.
kad hat geschrieben: ↑11.09.2024, 09:03
Fritz will einen Fußball mit Durchmesser 30 cm und sechs Tennisbälle mit Durchmesser von je 8 cm in einer quaderförmigen Schachtel verpacken. Welches ist die Schachtel mit der kleinsten Oberfläche, für die dies möglich ist?
Na ja, bei 8 Tennisbällen wäre meine Spontanvermutung, Fussball (F) in die Mitte und in jeder Ecke ein Tennisball (T) verpackt in einen Würfel.
Das wären dann für eine halbe Raum-Diagonale:
15 cm für den Radius von F + 4cm für den Radius der Hälfte eines T + sqrt(3*4^2) für die Diagonale des Tangentenwürfels der zweiten Hälfte des T = 25,928 cm.
Die gesamte Raum-Diagonale (D) wäre dann 51,568 und die Seitenlänge der würfelförmigen Schachtel (sqrt(D*D/3)) = 29,9393
Da die minimale Seitenlänge aber 30 ist, könnten die 8 T auch noch ein bisschen größer sein.
Meine Vermutung ist, dass das auch optimal für 6 T ist, da die Schachtel ja wohl nicht kleiner als 30x30x30 sein kann
und dies auch optimal in Hinblick auf die Oberfläche ist.
kad hat geschrieben: ↑11.09.2024, 09:03
Fritz will einen Fußball mit Durchmesser 30 cm und sechs Tennisbälle mit Durchmesser von je 8 cm in einer quaderförmigen Schachtel verpacken. Welches ist die Schachtel mit der kleinsten Oberfläche, für die dies möglich ist?
Na ja, bei 8 Tennisbällen wäre meine Spontanvermutung, Fussball (F) in die Mitte und in jeder Ecke ein Tennisball (T) verpackt in einen Würfel.
Das wären dann für eine halbe Raum-Diagonale:
15 cm für den Radius von F + 4cm für den Radius der Hälfte eines T + sqrt(3*4^2) für die Diagonale des Tangentenwürfels der zweiten Hälfte des T = 25,928 cm.
Die gesamte Raum-Diagonale (D) wäre dann 51,568 und die Seitenlänge der würfelförmigen Schachtel (sqrt(D*D/3)) = 29,9393
Da die minimale Seitenlänge aber 30 ist, könnten die 8 T auch noch ein bisschen größer sein.
Meine Vermutung ist, dass das auch optimal für 6 T ist, da die Schachtel ja wohl nicht kleiner als 30x30x30 sein kann
und dies auch optimal in Hinblick auf die Oberfläche ist.
Du liesst dich wegen der 6 (statt 8) Tennisbällen nicht verwirren.
Natürlich richtig.