Morris: Turning Tables

tt23I 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?

2 Comments »

  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!

RSS feed for comments on this post · TrackBack URL

Leave a Comment

You must be logged in to post a comment.

The Math Factor Podcast Website


Quality Math Talk Since 2004, on the web and on KUAF 91.3 FM


A production of the University of Arkansas, Fayetteville, Ark USA


Download a great math factor poster to print and share!

Got an idea? Want to do a guest post? Tell us about it!

Heya! Do us a favor and link here from your site!