mersenneforum.org Guess the Polynomial
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-22, 03:20 #1 Kevin     Aug 2002 Ann Arbor, MI 1B116 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 non-negative 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?
 2007-09-22, 05:33 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2×3,169 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.
 2007-09-22, 05:47 #3 Kevin     Aug 2002 Ann Arbor, MI 1101100012 Posts Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.
2007-09-22, 06:22   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11000110000102 Posts

Quote:
 Originally Posted by Kevin Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.
Chosing inputs can be done with a speadsheet and matching the outputs can be done by memorising. I've seen people do it with entire decks of cards and can recall the exact order of each card 1 hour later. However, I get the feeling I've missed the answer you are thinking of.

 2007-09-22, 14:22 #5 wblipp     "William" May 2003 New Haven 23×103 Posts Is the mathemagician allowed to design the deck, or should we interpret the problem to mean ALL polynomials with non-negative coefficients are in the deck? Last fiddled with by wblipp on 2007-09-22 at 14:27 Reason: Clarification
 2007-09-22, 15:31 #6 Zeta-Flux     May 2003 7×13×17 Posts The first number to plug into the polynomial is 1, giving the sum of the coefficients. Since the coefficients are non-negative, 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.
 2007-09-22, 15:43 #7 Zeta-Flux     May 2003 7×13×17 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 one-by-one 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...
2007-09-22, 17:22   #8
wblipp

"William"
May 2003
New Haven

23×103 Posts

Quote:
 Originally Posted by Zeta-Flux I wondered the same thing, but Kevin initially said the mathemagician says to pick *any* polynomial.
But then he said "from his deck." Since the mathemagician is presumably also a magician, I was thinking that he would know standard magician's tricks, and could secretly put the same polynomial on all the cards. But then it's not really a math puzzle, and the solutions are not unique.

Quote:
 Originally Posted by Zeta-Flux The solution I posted above should work in that case.
Clever!

 2007-09-23, 18:06 #9 Kevin     Aug 2002 Ann Arbor, MI 433 Posts Zeta-Flux 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 non-negative coefficients, and you're asking for the value at e=2.71828..., then clearly f(2)
2007-09-23, 23:37   #10
wblipp

"William"
May 2003
New Haven

23×103 Posts

Quote:
 Originally Posted by Kevin but apparently it was too misleading
I think you can patch it up with the addition of one word. The mathemagician should say "from his deck of all polynomials with non-negative integer coefficients." Adding "all" answers my question before I ask it.

Or you could just declare me too stupid to play, since obviously Zeta-flux figured it out.

William

 2007-09-24, 00:21 #11 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Pace's solution is similar to a trick we use in GMP-ECM 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

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Factoring 1 2017-01-05 17:55 ixfd64 Hardware 3 2009-03-05 13:20 10metreh Lounge 7 2008-12-29 20:34 davar55 Puzzles 11 2008-03-19 21:33 ixfd64 Factoring 4 2004-05-30 17:58

All times are UTC. The time now is 23:29.

Thu Jan 27 23:29:35 UTC 2022 up 188 days, 17:58, 2 users, load averages: 1.34, 1.37, 1.41