Polly's Perplexing Puzzle

[mmm4444bot]

From a University of Washington web site. (I changed the name to Polly.)

Polly is thinking of a polynomial P(x).

She tells you that all of the coefficients are non-negative integers, and, if you query her about any integer value x, she will the tell you the value of P(x).

However, she won't tell you anything else about the polynomial — you don't even know the degree.

She brags that she has a "really hard" polynomial that you won't be able to figure out, even after many queries.

How can you surprise Polly?

I'll post one solution, in a few days.

 

[soroban]

Hello, mmm4444bot!

I have a rather primitive method . . .

Polly is thinking of a polynomial P(x).
She tells you that all of the coefficients are non-negative integers.
If you query her about any integer value \(\displaystyle x\), she will the tell you the value of \(\displaystyle P(x).\)
However, she won't tell you anything else about the polynomial — you don't even know the degree.
She brags that she has a "really hard" polynomial that you won't be able to figure out, even after many queries.

How can you surprise Polly?

\(\displaystyle \text{Ask her for the values of: }\(0),\;P(1),\;P(2),\;P(3)\;\hdots\)

\(\displaystyle \text{Suppose her answers are: }\:5,\:13,\:33,\:71,\:133,\:225\:\hdots\)


Find the differences of consecutive values,
. . then find the differences of the differences, and so on.


\(\displaystyle \begin{array}{ccccccccccccc}\text{Sequence} & 5 && 13 && 33&& 71 && 133 && 225 \\ \text{1st diff.} && 8 && 20 && 38 && 62 && 92 \\ \text{2nd diff.} &&& 12 && 18 && 24 && 30 \\ \text{3rd diff} &&&& 6 && 6 && 6 \end{array}\)


When we reach a row of constants, we have the determined the degree of the polynomial.

In the example, the 3rd differences are constant . . . The polynomial is a cubic.


\(\displaystyle \text{The general cubic function is: }\;P(x) \:=\:ax^3 + bx^2 + cx + d\)


Use the first four values to set up a system of equations:

. . \(\displaystyle \begin{array}{cccccccccc}P(0) = 5: & a(0^3) + b(0^2) +c(0) + d &=& 5 \\ P(1) = 13: & a(1^3) + b(1^2) + c(1) + d &=& 13 \\ P(2) = 33: & a(2^3) + b(2^2) + c(2) + d &=& 33 \\ P(3) = 71: & a(3^3) + b(3^2) + c(3) + d &=& 71 \end{array}\)


\(\displaystyle \text{And we have: }\;\begin{array}{ccc} 0 + 0 + 0 + d &=& 5 \\ a + b + c + d &=& 13 \\ 8a + 4b + 2c + d &=& 33 \\ 27a + 9b + 3c + d &=& 71 \\ 64a + 16b + 4c + d &=& 133 \end{array}\)


\(\displaystyle \text{Solve the system: }\;a = 1,\;b = 3,\;c = 4,\;d = 5\)


\(\displaystyle \text{Therefore, the polynomial is: }\;P(x) \:=\:x^3 + 3x^2 + 4x + 5\)

 

[Aladdin]

----------------------------

Fabulous work . . .

I'll puzzle my teacher with this . . .

 

[mmm4444bot]

Soroban's approach is good; continue incrementing x and asking for P(x), until you reach a row of constants at the nth degree. Of course, he realizes, too, that if Polly's polynomial were degree 46, there would be need for a lot of queries and variables.

I posted this puzzler because I was surprised to learn that, in the given scenario, one can determine any polynomial with only two queries. (Although, I suspect that you still might want access to a computer, as a function of the two answers that you get.)

Chew on that, if you like, 'til the weekend.

 

[mmm4444bot]

?
[spoiler="ONE SOLUTION":yggli0ln]Surprisingly, no matter what polynomial Polly chooses, you can find all of the coefficients
with just two queries!

Suppose you knew that all of the coefficients were at most 9. Then you could ask her the
value of P(10), and the digits of her answer would give the coefficients directly. For instance,
if she told you that P(10) were 4625, you could immediately answer that her polynomial is
4x3 + 6x2 + 2x + 5.

The same trick works whenever a bound k is known on the values of the coefficients, except
that you must work in base k+1 (or larger). The problem is that we don’t know the bound.
No matter how high a bound we guess, it might turn out that she has used a coefficient that
is larger.

To obtain a bound on the values of the coefficients, ask Polly the value of P(1); this is at
least as large as any of the coefficients.

This gives us our two-query strategy: ask her the value of P(1), then ask her the value of
P( P(1) + 1 ). From here, the digits of this number in base P(1) + 1 are the coefficients of
her polynomial.[/spoiler:yggli0ln]

List of solvers:

The following people succeeded in "surprising" Polly: Daniel Nollette, Enkhbileg Ganbat, Eric Bensley (undergrad); Jacob Lewis (graduate); Steve Wilmarth, Mike Goodman (outside).

 

[Deleted member 4993]

I think I am missing something. Say

P(x) = x[sup:23ss5d0e]3[/sup:23ss5d0e] + 3x[sup:23ss5d0e]2[/sup:23ss5d0e] + 4x + 5

The largest coefficient is 5.

P(6) = 353......????

However P(10) is 1345.

So is it then we need to look P(10) when all the coefficients are ? 9 - no matter what actually the upper bound is (? 9)?

Then I tried with:

P(x) = 11*x[sup:23ss5d0e]3[/sup:23ss5d0e] + 3x[sup:23ss5d0e]2[/sup:23ss5d0e] + 4x + 5

and

p(12) = 19493

but

p(10) = 11345

Now I am really discombobulated.....

 

[Deleted member 4993]

I think I got it:

353[sub:2pmgt9n9]10[/sub:2pmgt9n9] = 1345[sub:2pmgt9n9]6[/sub:2pmgt9n9]

19493[sub:2pmgt9n9]10[/sub:2pmgt9n9] = 11345[sub:2pmgt9n9]12[/sub:2pmgt9n9] <<< However how do you know whether it is 4 th order polynomial or 5 th order polynomial??

..

However I think for large coefficients but low degree of polynomial - Soroban's (or Euler's) method could be faster (with a computer in both the cases).

 

[mmm4444bot]

P(x) = x[sup:ypfr332a]3[/sup:ypfr332a] + 3x[sup:ypfr332a]2[/sup:ypfr332a] + 4x + 5

Query 1: P(1) = 13

P(1) + 1 = 14

Query 2: P(14) = 3393

When I ask MVR5 convert(3393, base, 14), it replies [5, 4, 3, 1].