## Angol nyelvű szám, 2002. december | ||||

Előző oldal | Tartalomjegyzék | Következő oldal | MEGRENDELŐLAP |

## Solutions to the problems of the Kürschák Competition, 2001

**Gyula Károlyi**

**1.** *Given *3*n*-1* points in the plane, no three of which are collinear, show that it is possible to select *2*n points, such that their convex hull should not be a triangle.*

**Solution 1.** The claim is obvious if *n*=1. For *n*>1, we have to prove that there exist 2*n* among the given points, such that their convex hull has at least 4 vertices. If we manage to find *m*\(\displaystyle \ge\)2*n* points whose convex hull has at least 4 vertices, then *m*-2*n* of them can be deleted so that the convex hull of the remaining points should still have at least 4 vertices.

Thus if the convex hull of the set \(\displaystyle \mathcal{P}\) of the points is not a triangle then we are done. Therefore we can assume that the convex hull of \(\displaystyle \mathcal{P}\) is a triangle *A*_{1}*B*_{1}*C*_{1}. Assume that for some *i*<*n*, we have already defined the points *A*_{1},..., *A*_{i}, such that for all *j*\(\displaystyle \le\)*i* the convex hull of the set \(\displaystyle \mathcal{P}\setminus\{A_1,\dots,A_{j-1}\}\) is the triangle *A*_{j}*B*_{1}*C*_{1}. The set \(\displaystyle \mathcal{P}\setminus\{A_1,\dots,A_{i}\}\) has at least 2*n* elements, thus by the previous argument we can assume that the convex hull of that set is also a triangle. Two vertices of that triangle are clearly *B*_{1} and *C*_{1}. Let *A*_{i+1} denote the third vertex.

Thus we have shown that if it is not possible to select 2*n* points whose convex hull is not a triangle, then there exists a sequence *A*_{1},*A*_{2},...,*A*_{n} of points in \(\displaystyle \mathcal{P}\), such that for all *i*\(\displaystyle \le\)*n*, the convex hull of \(\displaystyle \mathcal{P}\setminus\{A_1,\dots,A_{i-1}\}\) is the triangle *A*_{i} *B*_{1}*C*_{1}. The point sequences *B*_{1},*B*_{2},...,*B*_{n} and *C*_{1},*C*_{2},...,*C*_{n} can be constructed in the same way. Among the 3*n* points hence obtained, there must be two points that coincide. Without the loss of generality we can assume that *A*_{j}=*B*_{k}. Then the set

\(\displaystyle \mathcal{P}\setminus\{A_1,A_2,\dots,A_n\}\setminus\{B_1,B_2,\dots,B_n\}\setminus\{C_1\} \)

has at least *n*-1\(\displaystyle \ge\)1 elements, all of which are interior points of both triangles *A*_{j}*B*_{1}*C*_{1} and *B*_{k}*A*_{1}*C*_{1}. But that is impossible, as the two triangles have no common interior points. This contradiction proves the claim.

*Remarks.* 1. It is not hard to show that the number of points in the problem cannot be decreased to 3*n*-2: Let *A*_{1}*B*_{1}*C*_{1} be an equilateral triangle with centre *O*, and let *A*, *B*, *C* be the midpoints of *OA*_{1}, *OB*_{1}, *OC*_{1}, respectively. Let *k*_{A}, *k*_{B}, *k*_{C} be circular arcs of radius *R* that connect *A*_{1} and *A*, *B*_{1} and *B*, *C*_{1} and *C*, respectively. Finally, let the points *A*_{2},..., *A*_{n}, *B*_{2},...,*B*_{n-1}, *C*_{2},...,*C*_{n-1} lie on the arcs *k*_{A}, *k*_{B}, *k*_{C}. If *n*\(\displaystyle \ge\)2 and *R* is big enough then it is not possible to select 2*n* points of the (3*n*-2)-element set \(\displaystyle \mathcal{P}=\{A_1,\dots,A_n,B_1,\dots,
B_{n-1},C_1,\dots,C_{n-1}\}\), such that their convex hull should not be a triangle. This is true because if *R* is big enough then each line *A*_{i}*A*_{j} separates the points *B*_{k} and \(\displaystyle C_\ell\). Thus if *A*_{i} and *A*_{j} are both vertices of the convex hull of a subset of \(\displaystyle \mathcal{P}\), then it may contain at most *n*-1 points other than *A*_{1},...,*A*_{n}, and therefore the subset itself may contain at most 2*n*-1 points. Similar reasoning applies if the convex hull contains at least two of the points *B*_{i} or the points *C*_{i} as vertices. Therefore, the convex hull of every 2*n*-element subset may only contain one *A*_{i}, one *B*_{i} and one *C*_{i} as vertices, and that makes it necessarily a triangle.

