20070922, 03:20  #1 
Aug 2002
Ann Arbor, MI
110110001_{2} Posts 
Guess the Polynomial
Question from the University of Michigan undergrad math competition a few years ago I thought was kind of cute/clever (though not exactly in this form...). Hopefully it hasn't already been posted.
A mathemagician approaches you on on the street, and bades you to pick a polynomial, any polynomial, from his deck of polynomials with nonnegative integer coefficients, but not to show him. The mathemagician will pick a number, and you will tell him the value of the polynomial evaluated at that number. Then the mathemagician will pick a second number, and you again give him the value of the polynomial at that number. The mathemagician closes his eyes for a second in deep thought (it might a mortal person longer, but he is mathemagician), and then is able to tell you precisely what your polynomial is. How did he do it? 
20070922, 05:33  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}×5×17×19 Posts 
Each card gives a unique set of results for the two chosen values. All the mathemagician has to do is remember the pairs of results and match them the the appropriate card.

20070922, 05:47  #3 
Aug 2002
Ann Arbor, MI
433 Posts 
Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.

20070922, 06:22  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}×5×17×19 Posts 
Quote:


20070922, 14:22  #5 
"William"
May 2003
New Haven
2,371 Posts 
Is the mathemagician allowed to design the deck, or should we interpret the problem to mean ALL polynomials with nonnegative coefficients are in the deck?
Last fiddled with by wblipp on 20070922 at 14:27 Reason: Clarification 
20070922, 15:31  #6 
May 2003
60B_{16} Posts 
The first number to plug into the polynomial is 1, giving the sum of the coefficients.
Since the coefficients are nonnegative, this number will limit all of the possible choices for coefficients. Next, let r be an integer which is larger than the sum of the coefficients. This will mean that that f(r), when written in base r, gives the coefficients. 
20070922, 15:43  #7 
May 2003
1547_{10} Posts 
wblipp,
I wondered the same thing, but Kevin initially said the mathemagician says to pick *any* polynomial. The solution I posted above should work in that case. Ignoring computability issues there is a way to do it only plugging in one number, and letting the coefficients be rational. That is, if you define number as "real number" (which I don't think the original poster meant to). Just plug in e=2.71828..., and since e is transcendental over the rationals, the linear combination f(e) is uniquely determined by its value. Now, by "value" we really mean "an algorithm to give f(e) to arbitrary precision." We can count the rational polynomials (i.e. they have countable cardinality) so one could check onebyone whether that linear combination gave the same value as the algorithm you gave to the mathemagician. However, the computability issue arises in the fact that it may be impossible to prove or disprove the two algorithms give the same number. So... 
20070922, 17:22  #8  
"William"
May 2003
New Haven
2,371 Posts 
Quote:
Clever! 

20070923, 18:06  #9 
Aug 2002
Ann Arbor, MI
433 Posts 
ZetaFlux got it. The stuff about the mathemagician was just thrown in so it sounded more like a puzzle and less like a math competition problem, but apparently it was too misleading . In any case, the point of a mathemagician is that their trick is seemingly magic, but actually done with only the laws and principles of mathematics. Wouldn't have been much of a puzzle if the answer was "his deck only has one kind of card".
At least as I see it, the computability factor isn't an issue (as far as proving an answer is right). Since you have all nonnegative coefficients, and you're asking for the value at e=2.71828..., then clearly f(2)<f(e)<f(3). So take the set of all polynomials with nonnegative integer coefficients whose value at 2 is less than f(e) and whose value at 3 is bigger than f(e). This will give you a finite number of possible polynomials to work with. At this point, you keep comparing decimal places of the returned value with the value of each polynomial at e (because you can compute them to arbitrary precision). It's still a b**** to compute, but you know for sure that all of the wrong solutions will be eliminated in finite time, leaving you with one correct polynomial. 
20070923, 23:37  #10 
"William"
May 2003
New Haven
2,371 Posts 
I think you can patch it up with the addition of one word. The mathemagician should say "from his deck of all polynomials with nonnegative integer coefficients." Adding "all" answers my question before I ask it.
Or you could just declare me too stupid to play, since obviously Zetaflux figured it out. William 
20070924, 00:21  #11 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Pace's solution is similar to a trick we use in GMPECM for polynomial multiplication. To get f(x)*g(x), you can choose a large enough r (preferably a power of 2 on a binary computer), evaluate f(r) and g(r) (really just copying coefficients with some padding between them if r is a power of 2) and compute the integer product f(r)*g(r). If r was large enough, you can read the coefficients of the product polynomial from the product integer. It's a reasonably efficient way of doing polynomial products if you have very fast integer multiplication.
Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I guess this is OPNrelated  fivemack  Factoring  1  20170105 17:55 
I guess my computer is getting old...  ixfd64  Hardware  3  20090305 13:20 
Guess my IQ  10metreh  Lounge  7  20081229 20:34 
Guess a Number  davar55  Puzzles  11  20080319 21:33 
Well, I guess M404253979041338401 ain't prime!  ixfd64  Factoring  4  20040530 17:58 