Author |
Topic: Integral Coordinate System (Rus 2002) (Read 459 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Integral Coordinate System (Rus 2002)
« on: Aug 30th, 2007, 1:45pm » |
 Quote  Modify
|
There are n points in the 2D plane such that given any three points, we can find a co-ordinate system such that those three points have integral co-ordinates.
Show that there is a co-ordinate system such that all the n points have integral co-ordinates in that system.
Note: Haven't tried it yet, seems like an interesting problem (hence in medium).
Source: 28th Russian Mathematical Olympiad, 2002.
|
| « Last Edit: Aug 30th, 2007, 1:53pm by Aryabhatta » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integral Coordinate System (Rus 2002)
« Reply #1 on: Aug 30th, 2007, 2:47pm » |
Quote Modify
|
Seems like you should be able to repeatedly add one point while refining your coordinate system.
If you have point a and b, and with point c you have an integral system that puts the distance between a and b x; then you have a point d, that makes the distance between a and b y (in its system). Then you can refine the system by using units y and x times smaller respectively to get a,b,c,d together in the same integral coordinate system
Right? (If it's not, I plead lateness and tiredness as an excuse)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Integral Coordinate System (Rus 2002)
« Reply #2 on: Aug 30th, 2007, 7:11pm » |
Quote Modify
|
I think you need to allow for rotation.
If a triangle has integral coordinates, then all (non-right) angles have rational tangents, since we can draw a horizontal line through a vertex and use the addition law for tan.
Let A,B be any two of the points; by assumption we may fix coordinates so that A,B are rational. Let C be any other point.
Suppose first that C doesn't lie on the line AB. Let P be a point with the same y-coordinate as A (not necessarily one of the given points). Since B is rational, tan BAP is rational. By assumption, tan CAB is rational. So tan CAP, which is the slope of line AC, is rational; similarly for line BC. Now AC,BC are lines with rational slope passing through rational points; therefore their intersection, C, has rational coordinates.
On the other hand, if C lies on the line AB, then by considering a frame in which A,B,C are integral, AC/AB must be rational, so C is rational in any frame in which A,B are.
Thus every point has rational coordinates; since there are finitely many, we can scale them up to be integral.
I wonder if an analogous statement holds in higher dimensions?
It wouldn't be enough to only consider triangles though: equilateral triangles and regular tetrahedra are embeddable in  4 (3 even), but a regular 4-simplex is not.
|
| « Last Edit: Aug 31st, 2007, 5:48am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integral Coordinate System (Rus 2002)
« Reply #3 on: Aug 31st, 2007, 1:23am » |
Quote Modify
|
on Aug 30th, 2007, 7:11pm, Eigenray wrote:| I think you need to allow for rotation. |
|
A yes, it was rather presumptuous to assume that in any integral coordinate system that fits a,b and c, that the distance between a and b is automatically an integer.
Aside from that it'd work right?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print