2. For any real number *x* denote the smallest integer not smaller than *x* by \(\displaystyle \lceil x\rceil\). It can be shown that the claim can be improved as follows:

*Let n*\(\displaystyle \ne\)3*. Given \(\displaystyle \lceil3n/2\rceil-1\) points in the plane, no three of which are collinear, it is possible to select n of them, such that their convex hull is not a triangle.*

The two solutions below prove this stronger statement. Note that the condition makes sense for positive integer *n* only, and that for *n*\(\displaystyle \le\)2 the claim obviously holds. Thus, in what follows, *n* is greater than 3. If *n* is odd, then a minor adjustment of the previous counterexample shows that the claim fails to hold if the number of points is reduced to \(\displaystyle \lceil3n/2\rceil-2\).

**Solution 2.** Assume that \(\displaystyle \mathcal{P}\) is a set of at least \(\displaystyle \lceil3n/2
\rceil-1\) points that does not contain *n* points whose convex hull is not a triangle. Let the convex hull of \(\displaystyle \mathcal{P}\) be the triangle *ABC*, and let *A*_{1}=*A*. As in Solution 1, construct the sequence \(\displaystyle A_1,A_2,\dots,A_{\lceil n/2\rceil}\) such that for all \(\displaystyle i\le\lceil n/2\rceil\), the convex hull of \(\displaystyle \mathcal{P}\setminus\{A_1,\dots,A_{i-1}\}\) is the triangle *A*_{i}*BC*.

