10885 - Martin the Gardener
Find a set of 13 points on a 2-dimensional Cartesian plane, such that:
- the points have integer coordinates
- the distance between any two points is an integer
- no three points lie on the same straight line.
We can weaken the first two conditions. Suppose, that we have found a set of 13 points with rational coordinates and rational distances between every two of them. Let L be the LCM of denominators of all coordinates and distances. Then, by multiplying coordinates of every point by L, we'll get a set of points with integer coordiantes and integer distance between every two of them.
Now, let's impose an additional constraint on the set of points. We'll be looking for a set of points, all of which lie on the same circle. It's easy to see, that every three points from this set will not lie on the same line, because a straight line intersects a circle in at most two points.
As a simplification, we may further assume that the points lie on a circle of unit radius, whose center is at the origin. Then the coordinates of the points may be written in the following form:
The distance between i-th and j-th points is:
If we add the constraint, that every and are rational, then the points will have rational coordiantes, and distance between any two of them will be rational, too.
Let , for some integers and .
Then . This value will be rational if , for some integer .
So, what we are now really looking for if is just a set of pythagorean triples , that is integers, which satisfy the equation: .
Having found a few of them (by e.g. brute force enumeration), you can express the coordinates of points:
0 180 0 3876 432 0 432 4056 1615 0 1615 4056 2047 180 2047 3876 2511 3528 2511 528 2880 1020 2880 3036 3136 2028