wu :: forums « wu :: forums - Miracle on three point street » Welcome, Guest. Please Login or Register. Jun 8th, 2023, 11:16am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: william wu, Icarus, SMQ, Grimbal, Eigenray, towr)    Miracle on three point street « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Miracle on three point street  (Read 977 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..
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »