Polynomkluring.

Borde funka med 2 gissningar.

Först frågar man P(1) och får svaret n, summan av koefficienterna. Eftersom koefficienterna är positiva har vi att n+1 är större än varje koefficient.

Så vi frågar sedan P(n+1), svaret i bas n+1 ger oss entydigt koefficienterna.

Jag är genuint lite ställd lite ställd av det här resultatet.

Man kan ställa frågor P(1),P(2),P(3).... osv, godtyckligt många frågor och det kan finnas oändlig många polynom som har samma värden.

Men fråga P(1) och P(P(1)+1) så är det entydigt bestämt!

Anta att polynomet är $P(x)=a_0x+a_1x+\cdots+a_nx^n$.

1. Fråga om vilket input $k\geq 1$ som helst, och låt $m=P(k)$. Det kommer gälla att $m\geq \sum_{i=1}^na_i$.
   Om $m=0$ så kan vi dra slutsatsen att $P=0$. Annars, fortsätt till steg 2. 
2. Fråga om valfritt input $\ell>m$. De okända koefficienterna $a_0,\ldots,a_n$ ges då av $P(\ell)$ uttryckt i basen $\ell$. 

Observera att det är viktigt att vi bara får fråga om P(k) där k är heltal.

Annars hade det räckt med en enda gissning, fråga P(pi), eftersom pi är transcendentalt kan inte två polynom med heltalskoefficienter anta samma värde i pi och eftersom mängden av polynom med heltalskoefficienter är uppräknelig så kan vi gå igenom den mängden, en och en, tills vi matchar P(pi)

Hur många decimaler tänker du be oraklet om när du frågar om P(pi)? 🙂

Tänkte också på detta. Vad händer om oraklet måste svara exakt? 

Så om $P(x) = 3x^2 +2x +1$ måste den svara $3\pi^2 +2\pi +1$ 😇