A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 1. Given points in the plane, no three of which are collinear, show that it is possible to select points, such that their convex hull should not be a triangle. Solution 1. The claim is obvious if . For , we have to prove that there exist among the given points, such that their convex hull has at least 4 vertices. If we manage to find points whose convex hull has at least 4 vertices, then 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 of the points is not a triangle then we are done. Therefore we can assume that the convex hull of is a triangle . Assume that for some , we have already defined the points , such that for all the convex hull of the set is the triangle . The set has at least 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 and . Let denote the third vertex. Thus we have shown that if it is not possible to select points whose convex hull is not a triangle, then there exists a sequence of points in , such that for all , the convex hull of is the triangle . The point sequences and can be constructed in the same way. Among the points hence obtained, there must be two points that coincide. Without the loss of generality we can assume that . Then the set | | has at least elements, all of which are interior points of both triangles and . 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 : Let be an equilateral triangle with centre , and let , , be the midpoints of , , , respectively. Let , , be circular arcs of radius that connect and , and , and , respectively. Finally, let the points , , lie on the arcs , , . If and is big enough then it is not possible to select points of the -element set , such that their convex hull should not be a triangle. This is true because if is big enough then each line separates the points and . Thus if and are both vertices of the convex hull of a subset of , then it may contain at most points other than , and therefore the subset itself may contain at most points. Similar reasoning applies if the convex hull contains at least two of the points or the points as vertices. Therefore, the convex hull of every -element subset may only contain one , one and one as vertices, and that makes it necessarily a triangle.
2. For any real number denote the smallest integer not smaller than by . It can be shown that the claim can be improved as follows: Let . Given points in the plane, no three of which are collinear, it is possible to select 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 only, and that for the claim obviously holds. Thus, in what follows, is greater than 3. If 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 .
Solution 2. Assume that is a set of at least points that does not contain points whose convex hull is not a triangle. Let the convex hull of be the triangle , and let . As in Solution 1, construct the sequence such that for all , the convex hull of is the triangle .
Consider the points in counterclockwise order as seen from the point . Let and denote the first and last of them, respectively. Let and be the intersections of lines and with the segment . We can assume, without loss of generality, that the order of points on the line is , , , . One of the triangles and contains the other one. The smaller one of the two triangles, which is covered by the union of triangles and , contains the set . has at least elements. We can clearly assume that at least half of these points lie inside the triangle (figure). Select ones out of these points and denote this set by . Finally, let . has elements, each of which lies either inside the triangle or on its boundary. Thus the points , , lie on the convex hull of . However, the convex hull of must also contain at least one point of the set , contradicting the assumption that does not contain 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 . Consider the points lying in the interior of this triangle . 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: , , or , respectively (on the figure P, K, Z). Let , , , denote the sets of points incident to red, blue, green segments, respectively. Since , there must be at least 2 points in the interior of triangle , therefore the set is the same as the set of points inside the triangle, and thus it has elements. We show that one of the sets , , must have at least elements. Let us represent the sets on a Venn diagram. The letters denote the number of elements in the corresponding subsets.
If, say, , 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 as . Therefore, we can assume that . Hence Now if each of | | were smaller than , then this would imply the inequality | | a contradiction. Therefore, it is true that one of the sets has at least elements. Assume that . Consider the set . has at least elements, and its convex hull contains the vertices and . Let , and let be a point in for which the segment is red. As the line does not intersect the segment , cannot be in the interior of triangle . Hence the convex hull of cannot be a triangle. Now it is clearly possible to select a subset of at least elements from , such that their convex hull is not a triangle either.
2. Let be an integer, and . Prove that if , , are distinct real numbers then there are at least different numbers among the numbers , , . Show that the statement is not necessarily true for . Solution 1. Assume that the statement is not true, that is, there are at most different numbers among the sums , , . Let denote the set of these numbers. It is that for every , the numbers , , are pairwise different, and thus form a 3-element subset of . Furthermore, if , , then , , , and thus, the set uniquely determines the set . As there exist indices , such that , contradicting to the condition. For the second part, consider the set , where . Let , and let denote the 3-element subsets of . If , where are integers, then let | | Clearly . Hence it is enough to show that the numbers () are all different. or are not possible for any , as the numbers are all negative, whereas and are all positive. is not possible either, as each lies in some interval , while each lies in an interval of the form where is an integer. Now let and , where and are integers. Suppose that . Then As , and , this can happen only if , and thus . Here and , and therefore equality can hold only if and then necessarily and . Thus the numbers are all different. A similar reasoning shows that the numbers and the numbers 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 different numbers among the sums. Then there is a sum that occurs at least times. Let denote that sum. If two of the sums , and were equal to for some , then there would be two equal numbers among , and . Thus we can assume that for all , exactly one of the sums , and equals . Now the remaining sums can assume only different values. Therefore, there is a value, some , that occurs at least times. By the previous argument, we can assume that for all , one of the sums , , is and another one is . The sums still remaining can only assume different values, and hence two of them are equal. But then the corresponding numbers , , 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 , where . Let and be two 3-element subsets of the set . As in Solution 1, it is enough to show that if then the two subsets are necessarily equal, and . It follows from the equality that If is written in base-3 notation, then its non-zero digits contain either three 1's, or one 1 and one 2, as is not possible. The base-3 notation of a number is unique, thus in the first case, and are the same 3-element subsets of the set . Since , this yields and hence , indeed. In the second case we have that and are identical 2-element subsets of . As , this subset must be identical to the set and this would imply which is impossible.
Solution 4. As also suggested by the above solutions, it is enough to show that for every positive integer , there exists a set for which is true if and only if the numbers , , are identical to the numbers , , in some order. Then it is easy to show that the numbers of the form (where is an arbitrary 3-element subset of the set ) are all different. If , then is obviously a good choice. It is enough to show that there exists an infinite sequence , such that for all , cannot be expressed in the form , where are rational numbers. Indeed, assuming that such a sequence exists, consider the set , and suppose that for some . Let be the greatest one of the indices , , , , , . Now if does not occur the same number of times on both sides of the equality, then rearrangement yields an equality of the form . Thus occurs the same numbers of times among , , as among , , . Cancelling the terms equal to on both sides, and repeating the above procedure, one finally concludes that the numbers , , indeed coincide with , , in some order. Assume, therefore, that and the numbers have already been determined according to the above requirement. Then the infinite set of numbers that can be expressed in the form is denumerable, while the set of all real numbers is not. Thus, there exists a real number that cannot be expressed in the form . 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 It can be shown that the choice , for example, yields a suitable sequence. ( denotes the -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 be integers and . If () are different real numbers then there are at least different numbers among the sums (, ), but this is not necessarily so if . 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 is an integer, , and , , , () are different real numbers, then there are at least different numbers among the sums , , , , , . Surprisingly enough this cannot be improved significantly. You can think about the following problem: for every integer , there exist different real numbers , , , , such that there are at most different numbers among the sums , , , , , .
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 () is the origin. Let the coordinates of the other two vertices be and , and let the circumcentre be . From the equality of the segments and , the Pythagorean theorem yields . Hence is even, and thus so are and . By a similar argument, and are also even numbers. Consider now the lattice triangle , where | | In this triangle,
and | | Hence the lengths of the sides of the triangle are times the corresponding sides of the triangle , and thus we have found a lattice triangle similar to the triangle , but of smaller area. This proves the statement.
Solution 2. Assume that the circumcentre of a lattice triangle is also a lattice point. Let be the coordinates of one of the side vectors, and let and be the coordinates of the position vectors of the endpoints of that side. Then , , , , , are integers, and from the Pythagorean theorem, | | As (the square of the radius of the circumscribed circle), and thus also is an even number. It follows that and are also even. By rotating the vector through an angle of about the origin in the positive direction, we get the vector . An enlargement of scale factor yields the vector which is a vector of integer coordinates. Thus we have shown that by a rotation through and an enlargement of scale factor , 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.
|