Solutions to the problems of the Kürschák Competition, 2001
Gyula Károlyi
1. Given 3n1 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 m2n 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_{j1}\}\) is the triangle A_{j}B_{1}C_{1}. 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 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 2n 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_{i1}\}\) 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 3n 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 n1\(\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 3n2: 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_{n1}, C_{2},...,C_{n1} 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 2n points of the (3n2)element set \(\displaystyle \mathcal{P}=\{A_1,\dots,A_n,B_1,\dots,
B_{n1},C_1,\dots,C_{n1}\}\), 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 n1 points other than A_{1},...,A_{n}, and therefore the subset itself may contain at most 2n1 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 2nelement 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\rceil1\) 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\rceil2\).
Solution 2. Assume that \(\displaystyle \mathcal{P}\) is a set of at least \(\displaystyle \lceil3n/2
\rceil1\) 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_{i1}\}\) 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 n3 elements. We can clearly assume that at least half of these points lie inside the triangle BYY' (figure). Select \(\displaystyle \big\lceil(n3)/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(n3)/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
\rceil4\) elements. We show that one of the sets R, B, G must have at least n2 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\rceil4\ge n2,
\)
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 n2, then this would imply the inequality
\(\displaystyle
3n8\le2\big(\lceil3n/2\rceil4\big)=2(x+y+z+v)\leR+B+G\le3(n3)=3n9,
\)
a contradiction.
Therefore, it is true that one of the sets has at least n2 elements. Assume that R\(\displaystyle \ge\)n2\(\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 3n 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 3element subset of T. Furthermore, if a_{i}+b_{i}=x, a_{i}+c_{i}=y, b_{i}+c_{i}=z then a_{i}=(x+yz)/2, b_{i}=(x+zy)/2, c_{i}=(y+zx)/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 3element 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^{2s2}, 2^{2s1}), while each c_{i} lies in an interval of the form (2^{2s1}, 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^{v1}<4^{v}4^{u}<4^{v} and 4^{y1}<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 3n sums. Then there is a sum that occurs at least \(\displaystyle \frac{3n}{k\){k1\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{k1\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({k1\choose2}+1\right)\) sums can assume only k1 different values. Therefore, there is a value, some b, that occurs at least
\(\displaystyle
2\left({k1\choose2}+1\right)\Big/(k1\)k2
">
times. By the previous argument, we can assume that for all 1\(\displaystyle \le\)i\(\displaystyle \le\)k1, one of the sums a_{i}+b_{i}, b_{i}+c_{i}, a_{i}+c_{i} is a and another one is b. The k1 sums still remaining can only assume k2 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 3element subsets of the set {1,2,..., k}. As in Solution 1, it is enough to show that if
\(\displaystyle
\frac{3^x+3^y3^z}{2}=\frac{3^u+3^v3^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 base3 notation, then its nonzero digits contain either three 1's, or one 1 and one 2, as x=y=w is not possible. The base3 notation of a number is unique, thus in the first case, {x,y,w} and {u,v,z} are the same 3element 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 2element 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 3element 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_{i1}t_{i1}, where r_{1},..., r_{i1} 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_{i1}t_{i1}. 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_{k1} 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_{k1}t_{k1} 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_{k1}t_{k1}. 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 nonconstructive 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 ith 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 4n 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 2k 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}=(ax)^{2}+(by)^{2}. Hence a^{2}+b^{2} is even, and thus so are a+b and ab. By a similar argument, c+d and cd 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{ab}{2}\right)\) and \(\displaystyle C_1=\left(\frac{c+d}{2},\frac{cd}{2}\right)\).
In this triangle,
\(\displaystyle
{A_1B_1}^2=\left(\frac{a+b}{2}\right)^2+\left(
\frac{ab}{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{cd}{2}\right)^2=\frac{c^2+d^2}{2}=\frac{{AC}^2}{2}
\)
and
\(\displaystyle
{B_1C_1}^2=\left(\frac{a+bcd}{2}\right)^2+
\left(\frac{abc+d}{2}\right)^2=
\frac{{(ac)}^2+{(bd)}^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}= (ac)^{2}+ (bd)^{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 xy 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{xy}{\sqrt{2}},\frac{x+y}{\sqrt{2}}\right)\). An enlargement of scale factor \(\displaystyle \frac{1}{\sqrt{2}}\) yields the vector \(\displaystyle \left(\frac{xy}{{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.
