# UVa 10885

Jump to navigation Jump to search

## Summary

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.

## Explanation

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:

$x_{i}=\cos \alpha _{i}$ , $y_{i}=\sin \alpha _{i}$ , ${\mbox{for}}i=1,\ldots ,13$ The distance between i-th and j-th points is: ${\sqrt {(\cos \alpha _{i}-\cos \alpha _{j})^{2}+(\sin \alpha _{i}-\sin \alpha _{j})^{2}}}={\sqrt {2-2\cos(\alpha _{i}-\alpha _{j})}}=2{\sqrt {\frac {1-\cos(\alpha _{i}-\alpha _{j})}{2}}}=2\sin \left({\frac {\alpha _{i}-\alpha _{j}}{2}}\right)$ If we add the constraint, that every $\sin {\frac {\alpha _{i}}{2}}$ and $\cos {\frac {\alpha _{i}}{2}}$ are rational, then the points will have rational coordiantes, and distance between any two of them will be rational, too.

Let $\sin \left({\frac {\alpha _{i}}{2}}\right)={\frac {p_{i}}{q_{i}}}$ , for some integers $p_{i}$ and $q_{i}$ .

Then $\cos \left({\frac {\alpha _{i}}{2}}\right)={\frac {\sqrt {q_{i}^{2}-p_{i}^{2}}}{q_{i}}}$ . This value will be rational if $q_{i}^{2}-p_{i}^{2}=r_{i}^{2}$ , for some integer $r_{i}$ .

So, what we are now really looking for if is just a set of pythagorean triples $(r_{i},p_{i},q_{i})$ , that is integers, which satisfy the equation: $r_{i}^{2}+p_{i}^{2}=q_{i}^{2}$ .

Having found a few of them (by e.g. brute force enumeration), you can express the coordinates of points:

$x_{i}={\frac {r_{i}^{2}-p_{i}^{2}}{q_{i}^{2}}}$ , $y_{i}={\frac {2p_{i}r_{i}}{q_{i}^{2}}}$ .

## Output

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