Consider the points \(\displaystyle A_2,\dots,A_{\lceil n/2\rceil}\) in counterclockwise order as seen from the point *A*. Let *X* and *Y* denote the first and last of them, respectively. Let *X*' and *Y*' be the intersections of lines *AX* and *AY* with the segment *BC*. We can assume, without loss of generality, that the order of points on the line *BC* is *B*, *X*', *Y*', *C*. One of the triangles *BCX* and *BCY* contains the other one. The smaller one of the two triangles, which is covered by the union of triangles *BYY*' and *CXX*', contains the set \(\displaystyle \mathcal{P}'=\mathcal{P}
\setminus\big\{A_1,A_2,\dots,A_{\lceil n/2\rceil},B,C\big\}\). \(\displaystyle \mathcal{P}'\) has at least *n*-3 elements. We can clearly assume that at least half of these points lie inside the triangle *BYY*' (*figure*). Select \(\displaystyle \big\lceil(n-3)/2\big\rceil\) ones out of these points and denote this set by \(\displaystyle \mathcal{P}''\). Finally, let \(\displaystyle \mathcal{Q}=\mathcal{P}''\cup\big\{A_1,A_2,\dots,A_{\lceil n/2\rceil},B\big\}\). \(\displaystyle \mathcal{Q}\) has \(\displaystyle \big\lceil(n-3)/2\rceil+\lceil n/2\big\rceil+1=n\) elements, each of which lies either inside the triangle *AY*'*B* or on its boundary. Thus the points *A*, *Y*, *B* lie on the convex hull of *Q*. However, the convex hull of *Q* must also contain at least one point of the set \(\displaystyle \mathcal{P}''\), contradicting the assumption that \(\displaystyle \mathcal{P}\) does not contain *n* points whose convex hull is not a triangle.

**Solution 3 **(by *G. Lippner*). As explained in Solution 1, we can assume that the convex hull of the points is a triangle *ABC*. Consider the points lying in the interior of this triangle *ABC*. Colour the segments connecting any two of the given points red, blue or green, depending on which side of the triangle they do not intersect: *AB*, *BC*, or *CA*, respectively. Let *R*, *B*, *G*, denote the sets of points incident to red, blue, green segments, respectively. Since *n*\(\displaystyle \ge\)4, there must be at least 2 points in the interior of triangle *ABC*, therefore the set *R*\(\displaystyle \cup\)*B*\(\displaystyle \cup\)*G* is the same as the set of points inside the triangle, and thus it has \(\displaystyle \lceil3n/2
\rceil-4\) elements. We show that one of the sets *R*, *B*, *G* must have at least *n*-2 elements.

Let us represent the sets on a Venn diagram. The letters denote the number of elements in the corresponding subsets.

If, say, *a*\(\displaystyle \ne\)0, then there is a point in the interior of the triangle that is connected to each of the other points with a red segment. Then

\(\displaystyle |P|=\lceil3n/2\rceil-4\ge n-2, \)

as *n*\(\displaystyle \ge\)4. Therefore, we can assume that *a*=*b*=*c*=0. Hence

|*R*\(\displaystyle \cup\)*B*\(\displaystyle \cup\)*G*|= *x*+*y*+*z*+*v*.

Now if each of

|*R*|=*y*+*z*+*v*, |*B*|=*z*+*x*+*v* and |*G*|=*x*+*y*+*v*

were smaller than *n*-2, then this would imply the inequality

\(\displaystyle 3n-8\le2\big(\lceil3n/2\rceil-4\big)=2(x+y+z+v)\le|R|+|B|+|G|\le3(n-3)=3n-9, \)

a contradiction.

Therefore, it is true that one of the sets has at least *n*-2 elements. Assume that |*R*|\(\displaystyle \ge\)*n*-2\(\displaystyle \ge\)2. Consider the set *R*'=*R*\(\displaystyle \cup\){*A*,*B*}. *R*' has at least *n* elements, and its convex hull contains the vertices *A* and *B*. Let *D*\(\displaystyle \in\)*R*, and let *E* be a point in *R* for which the segment *DE* is red. As the line *DE* does not intersect the segment *AB*, *E* cannot be in the interior of triangle *ABD*. Hence the convex hull of *R*' cannot be a triangle. Now it is clearly possible to select a subset of at least *n*\(\displaystyle \ge\)4 elements from *R*', such that their convex hull is not a triangle either.

**2.** *Let k*\(\displaystyle \ge\)3* be an integer, and \(\displaystyle \){k\choose3}">. Prove that if a*_{i}*, b*_{i}*, c*_{i}* *(1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*)* are *3*n distinct real numbers then there are at least k*+1* different numbers among the numbers a*_{i}+*b*_{i}*, a*_{i}+*c*_{i}*, b*_{i}+*c*_{i}*. Show that the statement is not necessarily true for \(\displaystyle n={k\choose3}\).*

**Solution 1.** Assume that the statement is not true, that is, there are at most *k* different numbers among the sums *a*_{i}+*b*_{i}, *a*_{i}+*c*_{i}, *b*_{i}+*c*_{i}. Let *T* denote the set of these numbers. It is obvious that for every 1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*, the numbers *a*_{i}+*b*_{i}, *a*_{i}+*c*_{i}, *b*_{i}+*c*_{i} are pairwise different, and thus form a 3-element subset of *T*. Furthermore, if *a*_{i}+*b*_{i}=*x*, *a*_{i}+*c*_{i}=*y*, *b*_{i}+*c*_{i}=*z* then *a*_{i}=(*x*+*y*-*z*)/2, *b*_{i}=(*x*+*z*-*y*)/2, *c*_{i}=(*y*+*z*-*x*)/2, and thus, the set {*x*,*y*,*z*} uniquely determines the set {*a*_{i},*b*_{i},*c*_{i}}. As

\(\displaystyle
{|T|\choose3}\le{k\choose3}

there exist indices 1\(\displaystyle \le\)*i*<*j*\(\displaystyle \le\)*n*, such that {*a*_{i},*b*_{i},*c*_{i}}= {*a*_{j},*b*_{j},*c*_{j}}, contradicting to the condition.

For the second part, consider the set *T*={*t*_{1},*t*_{2},..., *t*_{k}}, where *t*_{i}=4^{i}. Let \(\displaystyle n={k\choose3}\), and let *T*_{1},*T*_{2},...,*T*_{n} denote the 3-element subsets of *T*. If *T*_{i}={4^{u}, 4^{v},4^{w}}, where 1\(\displaystyle \le\)*u*<*v*<*w*\(\displaystyle \le\)*k* are integers, then let

*a*_{i}=(4^{u}+4^{v}-4^{w})/2, *b*_{i}=(4^{u}+4^{w}-4^{v})/2 and *c*_{i}=(4^{v}+4^{w}-4^{u})/2.

Clearly *a*_{i}+*b*_{i}, *a*_{i}+*c*_{i}, *b*_{i}+*c*_{i}\(\displaystyle \in\)*T*. Hence it is enough to show that the numbers *a*_{i}, *b*_{i}, *c*_{i} (1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*) are all different.

*a*_{i}=*b*_{j} or *a*_{i}=*c*_{j} are not possible for any *i*,*j*, as the numbers *a*_{i} are all negative, whereas *b*_{j} and *c*_{j} are all positive. *b*_{i}=*c*_{j} is not possible either, as each *b*_{i} lies in some interval (2^{2s-2}, 2^{2s-1}), while each *c*_{i} lies in an interval of the form (2^{2s-1}, 2^{2s}) where 3\(\displaystyle \le\)*s*\(\displaystyle \le\)*k* is an integer.

Now let *T*_{i}={4^{u}, 4^{v}, 4^{w}} and *T*_{j}={4^{x}, 4^{y}, 4^{z}}, where 1\(\displaystyle \le\)*u*<*v*<*w*\(\displaystyle \le\)*k* and 1\(\displaystyle \le\)*x*<*y*<*z*\(\displaystyle \le\)*k* are integers. Suppose that *c*_{i}=*c*_{j}. Then

4^{v}+4^{w}-4^{u}= 4^{y}+4^{z}-4^{x}.

As 4^{w}<4^{v}+4^{w}-4^{u}<4^{w+1}, and 4^{z}<4^{y}+4^{z}-4^{x}<4^{z+1}, this can happen only if *w*=*z*, and thus 4^{v}-4^{u}=4^{y}-4^{x}. Here 4^{v-1}<4^{v}-4^{u}<4^{v} and 4^{y-1}<4^{y}-4^{x}<4^{y}, and therefore equality can hold only if *v*=*y* and then necessarily *u*=*x* and *i*=*j*. Thus the numbers *c*_{i} are all different. A similar reasoning shows that the numbers *a*_{i} and the numbers *b*_{i} are all different. That completes the proof.

**Solution 2.** This is a different proof for the first part of the problem, by *D. Kiss.* Assume again, to the contrary, that there are at most *k* different numbers among the 3*n* sums. Then there is a sum that occurs at least \(\displaystyle \frac{3n}{k\){k-1\choose2}"> times. Let *a* denote that sum. If two of the sums *a*_{i}+*b*_{i}, *b*_{i}+*c*_{i} and *a*_{i}+*c*_{i} were equal to *a* for some *i*, then there would be two equal numbers among *a*_{i}, *b*_{i} and *c*_{i}. Thus we can assume that for all \(\displaystyle 1\le i\le{k-1\choose2}+1\), exactly one of the sums *a*_{i}+*b*_{i}, *b*_{i}+*c*_{i} and *a*_{i}+*c*_{i} equals *a*. Now the remaining \(\displaystyle 2\left({k-1\choose2}+1\right)\) sums can assume only *k*-1 different values. Therefore, there is a value, some *b*, that occurs at least

\(\displaystyle 2\left({k-1\choose2}+1\right)\Big/(k-1\)k-2 ">

times. By the previous argument, we can assume that for all 1\(\displaystyle \le\)*i*\(\displaystyle \le\)*k*-1, one of the sums *a*_{i}+*b*_{i}, *b*_{i}+*c*_{i}, *a*_{i}+*c*_{i} is *a* and another one is *b*. The *k*-1 sums still remaining can only assume *k*-2 different values, and hence two of them are equal. But then the corresponding numbers *a*_{i}, *b*_{i}, *c*_{i} are also equal. This contradiction proves the statement.

In what follows there are further constructions for the second part of the problem.

**Solution 3.** Consider the set *T*={*t*_{1},*t*_{2},..., *t*_{k}}, where *t*_{i}=3^{i}. Let {*x*,*y*,*z*} and {*u*,*v*,*w*} be two 3-element subsets of the set {1,2,..., *k*}. As in Solution 1, it is enough to show that if

\(\displaystyle \frac{3^x+3^y-3^z}{2}=\frac{3^u+3^v-3^w}{2}, \)

then the two subsets are necessarily equal, and *z*=*w*. It follows from the equality that

3^{x}+3^{y}+3^{w}=3^{u}+3^{v}+3^{z}=*A*.

If *A* is written in base-3 notation, then its non-zero digits contain either three 1's, or one 1 and one 2, as *x*=*y*=*w* is not possible. The base-3 notation of a number is unique, thus in the first case, {*x*,*y*,*w*} and {*u*,*v*,*z*} are the same 3-element subsets of the set {1,2,..., *k*}. Since *x*,*y*\(\displaystyle \ne\)*z*, this yields *w*=*z* and hence {*x*,*y*}={*u*,*v*}, indeed. In the second case we have that {*x*,*y*,*w*} and {*u*,*v*,*z*} are identical 2-element subsets of {1,2,...,*k*}. As *x*\(\displaystyle \ne\)*y*, this subset must be identical to the set {*x*,*y*} and this would imply *z*\(\displaystyle \in\){*x*,*y*} which is impossible.

**Solution 4.** As also suggested by the above solutions, it is enough to show that for every positive integer *k*, there exists a set *T*_{k}={*t*_{1},*t*_{2},..., *t*_{k}} for which *t*_{x}+*t*_{y}+*t*_{z}=*t*_{u}+*t*_{v}+*t*_{w} is true if and only if the numbers *x*, *y*, *z* are identical to the numbers *u*, *v*, *w* in some order. Then it is easy to show that the \(\displaystyle 3{k\choose3}\) numbers of the form (*t*_{x}+*t*_{y}-*t*_{z})/2 (where {*x*,*y*,*z*} is an arbitrary 3-element subset of the set {1,2,..., *k*}) are all different.

If *k*=1, then *t*_{1}=1 is obviously a good choice. It is enough to show that there exists an infinite sequence *t*_{1},*t*_{2},...,*t*_{i},..., such that for all *i*\(\displaystyle \ge\)2, *t*_{i} cannot be expressed in the form *r*_{1}*t*_{1}+^{...}+ *r*_{i-1}*t*_{i-1}, where *r*_{1},..., *r*_{i-1} are rational numbers. Indeed, assuming that such a sequence exists, consider the set *T*_{k}, and suppose that *t*_{x}+*t*_{y}+*t*_{z}=*t*_{u}+*t*_{v}+*t*_{w} for some 1\(\displaystyle \le\)*x*,*y*,*z*,*u*,*v*,*w*\(\displaystyle \le\)*k*. Let *i* be the greatest one of the indices *x*, *y*, *z*, *u*, *v*, *w*. Now if *t*_{i} does not occur the same number of times on both sides of the equality, then rearrangement yields an equality of the form *t*_{i}=*r*_{1}*t*_{1}+^{...}+*r*_{i-1}*t*_{i-1}. Thus *i* occurs the same numbers of times among *x*, *y*, *z* as among *u*, *v*, *w*. Cancelling the terms equal to *t*_{i} on both sides, and repeating the above procedure, one finally concludes that the numbers *x*, *y*, *z* indeed coincide with *u*, *v*, *w* in some order.

Assume, therefore, that *k*>1 and the numbers *t*_{1},...,*t*_{k-1} have already been determined according to the above requirement. Then the infinite set of numbers that can be expressed in the form *r*_{1}*t*_{1}+^{...}+ *r*_{k-1}*t*_{k-1} is denumerable, while the set of all real numbers is not. Thus, there exists a real number *t*_{k} that cannot be expressed in the form *r*_{1}*t*_{1}+^{...}+ *r*_{k-1}*t*_{k-1}. Hence the existence of a sequence of the required property follows directly from the principle of mathematical induction.

*Remark.* 1. The last solution uses a non-constructive method to prove the existence of an appropriate sequence *t*_{1},*t*_{2},...,*t*_{i},... . It can be shown that the choice \(\displaystyle t_i=\sqrt{p_i}\), for example, yields a suitable sequence. (*p*_{i} denotes the *i*-th positive prime number.) The proof, however, is beyond the scope of this article.

2. As observed by *A. T. Kocsis,* the problem can be generalized as follows. Let *k*\(\displaystyle \ge\)*t*\(\displaystyle \ge\)3 be integers and \(\displaystyle \){k\choose t}">. If *a*_{i1},*a*_{i2}, ...,*a*_{it} (1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*) are *tn* different real numbers then there are at least *k*+1 different numbers among the sums \(\displaystyle \sum_{j=1}^ta_{ij}-a_{ik}\) (1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*, 1\(\displaystyle \le\)*k*\(\displaystyle \le\)*t*), but this is not necessarily so if \(\displaystyle n={k\choose t}\). The proof is left to the reader as an exercise as it does not require any new idea.

3. The story is entirely different if we ask about two term sums. It is clear that if *k*\(\displaystyle \ge\)3 is an integer, \(\displaystyle \){k\choose3}">, and *a*_{i}, *b*_{i}, *c*_{i}, *d*_{i} (1\(\displaystyle \le\)*i*\(\displaystyle \le\)*n*) are 4*n* different real numbers, then there are at least *k*+1 different numbers among the sums *a*_{i}+*b*_{i}, *a*_{i}+*c*_{i}, *a*_{i}+*d*_{i}, *b*_{i}+*c*_{i}, *b*_{i}+*d*_{i}, *c*_{i}+*d*_{i}. Surprisingly enough this cannot be improved significantly. You can think about the following problem: for every integer *k*\(\displaystyle \ge\)3, there exist \(\displaystyle 4{k\choose3}\) different real numbers *a*_{i}, *b*_{i}, *c*_{i}, *d*_{i} \(\displaystyle \left(1\le i\le{k\choose3}\right)\), such that there are at most 2*k* different numbers among the sums *a*_{i}+*b*_{i}, *a*_{i}+*c*_{i}, *a*_{i}+*d*_{i}, *b*_{i}+*c*_{i}, *b*_{i}+*d*_{i}, *c*_{i}+*d*_{i}.

**3.** *In a square lattice, consider any triangle of minimum area that is similar to a given triangle. Prove that the centre of its circumscribed circle is not a lattice point.*

**Solution 1** (by *B. Gerencsér*). Consider a lattice triangle whose circumcentre is also a lattice point. We can assume, without loss of generality, that one vertex (*A*) is the origin. Let the coordinates of the other two vertices be *B*=(*a*,*b*) and *C*=(*c*,*d*), and let the circumcentre be *O*=(*x*,*y*).

From the equality of the segments *OA* and *OB*, the Pythagorean theorem yields *x*^{2}+*y*^{2}=(*a*-*x*)^{2}+(*b*-*y*)^{2}. Hence *a*^{2}+*b*^{2} is even, and thus so are *a*+*b* and *a*-*b*. By a similar argument, *c*+*d* and *c*-*d* are also even numbers.

Consider now the lattice triangle *A*_{1}*B*_{1}*C*_{1}, where

*A*_{1}=*A*, \(\displaystyle B_1=\left(\frac{a+b}{2},\frac{a-b}{2}\right)\) and \(\displaystyle C_1=\left(\frac{c+d}{2},\frac{c-d}{2}\right)\).

In this triangle,

\(\displaystyle {A_1B_1}^2=\left(\frac{a+b}{2}\right)^2+\left( \frac{a-b}{2}\right)^2=\frac{a^2+b^2}{2}= \frac{{AB}^2}{2},\)

\(\displaystyle {A_1C_1}^2=\left(\frac{c+d}{2}\right)^2+\left( \frac{c-d}{2}\right)^2=\frac{c^2+d^2}{2}=\frac{{AC}^2}{2} \)

and

\(\displaystyle {B_1C_1}^2=\left(\frac{a+b-c-d}{2}\right)^2+ \left(\frac{a-b-c+d}{2}\right)^2= \frac{{(a-c)}^2+{(b-d)}^2}{2}=\frac{{BC}^2}{2}. \)

Hence the lengths of the sides of the triangle *A*_{1}*B*_{1}*C*_{1} are \(\displaystyle \frac{1}{\sqrt{2}}\) times the corresponding sides of the triangle *ABC*, and thus we have found a lattice triangle similar to the triangle *ABC*, but of smaller area. This proves the statement.

**Solution 2.** Assume that the circumcentre *O* of a lattice triangle *H* is also a lattice point. Let (*x*,*y*) be the coordinates of one of the side vectors, and let (*a*,*b*) and (*c*,*d*) be the coordinates of the position vectors of the endpoints of that side. Then *a*, *b*, *c*, *d*, *x*, *y* are integers, and from the Pythagorean theorem,

*x*^{2}+*y*^{2}= (*a*-*c*)^{2}+ (*b*-*d*)^{2}=(*a*^{2}+*b*^{2})+(*c*^{2}+*d*^{2})-2(*ac*+*bd*).

As *a*^{2}+*b*^{2}=*c*^{2}+*d*^{2} (the square of the radius of the circumscribed circle), *x*^{2}+*y*^{2} and thus also (*x*+*y*)^{2} is an even number. It follows that *x*+*y* and *x*-*y* are also even.

By rotating the vector (*x*,*y*) through an angle of 45^{o} about the origin in the positive direction, we get the vector \(\displaystyle \left(\frac{x-y}{\sqrt{2}},\frac{x+y}{\sqrt{2}}\right)\). An enlargement of scale factor \(\displaystyle \frac{1}{\sqrt{2}}\) yields the vector \(\displaystyle \left(\frac{x-y}{{2}},\frac{x+y}{{2}}\right)\) which is a vector of integer coordinates.

Thus we have shown that by a rotation through 45^{o} and an enlargement of scale factor \(\displaystyle \frac{1}{\sqrt{2}}\), *H* is mapped onto a similar but smaller triangle. This proves the statement.

*Remark.* The diagonals drawn from one vertex of a cyclic polygon divide the polygon into triangles. As all these triangles have a common circumcentre, the statement of the problem is also valid for any cyclic polygon not just a triangle.