Yoak: A Fun Math Trick – Guess the Polynomial
Here’s an old puzzle, I think from Martin Gardner though I can’t immediately find a reference, adapted as a fun trick for spring break — if you have just the right sort of friends.
Invite a friend to invent a polynomial of any order, but require that it have only positive integer coefficients. Next, you explain that you have to get something of a feel for the polynomial so you provide an integer and ask them to apply the polynomial to it, telling you the value. You may have to do this more than once. You then close your eyes and dramatically tell them what their polynomial is.
What strategy would you use and how many values would you have to provide?
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
jyoak said,
April 8, 2009 at 1:26 pm
Here’s the solution:
[spoiler]
First consider a more simple problem. Suppose that the problem you pose is exactly as above, but you require an extra condition be met: None of the coefficients may be larger than 9. You can now get the answer by asking for the polynomial value of a single integer: 10.
Suppose the polynomial selected was p = 4x^3+2x+7. p(10) is now 4000+20+7 or 4027. The positional notation we use with normal base-10 numbers means that this is 4 1ooos (or 10-cubeds), 2 10s (or 10s), and 7 units (or 10^0s if you like.) This tells us the coefficients of each of the terms in the polynomial. You just read it from left to right: 4-0-2-7 means 4x^3+0x^2+2x+7 . Drop out the zero term and you have the polynomial with which we started.
Now… this only works because we ensured that the coefficients were smaller than the number we provided — 10. Consider the polynomial p = 10x^2+2. Using the same method p(10) is 102 which you might be tempted to read as x^3+2 instead of 10x^2+2. You can’t tell 10 of the x^2 items from 1 of the x^3 items if the coefficient can be as large or larger than the number you’re providing.
This brings us to the answer to the original problem. You first ask for p(1). This will give us the sum of the coefficients in the polynomial because 1 raised to any power will be 1. This sum is sure to be as large or larger than any individual coefficient as we only allowed positive coefficients. So after asking for p(1), you ask for p(x), x>p(1) and you have the info you need to obtain the original polynomial.
Now… unless you’re lucky enough to be able to use 10, a little extra decoding might be necessary. When you ask for p(n), you’re going to be given an answer in base-10, unless you have *really* strange friends. So when we ask for p(10), since the 10 matches the base of the answer, this simple left-to-right reading of the coefficients is possible, because of the way that the answer is encoded. The rightmost digit refers to the number of units. The next is the number of tens. The next is the number of hundreds, etc. These correspond to the number of x^0, x^1, x^2, etc., out of the polynomial. But what happens if the original polynomial is 4x^2+4x+4? When you ask for p(1), you’ll get 12, and now if you ask for p(10), you’ll have the problem shown above.
The general answer is that you have to convert the answer you receive into the base of the number you provided in the second step. So… for the problem above, you are going to ask for p of some number larger than 12. To make the mental math as easy as possible, suppose that you ask for p(100). The answer that you’ll get will be 40,000 + 400 + 4 or 40404. Now you convert this to a base-100 number. From right to left, the first digit contains units and there can be up to 99 of them. The next contains hundreds (also up to 99). Next ten thousands, etc. How many units? 4. How many hundreds? 4. How many ten thousands, 4. So the number in base-100 is 444, which is your answer.
Now… using 10s and 100s will make it fairly easy for the person you’re doing this with to figure it out. Plus using 100 is wasteful in some strange sense. So let’s use a minimal value instead just to demonstrate. After getting p(1) as 12, we ask for p(13). The answer we get is:
4 * 13^2 = 4 * 169 = 676
+
4 * 13 = 52
+
4
= 676+52+4 = 732
So… p(1) = 12 and p(13) = 732.
You now convert 732 base-10 into base-13.
The places will be units, 13s, and 169s, up to 12 each. (The next would be 2197s, which is larger than 732, so all remaining places to the left will be zero.)
So how many 169s in 732? 732/169 = 4 R 56
How many 13s left in the 56? 56/13 = 4 R 4
And finally, how many 1s in 4? 4/1 = 4
So… 732 is 444 in base-13, which was the original polynomial.
[/spoiler]
Stephen Morris said,
April 19, 2009 at 4:36 pm
[spoiler] You can show that two test numbers are always necessary, except when the polynomial is a constant.
If the result is less than the test number, t, then we have p(t) > t. As all of the coefficients are positive integers this is only possible if p(x) is a constant and does not contain any terms involving x. This is the only time we identify the polynomial with one test number.
If the polynomial is not a constant then two test numbers are always required. The result will always be at least as great as the test number. So p(t) >= t. Lets say the result is r. There are always at least two choices for p(x) which are p(x) = r and p(x) = x + (r-t). [/spoiler]