Let p(x) be a polynomial with positive integers conefficients. You can ask the question: What is p(n) for any positive integer n? What is the minimum number of questions to be asked to determine p(x) completely?Justify.

- ganeshie8

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- amilapsn

For people who know about simultaneous equations:
Let \(p(x)=\sum_{i=0}^n {a_ix^i}\)
Then we have to know n+1 unknown constants, \(a_0,\ldots,a_n\).
So we need to solve n+1 equations.
\(\therefore\) we need to ask n+1 questions.
But there's a problem. We don't know the degree of the polynomial.
So the answer is there's no way of determining p(x) completely.

- ganeshie8

That is a pretty straightforward method and a nice try :)

- ganeshie8

But the correct answer is "two questions"

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- amilapsn

Is it a riddle? :/

- ganeshie8

Haha not a riddle, it is a regular math problem..

- amilapsn

Am I mistaken the problem?

- ganeshie8

In your method, you're not using "all" the given information

- ganeshie8

It is given that the coefficients of the polynomial are "positive integers"
you haven't used that info anywhere

- amilapsn

I thought it won't matter.

- amilapsn

It don't matter whether \(a_i\)s are positive integers or not.

- Lurker

would it be n questions?

- Lurker

wait 2 questions really for alll n?

- Lurker

even for an infinite polynomial

- ganeshie8

Yes

- ganeshie8

For an analogy, consider the following quick example

- Lurker

|dw:1450077666177:dw|

- Lurker

|dw:1450077719610:dw|

- Lurker

uh wait lemme see

- ganeshie8

Consider the number \(2^{10}\) in base \(16\)
Suppose its representation in base \(16\) is \((A_n\ldots A_0)_{16}\)
Would you agree that all the numbers \(A_n,\ldots,A_0\) are uniquely determined by just two quantities :
1) base \(16\)
2) number value \(2^{10}\)
?

- ganeshie8

that is a small hint :)

- Lurker

okay yes

- Lurker

oh i see

- Lurker

now its polynomial base

- Lurker

all infinite power series is just another way to write some base expansion now with n1 and n2 as the base

- ganeshie8

something in that lines yeah

- ganeshie8

still need to devise the two questions and the method which determines the polynomial

- Lurker

okay ya now u gotta figure out how to atually solve for these coeffcients given u now the base and the representations in 2 differnet bases

- bubblegum.

yeah the answer is 2! i saw a similar ques on this website->
http://technothlon.techniche.org in a quiz called technopedia
they'll start after few months again
but in that ques we were given that the polynomial is of degree 10

- ganeshie8

this question was posted by @Nishant_Garg

- ganeshie8

it is from madavacompetition held on yesterday

- anonymous

Hahaha, nice to see you guys are still going at it, this is totally out my league :P

- ganeshie8

lunch... brb

- Lurker

http://prntscr.com/9dxyib

- ganeshie8

lunch isn't ready yet

- Lurker

wait no ignore that xD lemme think again

- ganeshie8

we cannot choose the base freely

- Lurker

the base is the n itself right

- Lurker

we can pick any n we want

- Lurker

okay u gotta go backwards

- ganeshie8

If \( \sum\limits_{i=0}^{\infty} a_i b^i \) is the representaion of \(N\) in base \(b\), the coefficients \(a_i\) must all all be less than \(b\) :
\[0\le a_i\lt b\]

- Lurker

like for 200 lets say
if we want to rewrite in base 2
u have ot take 128 first
((200 - 128) - 2^a1)-2^a^2.... = 0

- Lurker

a0,a1,a2,a3 are your coefficients

- Lurker

just backwards

- ganeshie8

200 = 2*100 + 0
100 = 2*50 + 0
50 = 2*25 + 0
25 = 2*12 + 1
12 = 2*6 + 0
6 = 2*3 + 0
3 = 2*1 + 1
1 = 2*0 + 1
\((200)_{10} = (11001000)_{2}\)

- ganeshie8

yeah once you have the "base" and the "number", the coefficients are determined uniquely

- Lurker

right

- ganeshie8

but we need to choose our base such that all the coefficients are less than the base

- ganeshie8

that is tricky because we don't the coefficients

- Lurker

hmmmmmm okay maybe we can work around this like okay so basically this is kinda what we are saying right
1+10*10 + 100 =201 <---- improper
1+0*10+2*100 = 201 <--- proper base rep

- Lurker

we know that all improper coefficents can be turned into proper base reps

- Lurker

but can we recover them back hmm

- ganeshie8

exactly!
below is not a proper expansion :
\(200 = 25*2^2 + 50*2^1 + 0*2^0\)
because the base 2 is not greater than all the coefficients

- ganeshie8

"we know that all improper coefficents can be turned into proper base reps"
there is no guarantee you get an unique representation

- ganeshie8

unique representation is guaranteed only when the base is greater than all the coefficients

- Lurker

ok phew integer coefficients

- Lurker

