Math brain teaser
12-27-2013, 05:18 AM
Post: #1
 Han Senior Member Posts: 1,882 Joined: Dec 2013
Math brain teaser
This was a cute problem that was sent my way a long time ago. It took me a while to come up with the answer, but very cool once you figure it out.

A computer generates a random polynomial whose coefficients are non-negative integers. You are allowed to ask the computer to evaluate the polynomial at two values. What two values do you choose in order to completely determine the coefficients?

Graph 3D | QPI | SolveSys
12-27-2013, 05:54 AM (This post was last modified: 12-27-2013 05:54 AM by Les_Koller.)
Post: #2
 Les_Koller Junior Member Posts: 22 Joined: Dec 2013
RE: Math brain teaser
Just read this gem on the National Council of Teacher's of Mathematics web page for the first time last night! (I teach High School Algebra). Thought I'd set it aside till tomorrow, very interesting problem. Now that I see it mentioned here, you've got me intrigued, and I'm pulling out pencil and paper. Hope I can report success soon!
12-27-2013, 07:41 AM
Post: #3
 Les_Koller Junior Member Posts: 22 Joined: Dec 2013
RE: Math brain teaser
OK, I think I actually have a couple of answers that are correct. I'll wait til others post to see if someone gets both of mine.

I'm a math teacher. Of course I have problems.
12-27-2013, 01:24 PM (This post was last modified: 12-27-2013 02:33 PM by Namir.)
Post: #4
 Namir Senior Member Posts: 1,100 Joined: Dec 2013
RE: Math brain teaser
We evaluate the polynomial at m1=P(1) and m2=P(m1+1). The value m1 gives us the sum of the polynomial coefficients. We use that value to breakdown the value of m2 into the polynomial coefficients using integer divisions and modulo operators (or equivalent operations). Here is a pseudo code for the solution:

Code:
m1=P(1) m2=P(m1+1) N=INT(log(m2)/log(m1)) Dim A(0 to N) For I = N to 0 Step -1   K = (m1+1)^I   A(I) = INT(m2/K)   m2 = m2 - A(I)*K Next

P(x) is the polynomial with the given positive integer coefficients evaluated at X. The array A() contains the calculated polynomial coefficients, such that:

P(X,A) = A(0) + A(1)*X + A(2)*X^2 + ... + A(N)*X^N
12-27-2013, 05:29 PM (This post was last modified: 12-27-2013 05:32 PM by Han.)
Post: #5
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: Math brain teaser
(12-27-2013 01:24 PM)Namir Wrote:  We evaluate the polynomial at m1=P(1) and m2=P(m1+1). The value m1 gives us the sum of the polynomial coefficients. We use that value to breakdown the value of m2 into the polynomial coefficients using integer divisions and modulo operators (or equivalent operations). Here is a pseudo code for the solution:

Code:
m1=P(1) m2=P(m1+1) N=INT(log(m2)/log(m1)) Dim A(0 to N) For I = N to 0 Step -1   K = (m1+1)^I   A(I) = INT(m2/K)   m2 = m2 - A(I)*K Next

P(x) is the polynomial with the given positive integer coefficients evaluated at X. The array A() contains the calculated polynomial coefficients, such that:

P(X,A) = A(0) + A(1)*X + A(2)*X^2 + ... + A(N)*X^N

Hi Namir,

That's an interesting approach! Allow me to make the brain teaser a bit more interesting. Let's suppose now the the computer is a gatekeeper. Due to a time-space anomaly, you have been thrown into the far, far future and are trying to find your way back to your current timeline. The only way to do so is to determine all the coefficients of the polynomial. The computer has a display that is capable of displaying infinite precision integers (and you can see all digits at once), and a keypad with which you may enter your values for evaluation. The catch, however, is that you have no pen, no paper, no calculator (basically nothing with which you may do any sort of calculations except for your own mind) and only a few minutes to answer the riddle to return back to your time, or forever be stuck! Can you devise a new scheme to solve the riddle and get back home?

Graph 3D | QPI | SolveSys
12-27-2013, 05:56 PM
Post: #6
 Thomas Klemm Senior Member Posts: 2,161 Joined: Dec 2013
RE: Math brain teaser
(12-27-2013 05:29 PM)Han Wrote:  Can you devise a new scheme to solve the riddle and get back home?

m1 = P(1)
m2 = P(10^k) where k is the number of digits of m1
12-27-2013, 06:13 PM
Post: #7
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: Math brain teaser
(12-27-2013 05:56 PM)Thomas Klemm Wrote:
(12-27-2013 05:29 PM)Han Wrote:  Can you devise a new scheme to solve the riddle and get back home?

m1 = P(1)
m2 = P(10^k) where k is the number of digits of m1

Nicely done!

Graph 3D | QPI | SolveSys
12-27-2013, 10:02 PM
Post: #8
 Namir Senior Member Posts: 1,100 Joined: Dec 2013
RE: Math brain teaser
Good alternate solution!!!

