Guess the Polynomial

Kevin · 2007-09-22, 03:20

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?

retina · 2007-09-22, 05:33

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.

Kevin · 2007-09-22, 05:47

Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.

retina · 2007-09-22, 06:22

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.

wblipp · 2007-09-22, 14:22

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?

Zeta-Flux · 2007-09-22, 15:31

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.

Zeta-Flux · 2007-09-22, 15:43

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...

wblipp · 2007-09-22, 17:22

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!

Kevin · 2007-09-23, 18:06

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)<f(e)<f(3). So take the set of all polynomials with non-negative 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.

wblipp · 2007-09-23, 23:37

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

akruppa · 2007-09-24, 00:21

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

2007-09-22, 03:20	#1
Kevin Aug 2002 Ann Arbor, MI 433 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, 14:22	#5
wblipp "William" May 2003 Near Grandkid 2·1,187 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I guess this is OPN-related	fivemack	Factoring	1	2017-01-05 17:55
I guess my computer is getting old...	ixfd64	Hardware	3	2009-03-05 13:20
Guess my IQ	10metreh	Lounge	7	2008-12-29 20:34
Guess a Number	davar55	Puzzles	11	2008-03-19 21:33
Well, I guess M404253979041338401 ain't prime!	ixfd64	Factoring	4	2004-05-30 17:58

2007-09-22, 05:33	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 6685₁₀ 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 433 Posts	Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.

2007-09-22, 15:31	#6
Zeta-Flux May 2003 3013₈ 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-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)<f(e)<f(3). So take the set of all polynomials with non-negative 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.

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