UVa 10885

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:

${\displaystyle x_{i}=\cos \alpha _{i}}$, ${\displaystyle y_{i}=\sin \alpha _{i}}$, ${\displaystyle {\mbox{for}}i=1,\ldots ,13}$

The distance between i-th and j-th points is: ${\displaystyle {\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 ${\displaystyle \sin {\frac {\alpha _{i}}{2}}}$ and ${\displaystyle \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 ${\displaystyle \sin \left({\frac {\alpha _{i}}{2}}\right)={\frac {p_{i}}{q_{i}}}}$, for some integers ${\displaystyle p_{i}}$ and ${\displaystyle q_{i}}$.

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

So, what we are now really looking for if is just a set of pythagorean triples ${\displaystyle (r_{i},p_{i},q_{i})}$, that is integers, which satisfy the equation: ${\displaystyle 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:

${\displaystyle x_{i}={\frac {r_{i}^{2}-p_{i}^{2}}{q_{i}^{2}}}}$, ${\displaystyle 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