UVa 10885

From Algorithmist
Jump to navigation Jump to search

10885 - Martin the Gardener[edit]

Summary[edit]

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[edit]

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:

, .

Output[edit]

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