10 replies to this topic

[Prime]

Funny.   I felt uncomfortable about using such complex math as Lagrange Interpolating Polynomial while not remembering how it actually worked.

I set out to invent a simpler switching function, which would select one value out of 11 based on an integer variable N and then convert that value into an integer of my choice. And I have invented such formula!   Thereafter, I consulted a respectable mathematical reference website and discovered that my simple and beautiful switching function was the Lagrange Interpolating Polynomial! Now I understand how it works! It appears 18th century mathematicians (Waring and Euler) invented it just for this puzzle.

 

I shall give a better explanation the puzzle solution and Lagrange Polynomial. It could be useful to some math students and, perhaps, parents of high school students who are about to get bogged down in those dreaded AP math classes.

 

Spoiler for Lagrange Interpolating Polynomial

To solve the puzzle, first we need a periodical (repeating) set of 11 values. Easy. Just take a periodic function like tan() and split its period interval into 11 parts. E.g. for tan() whose period is Pi, our step should be Pi/11. We must avoid Pi/2 + N*Pi points where tan() is not defined. The Pi/11 step avoids hitting Pi/2 naturally. However, if we wanted our 11 periodic values sorted in ascending order, we could subtract 5Pi/11, starting our sequence just to the right of -Pi/2.
Thus the function tan(N*Pi/11 - 5Pi/11) shall produce a repeating set of 11 distinct numbers ranging from tan(-5Pi/11) to tan(5Pi/11).

But those are real numbers not forming any linear progression, and what we need is a set of integers like [1,2,3...,11]. We shall call this set Y and its members [y_1,y₂,...,y₁₁].
Lets designate the result of our tan() function as x and its 11 possible values as set R [r₁,r₂,r₃,...,r₁₁]. The product (x - r₁)* (x - r₂)* (x - r₃)*...* (x - r₁₁) will always be zero since x is equal to one of the R values. Now, if we remove (x - r₁) from the above expression, the product yields zero, except when x = r₁. When x = r₁, the expression is equal to (r₁ - r₂)*(r₁ - r₃)* ... *(r₁ - r₁₁).Therefore dividing (x - r₁)* (x - r₂)* (x - r₃)*...* (x - r₁₁) by (r₁ - r₂)*(r₁ - r₃)* ... *(r₁ - r₁₁), yields zero, except when x = r₁, then we get 1. Now we can multiply that expression by corresponding number from our integer set Y (y₁ for r₁) and thus obtain the expression that yields y₁ when x=r₁ and zero otherwise. Constructing the expressions for r₂ through r₁₁ in like manner, then adding all the expressions together we get our sequence Y [1,2,...,11].
The formula works like a selector switch. For each of the 11 values of x it turns all but one term to zero. The one non-zero term is 1 multiplied by a corresponding number from the set Y. That is the Lagrange Interpolating Polynomial.

If we designate the Lagrange Polynomial as L(), the Tangent function as t(f(N)), the set of integers [1,2,3,...,11] as Y, and the set of the 11 values for tan(f(N)) as R, then the answer to the puzzle could be stated as:
(N - L(t(f(N),R,Y) ) / 11.

 

Lagrange Polynomial: http://mathworld.wol...Polynomial.html

Edited by Prime, 29 January 2013 - 10:43 PM.