wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Miracle on three point street
        
(Message started by: ecoist on Feb 7^th, 2009, 10:14am)

Title: Miracle on three point street
Post by ecoist on Feb 7^th, 2009, 10:14am

Just given the following problem that I have no idea how to solve.

Let c be a circle in the plane and let A, B, and C be three points inside c. Choose any point x on c and perform the following. Extend the line xA to meet c at x_A. Extend the line x_AB to meet c at x_B. Finally, extend the line x_BC to meet c at x_C. Define the function f on c by f(x)=x_C. Show that, by iterating f, f(f(...(f(x)...) converges to a unique point x' on c such that x'_C=x'.

I was told that this works for every three points inside a circle, that one gets a different x' tracing the three points in the reverse order C, B, A, and that this works even if the circle is replaced by certain other closed curves.

However --- I think I have a counterexample to "every three points inside a circle". Specifically, I found three points inside a circle and a point x on the circle such that iterating f produces a 6-sided closed polygon, that f(x) iterated becomes x only after 6 iterations! That is, f iterates of x never converge to a fixed point of f.

Title: Re: Miracle on three point street
Post by towr on Feb 7^th, 2009, 1:18pm

I think you're probably not supposed to pick a specific x to start with. Otherwise you have a very simple counterexample by picking A,B,C and the initial x on a diagonal of the circle; the process then iterates between two points.
But possibly most* randomly picked x's all converge on the same point.

Or have you found A,B and C such that any x converges on the closed polygon?

* where I guess "most" would probably be something like "all but countably infinitely many".

Title: Re: Miracle on three point street
Post by ecoist on Feb 7^th, 2009, 2:14pm

towr, the three points are given; x can be chosen arbitrarily. Thus f is defined on all of c. I was told that it didn't matter if the three given points are collinear. My not-as-simple counterexample also iterates between two points. My statement "f(x) iterated becomes x only after 6 iterations!" is false. Each iteration involves three line segments, whence two iterations return to x.

I don't know if, in my example, any x converges on the closed polygon. However, empirically, it seems that the iterates of f are each all clockwise, or all counterclockwise, of the previous iterate.

Title: Re: Miracle on three point street
Post by Eigenray on Feb 7^th, 2009, 3:15pm

Well that's interesting.

Of course trivially you can take A=B=C, or less trivially, take B = O the center of the circle, and C = -A. Then f(f(P)) = -P for all P.

Working algebraically (which is all I know how to do), the coordinates of f are fractional linear transformations, i.e., each coordinate of f(x,y) has the form [ ax + by + c ] / [ Ax + By + C]. To find a fixed point, we can solve for y in the form (quadratic in x)/(linear in x), and then get a cubic in x. So in general (i.e., densely) there will be 3 fixed points (counting multiplicity, over http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbc.gif, and not restricted to the circle).

But the same argument applies to any iterate of f, so for most f, the equation fⁿ(x) = x also has 3 solutions, which must contain the 3 solutions to f(x) = x, so there are no n-cycles.

For example take A,B,C to be an equilateral triangle centered at the origin, with vertices at a distance r from the origin. On the unit circle, there are 0 fixed points for r < 1/2, one fixed point for r = 1/2, and two fixed points for r > 1/2.

Similarly take A = (-r,0), B = (0,s), C = (r,0), and say 0 < r,s < 1. If s < (1-r²)/(1+r²) there are no fixed points. If s = (1-r²)/(1+r²) there is 1 fixed point, at (0, -1). And if s > (1-r²)/(1+r²), there will be 2 fixed points. Over the rationals we can parametrize them as
s = [ t + u²/t ] / [ 2(1+r²) ]
x = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif [ u² - t² ] / [ u² + t² ]
y = 2 u t / [ u² + t² ]
where u = 1-r², and t is a rational between (1-r)² and (1+r)². For example, with r = 1/2, t = 3/2, we get s = 3/4, and fixed points ( http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif3/5, -4/5 ).

I've tried a couple parametric configurations for A,B,C, and what I've seen is that there tends to be one real fixed point that may or may not be on the circle, and a pair of fixed points on the circle that may or may not be real, but the only time they are all real and on the circle is when they all coincide at one point. I can show that this is the case when, for example, one of A,B,C is O, or when two of them are negative each other.

Title: Re: Miracle on three point street
Post by tohuvabohu on Feb 7^th, 2009, 5:00pm

I believe ecoist's counterexample is simple to find. Take a circle and choose any 6 points on c. Label them A, D, B, F, C, E. And connect them in order. You'll find the three points at the intersections of AB-DE, BC-EF, and CD-FA. Just jotting down on paper, it looks like the three points will always be colinear? And three colinear points can't form a triangle ending at the starting point, so I presume they have to converge on a straight line solution, or on the 6 point star? It seems impossible that they would converge on the straight line. The math is all beyond me, so I'll stop rambling now.

Title: Re: Miracle on three point street
Post by Eigenray on Feb 7^th, 2009, 6:39pm

Aha, that's a nice construction. Yes those three points are collinear.

Moreover, whenever A,B,C are collinear, then f² is the identity, i.e., f(f(x)) = x for all x. In fact, f is itself a "reflection". Letting R_P denote reflection about P, we have
f = R_CR_BR_A = R_D
for another point D on the line ABC. If we pick coordinates such that A = (ah,k), B = (bh,k), C = (ch,k), where h² + k² = 1, then D = (dh, k), where
d = ( a-b+c - abc ) / ( 1 + ac-ba-bc ),
or
( a - b + c - d ) + abcd ( 1/a - 1/b + 1/c - 1/d ) = 0
(Proof by Mathematica)

Title: Re: Miracle on three point street
Post by ronnodas on Feb 7^th, 2009, 10:52pm

That construction, by the way is Pascal's Theorem http://en.wikipedia.org/wiki/Pascal%27s_theorem