The discussion centers on solving a polynomial riddle involving a "black box" function f(x) = a0 + a1x + a2x^2 + a3x^3, where the coefficients are positive integers. Participants explain that knowing f(x) for two values of x is insufficient to determine the coefficients unless the second input is greater than the sum of the coefficients. The method involves inputting a value k greater than the sum of coefficients to derive unique integer solutions for the coefficients, which can be easily read in base-k representation. An example with f(x) = 5 + 2x + 4x^2 illustrates the process of determining coefficients through strategic inputs.
PREREQUISITES
Understanding of polynomial functions and their coefficients
Familiarity with base-k number representation
Knowledge of integer solutions in algebra
Basic problem-solving skills in mathematical contexts
NEXT STEPS
Study polynomial interpolation techniques for coefficient determination
Learn about base conversions and their applications in number theory
Explore integer programming methods for solving equations with multiple unknowns
Investigate the properties of positive integer coefficients in polynomials
USEFUL FOR
Mathematicians, computer scientists, data analysts, and anyone interested in polynomial equations and their applications in computational problem-solving.
#1
dislect
163
0
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?
Knowing f(x) for two values of x is not enough to determine the coefficients if the polynomial is of higher than first order.
#3
economicsnerd
268
24
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##.
#4
dislect
163
0
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? let's 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 ?
#5
economicsnerd
268
24
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##.
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? let's say f(x)=5+2x+4x^2 is in the 'black box'.
Whats the rational behind putting a k > s, and how can i find all coefficients with just 2 equations ?
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:
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.