Author |
Topic: Cartesian Game (Read 470 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Cartesian Game
« on: Dec 23rd, 2006, 8:41pm » |
 Quote  Modify
|
Starting at a point (x,y), you can move to either (x+2y,y), (x-2y,y), (x,y+2x), or (x,y-2x). This becomes the new (x,y), and you have the same linear transformations for your next move, except that you are not allowed to move directly back to the previous point. This can continue indefinitely. Prove that if you begin at the point (1, sqrt(2)), it is impossible to return there.
|
| « Last Edit: Dec 24th, 2006, 3:54pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Cartesian GAme
« Reply #1 on: Dec 24th, 2006, 3:14pm » |
Quote Modify
|
Define the linear transformations A(x, y) = (x+2y, y) and B(x, y) = (x, y+2x). Then any valid sequence of steps is a linear transformation given by some reduced word W in L={A, A-1, B, B-1}. Since the matrices of A and B have rational entries, W does too, so if W fixes the point (1, sqrt(2)), then it must be the identity. Hence it suffices to show that no nontrivial reduced word in L is the identity.
Let
S(A) = {(x,y) : |x| > |y|, xy>0},
S(A-1) = {(x,y) : |x| > |y|, xy<0},
S(B) = {(x,y) : |x| < |y|, xy>0},
S(B-1) = {(x,y) : |x| < |y|, xy<0}.
Suppose that (x,y) is in S(A) or S(A-1), so that |x|>|y|. Then |y+2x| > 2|x|-|y| > |x|, and 2x+y has the same sign as x, so B(x,y) is in S(B). And if (x,y) is in S(B), then since x,y have the same sign, y+2x has the same sign as x and is larger in absolute value, so again B(x,y) is in S(B). Thus B maps every region other than S(B-1) into
S(B).
Similarly, we find that for any X in L, X maps everything other than S(X-1) into S(X).
Now suppose W = Xn...X1 is a nontrivial reduced word in L. That is, each Xi is in L, and no Xi = Xi+1-1.
Pick v=(x,y) not in S(X1-1) or in S(Xn). Then X1(v) is in S(X1). Inductively, if Xi...X1(v) is in S(Xi), then because Xi is not Xi+1-1, we have Xi+1...X1(v) is in S(Xi+1). It follows W(v) is in S(Xn). Since we chose v not in S(Xn), it follows W is not the identity.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print