Namir
12-27-2013, 10:52 PM
Post: #9
 Paul Dale Senior Member Posts: 1,840 Joined: Dec 2013
RE: Math brain teaser
They are essentially the same solution, just using a different base. The first is extracting the digits base m1+1, the second base k. The second is easier for a human to read of course.

- Pauli
12-27-2013, 11:00 PM
Post: #10
 Han Senior Member Posts: 1,882 Joined: Dec 2013
RE: Math brain teaser
When I first saw this problem, I came up with the same solution as Thomas. It didn't even occur to me to think about other solutions (or even other bases).

Graph 3D | QPI | SolveSys
12-28-2013, 02:03 AM
Post: #11
 Les_Koller Junior Member Posts: 22 Joined: Dec 2013
RE: Math brain teaser
I ask for p(a), then p(p(a)). Alternatively, ask for p(pi). IF the computer absolutely HAS to deliver exact answers, you will get your answer quickly. For instance, if P = 13x^4 + 10x^2 + x + 8, you get 13 pi^4 + 10 pi^2 + pi + 8.

I'm a math teacher. Of course I have problems.
12-28-2013, 02:45 AM
Post: #12
 Paul Dale Senior Member Posts: 1,840 Joined: Dec 2013
RE: Math brain teaser
p(a) and p(p(a)) doesn't quite work. Take a polynomial where p(a) = a. The second evaluation produces no new information and you cannot distinguish between p(x) = x and p(x) = a.

- Pauli
12-28-2013, 04:31 AM
Post: #13
 walter b On Vacation Posts: 1,957 Joined: Dec 2013
RE: Math brain teaser
(12-28-2013 02:03 AM)Les_Koller Wrote:  I ask for p(a), then p(p(a)). Alternatively, ask for p(pi). IF the computer absolutely HAS to deliver exact answers, you will get your answer quickly. For instance, if P = 13x^4 + 10x^2 + x + 8, you get 13 pi^4 + 10 pi^2 + pi + 8.
(12-28-2013 02:45 AM)Paul Dale Wrote:  p(a) and p(p(a)) doesn't quite work. Take a polynomial where p(a) = a. The second evaluation produces no new information and you cannot distinguish between p(x) = x and p(x) = a.
Let me modify Les' solution a bit: I'd ask for p(pi) and p(e). So I'd get two answers allowing me to exclude the case Pauli mentioned. Thanks, Les, for the basic idea!

d:-)
12-28-2013, 11:11 AM
Post: #14
 Thomas Klemm Senior Member Posts: 2,161 Joined: Dec 2013
RE: Math brain teaser
(12-28-2013 04:31 AM)walter b Wrote:  I'd ask for p(pi) and p(e).
You're dead before entering all the digits of $$\pi$$.

Have a nice time in the future ...
12-28-2013, 11:20 AM
Post: #15
 Thomas Klemm Senior Member Posts: 2,161 Joined: Dec 2013
RE: Math brain teaser
(12-27-2013 10:52 PM)Paul Dale Wrote:  the second base k
It's $$10^k$$.
12-28-2013, 11:58 AM
Post: #16
 Paul Dale Senior Member Posts: 1,840 Joined: Dec 2013
RE: Math brain teaser
Sorry, it is $$10^k$$.

- Pauli
12-28-2013, 12:17 PM
Post: #17
 walter b On Vacation Posts: 1,957 Joined: Dec 2013
RE: Math brain teaser
(12-28-2013 11:11 AM)Thomas Klemm Wrote:  You're dead before entering all the digits of $$\pi$$.

Have a nice time in the future ...
Thanks for the good wishes, although I'd just enter $$\pi$$ with two keystrokes

d:-)
12-28-2013, 12:55 PM
Post: #18
 Thomas Klemm Senior Member Posts: 2,161 Joined: Dec 2013
RE: Math brain teaser
(12-28-2013 12:17 PM)walter b Wrote:  I'd just enter $$\pi$$ with two keystrokes
You should know better that they are always cheating with this key:
they write $$\pi$$ on it but all you get is a rational approximation.
12-28-2013, 09:21 PM
Post: #19
 Les_Koller Junior Member Posts: 22 Joined: Dec 2013
RE: Math brain teaser
Seriously? You don't have to (in fact CANNOT) use all the digits of pi. If the computer is REQUIRED to deliver the CORRECT answer, it will have CAS built-in and use PI as a symbol, just like the 50g or prime or nspire or any other number of calculators. Using PI and e (I see the necessity of both) will suffice.

I'm a math teacher. Of course I have problems.
12-29-2013, 12:10 AM
Post: #20
 Thomas Klemm Senior Member Posts: 2,161 Joined: Dec 2013
RE: Math brain teaser
And I thought you chose $$\pi$$ because it's transcedent.
But then any symbol like $$x$$ or $$t$$ will do.

(12-28-2013 09:21 PM)Les_Koller Wrote:  Using PI and e (I see the necessity of both) will suffice.

Can you elaborate on that? Why would you need both?
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)