mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-09-22, 03:20   #1
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default 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?
Kevin is offline   Reply With Quote
Old 2007-09-22, 05:33   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

142358 Posts
Default

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.
retina is online now   Reply With Quote
Old 2007-09-22, 05:47   #3
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Right, the question is how does he choose inputs and interpret the outputs to figure out what the polynomial is.
Kevin is offline   Reply With Quote
Old 2007-09-22, 06:22   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11000100111012 Posts
Default

Quote:
Originally Posted by Kevin View Post
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.
retina is online now   Reply With Quote
Old 2007-09-22, 14:22   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2007-09-22, 15:31   #6
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

110000010112 Posts
Default

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 is offline   Reply With Quote
Old 2007-09-22, 15:43   #7
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

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...
Zeta-Flux is offline   Reply With Quote
Old 2007-09-22, 17:22   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
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 View Post
The solution I posted above should work in that case.
Clever!
wblipp is offline   Reply With Quote
Old 2007-09-23, 18:06   #9
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

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.
Kevin is offline   Reply With Quote
Old 2007-09-23, 23:37   #10
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·103 Posts
Default

Quote:
Originally Posted by Kevin View Post
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
wblipp is offline   Reply With Quote
Old 2007-09-24, 00:21   #11
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 00:52.


Mon Nov 29 00:52:21 UTC 2021 up 128 days, 19:21, 0 users, load averages: 0.90, 1.08, 1.12

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.