wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Integral Coordinate System (Rus 2002)
        
(Message started by: Aryabhatta on Aug 30^th, 2007, 1:45pm)

Title: Integral Coordinate System (Rus 2002)
Post by Aryabhatta on Aug 30^th, 2007, 1:45pm

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.

Title: Re: Integral Coordinate System (Rus 2002)
Post by towr on Aug 30^th, 2007, 2:47pm

Seems like you should be able to repeatedly add one point while refining your coordinate system.

[hide]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[/hide]
Right? (If it's not, I plead lateness and tiredness as an excuse)

Title: Re: Integral Coordinate System (Rus 2002)
Post by Eigenray on Aug 30^th, 2007, 7:11pm

I think you need to allow for rotation.

If a triangle has integral coordinates, then [hide]all (non-right) angles have rational tangents[/hide], since we can [hide]draw a horizontal line through a vertex and use the addition law for tan[/hide].

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 [hide]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[/hide].

On the other hand, if [hide]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[/hide].

Thus [hide]every point has rational coordinates; since there are finitely many, we can scale them up to be integral[/hide].

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif⁴ (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif³ even), but a regular 4-simplex is not.

Title: Re: Integral Coordinate System (Rus 2002)
Post by towr on Aug 31^st, 2007, 1:23am

on 08/30/07 at 19:11:08, 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?