okay lets see for integer coeff
1+(a+k)x+(b+k2)x^2+(c+k3)x^3... suppose we got something like this a b c are less than x and k ,k2 ,k3 is ammount the coeff is greater by
since its an integer there must be a way to rewrite this as a proper base number
becase all integers are represented in all bases

- ganeshie8

that might work !
what are your two questions again ?

- Lurker

i dont know yet because okay say we encounter higher coeff for both of the bases choses in the manner shown before, we take the ggreater coeffecs break it out, and feel the higher numbers upto the higher powers on base and this way u saturate until its a proper representation, now im thinkin since now there is an actual constrain on how the greater part for the coefficient is places is there a way to recover the actual coefficients from the proper representations

- Lurker

i think we shud just try to work a smaller problem out

- Lurker

try to solve the real coeff after writing this in base 2 and 3

- ganeshie8

yeah

- ganeshie8

say our secret polynomial is
\[p(x)=x^3+2x + 9\]

- ganeshie8

what will be the two questions ?

- Lurker

20*1+10*2^1+5*2^2 = 60 = (111100)_2, 2020_3
20*1+10*3^1+5*3^2= 95 = (10112)_3 , 1011111_2

- ParthKohli

What is \(p(1)\)?
Ans: 12
What is \(p(13)\)?
Ans: 2232
2232 in base 13 is 1029 - the coefficients written in order.
You can also ask for \(p(14)\) or \(p(15)\) and so on. Just that the number should be greater than \(f(1)\). I'll post the reasoning.

- Lurker

ye that is true parth however we are trying to sort the case out where the coeff is greater than the base

- ParthKohli

Yes, but we are CHOOSING the base :)
The reason we ask for p(1) is to place a restriction on the base, right? Because no coefficient can be greater than p(1).

- ganeshie8

it seems "coefficient greater than the base" case never arises with PK's method above...

- Lurker

oh i thought we gotta just do it for any random n

- Lurker

ah i see what u mean

- Lurker

thats nice

- ganeshie8

analysing it for any random \(n\) looks complicated but is very interesting...
part of my reason in encouraging you with that method earlier is to side track you :)

- Lurker

p(1) = sum of coeffecients and then we just pick a base greater than the sum

- Lurker

pretty neat idea i didnt think of it xD

- ganeshie8

|dw:1450080868860:dw|

- Lurker

but u cheateeeeeeeerr u got to pick whatever base u wanted :)

- Lurker

its cut off

- ParthKohli

in a magic trick, we are in charge.

- ganeshie8

existence part looks easy to prove using euclid division algorithm
but the uniqueness part is a bit tricky

- ganeshie8

http://i.stack.imgur.com/HW98T.png

- Lurker

we shud still try to work this out im kind of curious how we can recover a poylnomial after its rewritten as this new power series

- ganeshie8

me too

- Lurker

or atleast prove thats its simple not possible

- Lurker

i think we are better off showing its not possible

- thomas5267

I still don't understand why two points would be sufficient. Consider the following polynomial. \[
\begin{align*}
f(x)&=x^2+100\\
g(x)&=3x+98\\
f(1)&=g(1)=101\\
f(2)&=g(2)=104
\end{align*}\]Either this is not the two points to ask, or two points don't work.
Furthermore, if the polynomial is of the form \(ax^2+b\) with a large enough \(b\), you can always do a linear fit with positive coefficients. How can two points be sufficient given that there are no constraints on maximum value of coefficients?

- ganeshie8

since the coefficients are all positive, any cofficient cannot be greater than \(f(1)\)

- ganeshie8

therefore we can use "f(1) + 1" as a base

- ganeshie8

f( f(1) + 1 ) can be expressed uniquely in base "f(1) + 1"
the coefficients of this expansion give the coefficients of the required polynomial

- ganeshie8

\(\begin{align*}
f(x)&=x^2+100\\
g(x)&=3x+98\\
\end{align*}
\)
for f(x) we ask below questions :
1) what is f(1) ?
101
2) what is f(102) ?
10504
Notice that \(10504 = \color{red}{1}*102^2 + \color{red}{0}*102^1+\color{red}{100}*102^0\)

- thomas5267

Curiously it also works with f(103) in base 103 just as ParthKohli suggested.

- ganeshie8

yeah base just needs to be greater than any of the coefficients
so any number greater than f(1) will work just fine

- thomas5267

I realised why it works... I should think before posting lol

- ganeshie8

that is due to the theorem
http://i.stack.imgur.com/HW98T.png

- thomas5267

For the simple reason that, \(a104^2+b104+c\) in base 104 is \(abc_{104}\)

- ganeshie8

uniqueness part is a bit tricky though

- thomas5267

Don't fret, don't sweat! ProofWiki is coming to settle the mess!
https://proofwiki.org/wiki/Basis_Representation_Theorem

- ganeshie8

If \(0\le p_i,q_i\lt b\) and \(\sum\limits_{i=0}^{\infty}p_ib^i = \sum\limits_{i=0}^{\infty}q_ib^i \),
then \(p_i=q_i\) for each \(i\)

- amilapsn

I got the point. It's brilliant!

Looking for something else?

Not the answer you are looking for? Search for more explanations.