Author 
Topic: Miracle on three point street (Read 977 times) 

ecoist
Senior Riddler
Gender:
Posts: 405


Miracle on three point street
« on: Feb 7^{th}, 2009, 10:14am » 
Quote Modify

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_{A}B to meet c at x_{B}. Finally, extend the line x_{B}C 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 6sided 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Miracle on three point street
« Reply #1 on: Feb 7^{th}, 2009, 1:18pm » 
Quote Modify

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".


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ecoist
Senior Riddler
Gender:
Posts: 405


Re: Miracle on three point street
« Reply #2 on: Feb 7^{th}, 2009, 2:14pm » 
Quote Modify

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 notassimple 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.


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Miracle on three point street
« Reply #3 on: Feb 7^{th}, 2009, 3:15pm » 
Quote Modify

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 , and not restricted to the circle). But the same argument applies to any iterate of f, so for most f, the equation f^{n}(x) = x also has 3 solutions, which must contain the 3 solutions to f(x) = x, so there are no ncycles. 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 < (1r^{2})/(1+r^{2}) there are no fixed points. If s = (1r^{2})/(1+r^{2}) there is 1 fixed point, at (0, 1). And if s > (1r^{2})/(1+r^{2}), there will be 2 fixed points. Over the rationals we can parametrize them as s = [ t + u^{2}/t ] / [ 2(1+r^{2}) ] x = [ u^{2}  t^{2} ] / [ u^{2} + t^{2} ] y = 2 u t / [ u^{2} + t^{2} ] where u = 1r^{2}, and t is a rational between (1r)^{2} and (1+r)^{2}. For example, with r = 1/2, t = 3/2, we get s = 3/4, and fixed points ( 3/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.

« Last Edit: Feb 7^{th}, 2009, 3:47pm by Eigenray » 
IP Logged 



tohuvabohu
Junior Member
Gender:
Posts: 102


Re: Miracle on three point street
« Reply #4 on: Feb 7^{th}, 2009, 5:00pm » 
Quote Modify

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 ABDE, BCEF, and CDFA. 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.

« Last Edit: Feb 7^{th}, 2009, 5:04pm by tohuvabohu » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Miracle on three point street
« Reply #5 on: Feb 7^{th}, 2009, 6:39pm » 
Quote Modify

Aha, that's a nice construction. Yes those three points are collinear. Moreover, whenever A,B,C are collinear, then f^{2} 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_{C}R_{B}R_{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^{2} + k^{2} = 1, then D = (dh, k), where d = ( ab+c  abc ) / ( 1 + acbabc ), or ( a  b + c  d ) + abcd ( 1/a  1/b + 1/c  1/d ) = 0 (Proof by Mathematica)

« Last Edit: Feb 7^{th}, 2009, 7:49pm by Eigenray » 
IP Logged 



Ronno
Junior Member
Gender:
Posts: 140


Re: Miracle on three point street
« Reply #6 on: Feb 7^{th}, 2009, 10:52pm » 
Quote Modify

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


IP Logged 
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..



