1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...