ganeshie8
  • ganeshie8
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.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
amilapsn
  • 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
  • ganeshie8
That is a pretty straightforward method and a nice try :)
ganeshie8
  • 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
  • amilapsn
Is it a riddle? :/
ganeshie8
  • ganeshie8
Haha not a riddle, it is a regular math problem..
amilapsn
  • amilapsn
Am I mistaken the problem?
ganeshie8
  • ganeshie8
In your method, you're not using "all" the given information
ganeshie8
  • ganeshie8
It is given that the coefficients of the polynomial are "positive integers" you haven't used that info anywhere
amilapsn
  • amilapsn
I thought it won't matter.
amilapsn
  • amilapsn
It don't matter whether \(a_i\)s are positive integers or not.
Lurker
  • Lurker
would it be n questions?
Lurker
  • Lurker
wait 2 questions really for alll n?
Lurker
  • Lurker
even for an infinite polynomial
ganeshie8
  • ganeshie8
Yes
ganeshie8
  • ganeshie8
For an analogy, consider the following quick example
Lurker
  • Lurker
|dw:1450077666177:dw|
Lurker
  • Lurker
|dw:1450077719610:dw|
Lurker
  • Lurker
uh wait lemme see
ganeshie8
  • 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
  • ganeshie8
that is a small hint :)
Lurker
  • Lurker
okay yes
Lurker
  • Lurker
oh i see
Lurker
  • Lurker
now its polynomial base
Lurker
  • Lurker
all infinite power series is just another way to write some base expansion now with n1 and n2 as the base
ganeshie8
  • ganeshie8
something in that lines yeah
ganeshie8
  • ganeshie8
still need to devise the two questions and the method which determines the polynomial
Lurker
  • 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.
  • 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
  • ganeshie8
this question was posted by @Nishant_Garg
ganeshie8
  • ganeshie8
it is from madavacompetition held on yesterday
anonymous
  • anonymous
Hahaha, nice to see you guys are still going at it, this is totally out my league :P
ganeshie8
  • ganeshie8
lunch... brb
Lurker
  • Lurker
http://prntscr.com/9dxyib
ganeshie8
  • ganeshie8
lunch isn't ready yet
Lurker
  • Lurker
wait no ignore that xD lemme think again
ganeshie8
  • ganeshie8
we cannot choose the base freely
Lurker
  • Lurker
the base is the n itself right
Lurker
  • Lurker
we can pick any n we want
Lurker
  • Lurker
okay u gotta go backwards
ganeshie8
  • 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
  • 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
  • Lurker
a0,a1,a2,a3 are your coefficients
Lurker
  • Lurker
just backwards
ganeshie8
  • 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
  • ganeshie8
yeah once you have the "base" and the "number", the coefficients are determined uniquely
Lurker
  • Lurker
right
ganeshie8
  • ganeshie8
but we need to choose our base such that all the coefficients are less than the base
ganeshie8
  • ganeshie8
that is tricky because we don't the coefficients
Lurker
  • 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
  • Lurker
we know that all improper coefficents can be turned into proper base reps
Lurker
  • Lurker
but can we recover them back hmm
ganeshie8
  • 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
  • ganeshie8
"we know that all improper coefficents can be turned into proper base reps" there is no guarantee you get an unique representation
ganeshie8
  • ganeshie8
unique representation is guaranteed only when the base is greater than all the coefficients
Lurker
  • Lurker
ok phew integer coefficients
Lurker
  • 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
  • ganeshie8
that might work ! what are your two questions again ?
Lurker
  • 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
  • Lurker
i think we shud just try to work a smaller problem out
Lurker
  • Lurker
try to solve the real coeff after writing this in base 2 and 3
ganeshie8
  • ganeshie8
yeah
ganeshie8
  • ganeshie8
say our secret polynomial is \[p(x)=x^3+2x + 9\]
ganeshie8
  • ganeshie8
what will be the two questions ?
Lurker
  • 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
  • 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
  • Lurker
ye that is true parth however we are trying to sort the case out where the coeff is greater than the base
ParthKohli
  • 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
  • ganeshie8
it seems "coefficient greater than the base" case never arises with PK's method above...
Lurker
  • Lurker
oh i thought we gotta just do it for any random n
Lurker
  • Lurker
ah i see what u mean
Lurker
  • Lurker
thats nice
ganeshie8
  • 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
  • Lurker
p(1) = sum of coeffecients and then we just pick a base greater than the sum
Lurker
  • Lurker
pretty neat idea i didnt think of it xD
ganeshie8
  • ganeshie8
|dw:1450080868860:dw|
Lurker
  • Lurker
but u cheateeeeeeeerr u got to pick whatever base u wanted :)
Lurker
  • Lurker
its cut off
ParthKohli
  • ParthKohli
in a magic trick, we are in charge.
ganeshie8
  • ganeshie8
existence part looks easy to prove using euclid division algorithm but the uniqueness part is a bit tricky
ganeshie8
  • ganeshie8
http://i.stack.imgur.com/HW98T.png
Lurker
  • 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
  • ganeshie8
me too
Lurker
  • Lurker
or atleast prove thats its simple not possible
Lurker
  • Lurker
i think we are better off showing its not possible
thomas5267
  • 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
  • ganeshie8
since the coefficients are all positive, any cofficient cannot be greater than \(f(1)\)
ganeshie8
  • ganeshie8
therefore we can use "f(1) + 1" as a base
ganeshie8
  • 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
  • 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
  • thomas5267
Curiously it also works with f(103) in base 103 just as ParthKohli suggested.
ganeshie8
  • 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
  • thomas5267
I realised why it works... I should think before posting lol
ganeshie8
  • ganeshie8
that is due to the theorem http://i.stack.imgur.com/HW98T.png
thomas5267
  • thomas5267
For the simple reason that, \(a104^2+b104+c\) in base 104 is \(abc_{104}\)
ganeshie8
  • ganeshie8
uniqueness part is a bit tricky though
thomas5267
  • thomas5267
Don't fret, don't sweat! ProofWiki is coming to settle the mess! https://proofwiki.org/wiki/Basis_Representation_Theorem
ganeshie8
  • 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
  • amilapsn
I got the point. It's brilliant!

Looking for something else?

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