## Morris: Turning Tables I took one of Peter Winkler’s puzzle books on holiday recently.  After dinner each night I intended to impress my friend with an amazing math puzzle.  I had done this before.

The book dissapeared on the flight out.  After dinner each night my friend impressed me with an amazing math puzzle.  I haven’t seen the book since.

Serves me right!

This is one of those puzzles, you will understand why I have to do it from memory.

I really like Jeff’s post  A Fun Trick – Guess the Polynomial.  You might want to look at it first.

If you relax the conditions a bit you have a similar sounding puzzle with a very different solution.

So my puzzle is this:

I am thinking of a polynomial.  All of the co-efficients are fractions.   You may use any number as your test number.  When you give me a test number I will tell you the result.

How many test numbers do you need to identify the polynomial?

1. ### czarandy said,

April 20, 2009 at 7:51 pm

[spoiler]
It seems like you need n+2, if n is the degree of the polynomial.
[/spoiler]

2. ### Stephen Morris said,

April 21, 2009 at 1:41 pm

Thanks czarandy.  I’ve spent a couple of hours thinking about your answer.   It was fun so thanks!  Also it is good material for a follow up post.

It isn’t the right answer to the question as posed.  However it looks like (but isn’t necesarrily) the right answer to a very similar question, a third variant.
I would be very interested in seeing your working if you have time to write it up.
This is what I think you missed in the problem statement:
[spoiler]Although the co-efficients are constrained to be fractions there are no constraints on the test numbers.[/spoiler]
The actual answer relies on a neat bit of theory I intend to explain in a follow up post.  It relates to: [spoiler]algebraic and trancendental numbers[/spoiler]
This is my analysis of the third variant, I will write it up properly in a follow up post.
[spoiler]If we constrain the test numbers to be integers or fractions then there is no solution.  If we knew the degree of the polynomial, n, then we could do it in n+1 test numbers. Otherwise it takes an infinite number of guesses; there is a proof by contradiction as follows:  Suppose the polynomial is p(x) and we can identify it with the test numbers t0, t1, t2, … , tm.  Now put q(x) = (x-t0)(x-t1)…(x-tm).  Clearly q(ti) will be zero for each of the test numbers.  Put r(x) = q(x) + p(x).  r(ti) = p(ti) for each of the test numbers so we cannot distinguish between r(x) and p(x).  Therefore we have a proof by contradiction.[/spoiler]

I’ve just edited this because I’ve realised I’ve missed a case: [spoiler]what if the test numbers can only be algebraic numbers (E.g. 3, 47/236, sqrt(59) but not pi or e)? My proof by contradiction doesn’t work. Is the answer n+2? I need more time to think about it! Would love to see your working![/spoiler]

Thanks czarandy, that was fun!