Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Angol nyelvű szám, 2002. december

Előző oldalTartalomjegyzékKövetkező oldalMEGRENDELŐLAP


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

Gyula Károlyi

1. Given 3n-1 points in the plane, no three of which are collinear, show that it is possible to select 2n 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 2n among the given points, such that their convex hull has at least 4 vertices. If we manage to find m\(\displaystyle \ge\)2n points whose convex hull has at least 4 vertices, then m-2n 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 A1B1C1. Assume that for some i<n, we have already defined the points A1,..., Ai, 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 AjB1C1. The set \(\displaystyle \mathcal{P}\setminus\{A_1,\dots,A_{i}\}\) has at least 2n 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 B1 and C1. Let Ai+1 denote the third vertex.

Thus we have shown that if it is not possible to select 2n points whose convex hull is not a triangle, then there exists a sequence A1,A2,...,An 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 Ai B1C1. The point sequences B1,B2,...,Bn and C1,C2,...,Cn can be constructed in the same way. Among the 3n points hence obtained, there must be two points that coincide. Without the loss of generality we can assume that Aj=Bk. 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 AjB1C1 and BkA1C1. 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 3n-2: Let A1B1C1 be an equilateral triangle with centre O, and let A, B, C be the midpoints of OA1, OB1, OC1, respectively. Let kA, kB, kC be circular arcs of radius R that connect A1 and A, B1 and B, C1 and C, respectively. Finally, let the points A2,..., An, B2,...,Bn-1, C2,...,Cn-1 lie on the arcs kA, kB, kC. If n\(\displaystyle \ge\)2 and R is big enough then it is not possible to select 2n points of the (3n-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 AiAj separates the points Bk and \(\displaystyle C_\ell\). Thus if Ai and Aj 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 A1,...,An, and therefore the subset itself may contain at most 2n-1 points. Similar reasoning applies if the convex hull contains at least two of the points Bi or the points Ci as vertices. Therefore, the convex hull of every 2n-element subset may only contain one Ai, one Bi and one Ci 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 A1=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 AiBC.

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 ai, bi, ci (1\(\displaystyle \le\)i\(\displaystyle \le\)n) are 3n distinct real numbers then there are at least k+1 different numbers among the numbers ai+bi, ai+ci, bi+ci. 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 ai+bi, ai+ci, bi+ci. Let T denote the set of these numbers. It is obvious that for every 1\(\displaystyle \le\)i\(\displaystyle \le\)n, the numbers ai+bi, ai+ci, bi+ci are pairwise different, and thus form a 3-element subset of T. Furthermore, if ai+bi=x, ai+ci=y, bi+ci=z then ai=(x+y-z)/2, bi=(x+z-y)/2, ci=(y+z-x)/2, and thus, the set {x,y,z} uniquely determines the set {ai,bi,ci}. As

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

there exist indices 1\(\displaystyle \le\)i<j\(\displaystyle \le\)n, such that {ai,bi,ci}= {aj,bj,cj}, contradicting to the condition.

For the second part, consider the set T={t1,t2,..., tk}, where ti=4i. Let \(\displaystyle n={k\choose3}\), and let T1,T2,...,Tn denote the 3-element subsets of T. If Ti={4u, 4v,4w}, where 1\(\displaystyle \le\)u<v<w\(\displaystyle \le\)k are integers, then let

ai=(4u+4v-4w)/2, bi=(4u+4w-4v)/2 and ci=(4v+4w-4u)/2.

Clearly ai+bi, ai+ci, bi+ci\(\displaystyle \in\)T. Hence it is enough to show that the numbers ai, bi, ci (1\(\displaystyle \le\)i\(\displaystyle \le\)n) are all different.

ai=bj or ai=cj are not possible for any i,j, as the numbers ai are all negative, whereas bj and cj are all positive. bi=cj is not possible either, as each bi lies in some interval (22s-2, 22s-1), while each ci lies in an interval of the form (22s-1, 22s) where 3\(\displaystyle \le\)s\(\displaystyle \le\)k is an integer.

Now let Ti={4u, 4v, 4w} and Tj={4x, 4y, 4z}, where 1\(\displaystyle \le\)u<v<w\(\displaystyle \le\)k and 1\(\displaystyle \le\)x<y<z\(\displaystyle \le\)k are integers. Suppose that ci=cj. Then

4v+4w-4u= 4y+4z-4x.

As 4w<4v+4w-4u<4w+1, and 4z<4y+4z-4x<4z+1, this can happen only if w=z, and thus 4v-4u=4y-4x. Here 4v-1<4v-4u<4v and 4y-1<4y-4x<4y, and therefore equality can hold only if v=y and then necessarily u=x and i=j. Thus the numbers ci are all different. A similar reasoning shows that the numbers ai and the numbers bi 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 3n 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 ai+bi, bi+ci and ai+ci were equal to a for some i, then there would be two equal numbers among ai, bi and ci. Thus we can assume that for all \(\displaystyle 1\le i\le{k-1\choose2}+1\), exactly one of the sums ai+bi, bi+ci and ai+ci 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 ai+bi, bi+ci, ai+ci 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 ai, bi, ci 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={t1,t2,..., tk}, where ti=3i. 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

3x+3y+3w=3u+3v+3z=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 Tk={t1,t2,..., tk} for which tx+ty+tz=tu+tv+tw 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 (tx+ty-tz)/2 (where {x,y,z} is an arbitrary 3-element subset of the set {1,2,..., k}) are all different.

If k=1, then t1=1 is obviously a good choice. It is enough to show that there exists an infinite sequence t1,t2,...,ti,..., such that for all i\(\displaystyle \ge\)2, ti cannot be expressed in the form r1t1+...+ ri-1ti-1, where r1,..., ri-1 are rational numbers. Indeed, assuming that such a sequence exists, consider the set Tk, and suppose that tx+ty+tz=tu+tv+tw 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 ti does not occur the same number of times on both sides of the equality, then rearrangement yields an equality of the form ti=r1t1+...+ri-1ti-1. Thus i occurs the same numbers of times among x, y, z as among u, v, w. Cancelling the terms equal to ti 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 t1,...,tk-1 have already been determined according to the above requirement. Then the infinite set of numbers that can be expressed in the form r1t1+...+ rk-1tk-1 is denumerable, while the set of all real numbers is not. Thus, there exists a real number tk that cannot be expressed in the form r1t1+...+ rk-1tk-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 t1,t2,...,ti,... . It can be shown that the choice \(\displaystyle t_i=\sqrt{p_i}\), for example, yields a suitable sequence. (pi 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 ai1,ai2, ...,ait (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 ai, bi, ci, di (1\(\displaystyle \le\)i\(\displaystyle \le\)n) are 4n different real numbers, then there are at least k+1 different numbers among the sums ai+bi, ai+ci, ai+di, bi+ci, bi+di, ci+di. 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 ai, bi, ci, di \(\displaystyle \left(1\le i\le{k\choose3}\right)\), such that there are at most 2k different numbers among the sums ai+bi, ai+ci, ai+di, bi+ci, bi+di, ci+di.

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 x2+y2=(a-x)2+(b-y)2. Hence a2+b2 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 A1B1C1, where

A1=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 A1B1C1 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,

x2+y2= (a-c)2+ (b-d)2=(a2+b2)+(c2+d2)-2(ac+bd).

As a2+b2=c2+d2 (the square of the radius of the circumscribed circle), x2+y2 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 45o 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 45o 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.