Do you believe I'm psychic?
I am thinking of a polynomial, f ( x ) with non-negative integer coefficients. You can ask me the value of the polynomial at any positive integer value of x and I will tell you honestly. Then you can do this over and over again. What is the minimum number of questions you need to ask to exactly determine what my polynomial is?
Adapted from a forum post.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Moderator note:
Of course, for completeness, you should mention why it can't be done with just 1 value. It may be obvious, but you should still state why.
I would argue that the answer is 1. If we are told that f ( π ) = 3 π 2 + 2 π + 1 , then we know for certain that f ( x ) = 3 x 2 + 2 x + 1 , because it has integer coefficients and π is transcendental. Where's the flaw in my argument?
Log in to reply
I've heard of this problem before, and I am fairly sure you are only allowed to plug in (positive) integers.
Log in to reply
Right, I've heard of the version of positive integers too. Unfortunately, that's not what this problem states.
Of course, if we don't restrict plugging in positive integers, then we can allow the coefficients to be possibly negative integers.
Log in to reply
@Calvin Lin – Added "can only ask positive integers". Thanks!
What if you're not given the.closed form?
Log in to reply
I'm a mathematician. Of course it is in exact mathematical form. None of this approximate real number estimation crap.
Log in to reply
@Calvin Lin – I AGREE WITH YOU.
Log in to reply
@A Former Brilliant Member – The problem has since been changed, and the specific condition is that "You can ask me the value of the polynomial at any positive integer value of x ".
My comment was relevant to the old version, where we could substitute "any real value of x ", thereby allowing me to use π .
@Calvin Lin – I am a god from Olympus. Here is what I do to give out numbers to people: I have got an infinite ruler which I call the number line. I have also a linear measure on that ruler. Integer points such as 1, 2, 3, are marked on the ruler. Because I am a god, I have the power to mark the exact value of f(x) on the ruler with my divine marker that creates an infinitesimally small mark on the ruler. After, I do this, I hand this back to you. This is my way of giving output to mathematicians.
When you give me pi, I can accept it, because I know what pi is. Even I can pin point pi on my ruler (although, you can't). Let's say, I do pin point my value of f(pi) on the ruler, then this is exact. But being a mathematician, what do you do?
Log in to reply
@Agnishom Chattopadhyay – Whether you be a God from Olympus or a mere mortal of flesh and bones, you can never pin point the location of irrationals on the real number line. Dedekind Cuts are the way irrationals are on the real number line. Your way of "giving out numbers to people on an infinite ruler with a divine marker" unfortunately doesn't work for irrationals.
@Agnishom Chattopadhyay – "When you give me pi, I can accept it, because I know what pi is"
What makes you think that "I" will accept? it is still an impossible task to do for transcendental numbers. "I" was instructed to do an impossible task.
Log in to reply
@Pi Han Goh – Which is the impossible task?
Log in to reply
@Agnishom Chattopadhyay – You can't "construct" a transcendental number.
Log in to reply
@Pi Han Goh – Only if I am limited to a straight edge and a compass
Nice. Thought of it the same way.
Ask for x = 1 , then I will give you the value of f ( 1 ) which is the sum of the coefficients of the polynomial. And since they are all non-negative, you can bound on the largest coefficient.
Next, pick a power of 10 that is larger than f ( 1 ) , say 1 0 n for some integer n .
Ask me the value of f ( 1 0 n ) , with this, you can just read off the coefficients by breaking the numbers apart from every n th digit.