Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Polynomial riddle

  1. Jun 8, 2014 #1
    Hi guys,

    My boss gave me a riddle.
    He says that you have a "black box" with a polynomial inside it like f(x)=a0+a1x+a2x^2+a3x^3 ....
    you don't know the rank of it or the coefficients a0, a1, a2 ....
    You do know:
    all of the coefficients are positive
    you get to input two x numbers and their f(x) value


    How can you find all of the coefficients a0,a1,a2 .... and the rank?

    Thanks !
     
  2. jcsd
  3. Jun 8, 2014 #2

    hilbert2

    User Avatar
    Science Advisor
    Gold Member

    Knowing f(x) for two values of x is not enough to determine the coefficients if the polynomial is of higher than first order.
     
  4. Jun 8, 2014 #3
    It can be done if you know the polynomial has nonnegative integer coefficients, and if the second input is allowed to depend on the first output.

    Put in ##1##. The output gives you the sum ##s## of the coefficients.
    - If ##s=0##, you know ##f=0##.
    - If ##s>0##, put in any integer ##k>s##. Then there is a unique integer solution, which is especially easy to read off if you express the output in base-##k##.
     
  5. Jun 8, 2014 #4
    Hi economicsnerd,

    Couldn't follow "put in any integer k>s. Then there is a unique integer solution, which is especially easy to read off if you express the output in base-k."
    Could you give me an example? lets say f(x)=5+2x+4x^2 is in the 'black box'.
    i put in x=1 and receive f(x)=s=a0+a1+a2=11 > 0 so i put in x=k=15 and get f(x)=a0+15a1+900a2=935
    organize:
    1. a0+a1+a2=11 2. a0+15a1+900a2=935
    2 equations with 3 unknowns.

    Whats the rational behind putting a k > s, and how can i find all coefficients with just 2 equations ?
     
  6. Jun 8, 2014 #5
    Okay. So you know ##f(1)=11## and ##f(15)=935##.
    - First note that ##15^3 > 935##, so that the polynomial can't be of degree ##>2##. That is, ##f(x)=a_0 + a_1 x + a_2 x^2## for some ##a_0,a_1, a_2\in\mathbb Z_+##.
    - Next, note that ##a_0,a_1\in\mathbb Z_+## with ##a_0+ a_1 \leq 11 < 15##, so that ##a_0 + a_1(15)<15^2##. This means that ##935 - 15^2< a_2 (15)^2 \leq 935##. It's easy to check that there's a unique integer ##a_2## that accomplishes this, namely ##a_2 = 4##.
    - Substituting the solution for ##a_2## in, we now know that: ##a_0+a_1 < 15## and ##a_0 + a_1 (15) = 15 35##. [Of course, you have two equations and two unknowns now, but we don't actually need to know that ##a_0 + a_1 =7##, because knowing they're integers gives us enough information.] Now we can do the same trick again. ##35 - 15< a_1 (15) \leq 35##, which pins down ##a_1=2##.
    - Then substitution yields ##a_0 = 5##.

    We can always work backward in this way.

    To get some better intuition for why, consider the following question:
    Say I tell you I have a polynomial ##g## such that every coefficient of ##g## is a nonnegative integer ##<10##. If I tell you ##g(10)##, will you then be able to tell me what ##g## is?

    For example:
    - If ##g(10)=5021##, then do we know ##g(x) = 5x^3 + 2x + 1##?
    - If ##g(10)=60007##, then do we know ##g(x) = 6x^4 + 7##?

    Nothing is magical about ##10## that makes this trick work. It's just that we usually express numbers in a way (base-10) that makes it easy to answer this question. All the first question is needed for is to find a ##k## such that we can be sure that every coefficient of the polynomial is a nonnegative integer ##<k##.
     
  7. Jun 8, 2014 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    The rationale behind using asking for f(k) where k>f(1) is because otherwise the magic might not work. Suppose the function in the black box is f(x)=5+2x+4x2. The black box cranks out 11 as a response to f(1). Suppose I use 4 next. The black box churns out f(4)=77, which is 1031 when expressed base 4. That suggests the polynomial is 1+3x+5x3, which is wrong.

    To see what's going on, here are f(k) from k=2 to 16, expressed in base 10 and in base k:
    Code (Text):

     k f(k)  base k  Polynomial
     2   25   11001  1+x^3+x^4
     3   47    1202  2+x^2+x^3
     4   77    1031  1+3x+x^3
     5  115     430  3x+4x^2
     6  161     425  5+2x+4x^2
     7  215     425  5+2x+4x^2
     8  277     425  5+2x+4x^2
     9  347     425  5+2x+4x^2
    10  425     425  5+2x+4x^2
    11  511     425  5+2x+4x^2
    12  605     425  5+2x+4x^2
    13  707     425  5+2x+4x^2
    14  817     425  5+2x+4x^2
    15  935     425  5+2x+4x^2
    16 1061     425  5+2x+4x^2
    Can you see the pattern? It appears that f(k) when expressed in base k is 425 for all k>5. This is indeed the case. You might want to try proving it.

    Note that in this case reading off the polynomial from the base-k representation of f(k) works for all k>5. That's because the largest coefficient is five. Using k=f(1)+1 (or higher) ensures that k is larger than the largest possible coefficient.

    Suppose the black box function was instead f(x)=11x3. Once again you'll get f(1)=11, but now the base k representation of f(k) keeps changing until you reach k=12, at which point it becomes b00 ('b' means 11) and stays that way for all k>11. The black box knows what the largest coefficient is. You don't, but you do know that it cannot be larger than 11.
     
    Last edited: Jun 8, 2014
  8. Jun 9, 2014 #7
    Thank you all :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Polynomial riddle
  1. Simple riddle (Replies: 9)

  2. A simple riddle. (Replies: 5)

  3. Simple riddle! (Replies: 5)

  4. Math Riddle Help! (Replies: 3)

  5. Dot Product Riddle (Replies: 7)

Loading...