Author |
Topic: Miracle on three point street (Read 991 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Miracle on three point street
« on: Feb 7th, 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 xA. Extend the line xAB to meet c at xB. Finally, extend the line xBC to meet c at xC. Define the function f on c by f(x)=xC. 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.
|
|
 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 7th, 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 7th, 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 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Miracle on three point street
« Reply #3 on: Feb 7th, 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 fn(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-r2)/(1+r2) there are no fixed points. If s = (1-r2)/(1+r2) there is 1 fixed point, at (0, -1). And if s > (1-r2)/(1+r2), there will be 2 fixed points. Over the rationals we can parametrize them as
s = [ t + u2/t ] / [ 2(1+r2) ]
x =  [ u2 - t2 ] / [ u2 + t2 ]
y = 2 u t / [ u2 + t2 ]
where u = 1-r2, and t is a rational between (1-r)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 7th, 2009, 3:47pm by Eigenray » |
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Miracle on three point street
« Reply #4 on: Feb 7th, 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 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.
|
| « Last Edit: Feb 7th, 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 7th, 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 f2 is the identity, i.e., f(f(x)) = x for all x. In fact, f is itself a "reflection". Letting RP denote reflection about P, we have
f = RCRBRA = RD
for another point D on the line ABC. If we pick coordinates such that A = (ah,k), B = (bh,k), C = (ch,k), where h2 + k2 = 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)
|
| « Last Edit: Feb 7th, 2009, 7:49pm by Eigenray » |
IP Logged |
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Miracle on three point street
« Reply #6 on: Feb 7th, 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..
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print