IMO 1969 · Problem 5
Given \(n > 4\) points in the plane such that no three are collinear. Prove that there are at least \(\binom{n-3}{2}\) convex quadrilaterals whose vertices are four of the given points.
Official text of the problem. Official problem paper (PDF)
Solution
We first prove that any five points in the plane, no three collinear, contain four vertices of a convex quadrilateral.
If their convex hull has at least four vertices, choose any four of those vertices. They form a convex quadrilateral, since none can lie in the triangle formed by the other three.
Otherwise, their convex hull is a triangle \(ABC\), and the remaining points \(D,E\) lie strictly inside it. The segments \(AD,BD,CD\) partition \(ABC\) into three triangles. Since no three points are collinear, \(E\) lies strictly inside one of these triangles; relabeling \(A,B,C\), suppose it lies inside \(ABD\).
The segment \(CE\) starts outside triangle \(ABD\) and ends inside it, so it crosses its boundary. It cannot cross \(AB\), because \(C\) and \(E\) lie strictly on the same side of the line \(AB\). Thus \(CE\) crosses \(AD\) or \(BD\). The crossing lies in the interiors of both segments: passing through a vertex would make three given points collinear.
The four endpoints of two such crossing segments form a convex quadrilateral. Indeed, the line through either segment separates the endpoints of the other, so each endpoint lies outside the triangle formed by the other three. This proves the claim.
Now let \(q\) be the number of convex quadrilaterals determined by the \(n\) given points. Count pairs \((S,Q)\), where \(S\) is a set of five given points and \(Q\) is a convex quadrilateral whose vertices belong to \(S\).
By the claim, each of the \(\binom n5\) choices of \(S\) contributes at least one pair. Conversely, each quadrilateral \(Q\) belongs to exactly \(n-4\) such sets \(S\), obtained by adjoining one of the remaining points. Therefore \[ (n-4)q\geq \binom n5, \] and hence \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
Finally, \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] This is nonnegative for every integer \(n\geq5\): it is zero for \(n=5,6\), and positive for \(n\geq7\). Consequently, \[ \boxed{q\geq \binom{n-3}{2}}. \]
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1969 · Aufgabe 5
Gegeben seien \(n > 4\) Punkte in der Ebene, von denen keine drei auf einer Geraden liegen. Man beweise, dass es mindestens \(\binom{n-3}{2}\) konvexe Vierecke gibt, deren Eckpunkte vier der gegebenen Punkte sind.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir beweisen zunächst, dass unter je fünf Punkten in der Ebene, von denen keine drei auf einer Geraden liegen, vier die Eckpunkte eines konvexen Vierecks bilden.
Hat ihre konvexe Hülle mindestens vier Eckpunkte, so wählen wir vier beliebige davon. Sie bilden ein konvexes Viereck, da keiner von ihnen im Dreieck liegen kann, das von den anderen drei gebildet wird.
Andernfalls ist ihre konvexe Hülle ein Dreieck \(ABC\), und die übrigen Punkte \(D,E\) liegen in dessen Innerem. Die Strecken \(AD,BD,CD\) zerlegen \(ABC\) in drei Dreiecke. Da keine drei Punkte auf einer Geraden liegen, liegt \(E\) im Inneren eines dieser Dreiecke; durch Umbenennen von \(A,B,C\) können wir annehmen, dass es im Inneren von \(ABD\) liegt.
Die Strecke \(CE\) beginnt außerhalb des Dreiecks \(ABD\) und endet in seinem Inneren, schneidet also dessen Rand. Sie kann \(AB\) nicht schneiden, da \(C\) und \(E\) beide in derselben offenen Halbebene bezüglich der Geraden \(AB\) liegen. Somit schneidet \(CE\) die Strecke \(AD\) oder \(BD\). Der Schnittpunkt liegt im Inneren beider Strecken: Verliefe eine Strecke durch einen Eckpunkt, so lägen drei der gegebenen Punkte auf einer Geraden.
Die vier Endpunkte zweier solcher sich schneidender Strecken bilden ein konvexes Viereck. Die Gerade durch jede der beiden Strecken trennt nämlich die Endpunkte der jeweils anderen, sodass jeder Endpunkt außerhalb des von den anderen drei gebildeten Dreiecks liegt. Damit ist die Behauptung bewiesen.
Es sei nun \(q\) die Anzahl der konvexen Vierecke, die durch die \(n\) gegebenen Punkte bestimmt werden. Wir zählen die Paare \((S,Q)\), wobei \(S\) eine Menge aus fünf der gegebenen Punkte und \(Q\) ein konvexes Viereck ist, dessen Eckpunkte zu \(S\) gehören.
Nach der bewiesenen Behauptung liefert jede der \(\binom n5\) Möglichkeiten für \(S\) mindestens ein Paar. Umgekehrt gehört jedes Viereck \(Q\) zu genau \(n-4\) solchen Mengen \(S\), die man erhält, indem man einen der übrigen Punkte hinzunimmt. Daher gilt \[ (n-4)q\geq \binom n5, \] und somit \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
Schließlich gilt \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] Dieser Ausdruck ist für jede ganze Zahl \(n\geq5\) nichtnegativ: Für \(n=5,6\) ist er null, und für \(n\geq7\) ist er positiv. Folglich gilt \[ \boxed{q\geq \binom{n-3}{2}}. \]
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1969 · Soru 5
Düzlemde herhangi üçü doğrusal olmayan \(n > 4\) nokta veriliyor. Köşeleri verilen noktalardan dördü olan en az \(\binom{n-3}{2}\) dışbükey dörtgen bulunduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Önce düzlemde herhangi üçü doğrusal olmayan her beş noktadan dördünün bir dışbükey dörtgenin köşelerini oluşturduğunu kanıtlayalım.
Bu noktaların dışbükey örtüsünün en az dört köşesi varsa, bu köşelerden herhangi dördünü seçelim. Hiçbiri diğer üçünün oluşturduğu üçgenin içinde bulunamayacağından, bunlar bir dışbükey dörtgen oluşturur.
Aksi hâlde dışbükey örtü bir \(ABC\) üçgenidir ve kalan \(D,E\) noktaları bu üçgenin kesin olarak içindedir. \(AD,BD,CD\) doğru parçaları \(ABC\)'yi üç üçgene ayırır. Herhangi üç nokta doğrusal olmadığından \(E\), bu üçgenlerden birinin kesin olarak içindedir; \(A,B,C\)'yi yeniden adlandırarak \(ABD\)'nin içinde olduğunu varsayalım.
\(CE\) doğru parçası \(ABD\) üçgeninin dışında başlayıp içinde bittiğinden üçgenin sınırını keser. \(C\) ve \(E\), \(AB\) doğrusunun kesin olarak aynı tarafında bulunduğundan \(AB\)'yi kesemez. Dolayısıyla \(CE\), \(AD\)'yi veya \(BD\)'yi keser. Kesişim noktası her iki doğru parçasının da içindedir: bir köşeden geçmesi, verilen noktalardan üçünün doğrusal olmasına yol açardı.
Bu şekilde kesişen iki doğru parçasının dört uç noktası bir dışbükey dörtgen oluşturur. Gerçekten de, doğru parçalarının her birinden geçen doğru, diğerinin uç noktalarını ayırır; dolayısıyla her uç nokta, diğer üçünün oluşturduğu üçgenin dışındadır. Böylece iddia kanıtlanmış olur.
Şimdi \(q\), verilen \(n\) noktanın belirlediği dışbükey dörtgenlerin sayısı olsun. \(S\)'nin verilen noktalardan beşini içeren bir küme, \(Q\)'nun ise köşeleri \(S\)'ye ait bir dışbükey dörtgen olduğu \((S,Q)\) çiftlerini sayalım.
İddiaya göre, \(S\) için \(\binom n5\) seçimin her biri en az bir çift verir. Öte yandan her \(Q\) dörtgeni, kalan noktalardan birinin eklenmesiyle elde edilen tam olarak \(n-4\) tane böyle \(S\) kümesine aittir. Dolayısıyla \[ (n-4)q\geq \binom n5, \] ve buradan \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120} \] elde edilir.
Son olarak, \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] Bu ifade her \(n\geq5\) tam sayısı için negatif değildir: \(n=5,6\) için sıfır, \(n\geq7\) için ise pozitiftir. Sonuç olarak, \[ \boxed{q\geq \binom{n-3}{2}}. \]
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1969 · Problema 5
Se dan \(n > 4\) puntos en el plano tales que no hay tres alineados. Demuestre que existen al menos \(\binom{n-3}{2}\) cuadriláteros convexos cuyos vértices son cuatro de los puntos dados.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Primero demostramos que entre cualesquiera cinco puntos del plano, sin tres alineados, hay cuatro que son los vértices de un cuadrilátero convexo.
Si su envolvente convexa tiene al menos cuatro vértices, elegimos cuatro cualesquiera de ellos. Estos forman un cuadrilátero convexo, pues ninguno puede estar en el triángulo formado por los otros tres.
En caso contrario, su envolvente convexa es un triángulo \(ABC\), y los puntos restantes \(D,E\) están estrictamente en su interior. Los segmentos \(AD,BD,CD\) dividen \(ABC\) en tres triángulos. Como no hay tres puntos alineados, \(E\) está estrictamente en el interior de uno de estos triángulos; cambiando las denominaciones de \(A,B,C\), suponemos que está en el interior de \(ABD\).
El segmento \(CE\) comienza fuera del triángulo \(ABD\) y termina en su interior, por lo que cruza su frontera. No puede cruzar \(AB\), porque \(C\) y \(E\) están estrictamente del mismo lado de la recta \(AB\). Por tanto, \(CE\) cruza \(AD\) o \(BD\). El punto de cruce está en el interior de ambos segmentos: si pasara por un vértice, habría tres puntos dados alineados.
Los cuatro extremos de dos segmentos que se cruzan de esta manera forman un cuadrilátero convexo. En efecto, la recta que contiene cualquiera de los segmentos separa los extremos del otro, por lo que cada extremo está fuera del triángulo formado por los otros tres. Esto demuestra la afirmación.
Sea ahora \(q\) el número de cuadriláteros convexos determinados por los \(n\) puntos dados. Contamos los pares \((S,Q)\), donde \(S\) es un conjunto de cinco puntos dados y \(Q\) es un cuadrilátero convexo cuyos vértices pertenecen a \(S\).
Por la afirmación anterior, cada una de las \(\binom n5\) elecciones de \(S\) aporta al menos un par. Por otra parte, cada cuadrilátero \(Q\) pertenece exactamente a \(n-4\) de estos conjuntos \(S\), que se obtienen añadiendo uno de los puntos restantes. Por tanto, \[ (n-4)q\geq \binom n5, \] y, en consecuencia, \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
Finalmente, \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] Esta expresión es no negativa para todo entero \(n\geq5\): es cero para \(n=5,6\) y positiva para \(n\geq7\). En consecuencia, \[ \boxed{q\geq \binom{n-3}{2}}. \]
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1969 · 问题 5
平面上给定 \(n > 4\) 个点，其中任意三点不共线。证明：以给定点中的四个点为顶点的凸四边形至少有 \(\binom{n-3}{2}\) 个。
题目译自官方英文原文。 官方试卷 (PDF)
解答
先证明：平面上任意五个点，若其中任意三点不共线，则其中必有四个点是某个凸四边形的顶点。
若这五个点的凸包至少有四个顶点，任取其中四个顶点。它们构成一个凸四边形，因为其中任何一点都不可能位于其余三点所构成的三角形内。
否则，它们的凸包是一个三角形 \(ABC\)，其余两点 \(D,E\) 严格位于其内部。线段 \(AD,BD,CD\) 将 \(ABC\) 分成三个三角形。由于任意三点不共线，\(E\) 严格位于这三个三角形之一的内部；重新标记 \(A,B,C\)，不妨设它位于 \(ABD\) 内部。
线段 \(CE\) 的起点位于三角形 \(ABD\) 外部，终点位于其内部，所以它与该三角形的边界相交。它不可能与 \(AB\) 相交，因为 \(C\) 和 \(E\) 严格位于直线 \(AB\) 的同一侧。因此，\(CE\) 与 \(AD\) 或 \(BD\) 相交。交点位于两条线段各自的内部：若经过一个顶点，就会使三个给定点共线。
这样相交的两条线段的四个端点构成一个凸四边形。事实上，任一线段所在的直线都将另一线段的两个端点分隔在两侧，因此每个端点都位于其余三点构成的三角形之外。这就证明了上述结论。
现在设 \(q\) 为给定的 \(n\) 个点所确定的凸四边形个数。计算二元组 \((S,Q)\) 的个数，其中 \(S\) 是由五个给定点组成的集合，\(Q\) 是顶点都属于 \(S\) 的凸四边形。
根据上述结论，\(S\) 的 \(\binom n5\) 种选择中，每一种都至少贡献一个二元组。反过来，每个四边形 \(Q\) 恰好属于 \(n-4\) 个这样的集合 \(S\)，这些集合由其四个顶点添入其余点中的一个而得到。因此 \[ (n-4)q\geq \binom n5, \] 从而 \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
最后， \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] 对于每个整数 \(n\geq5\)，此式均非负：当 \(n=5,6\) 时为零，当 \(n\geq7\) 时为正。因此， \[ \boxed{q\geq \binom{n-3}{2}}. \]
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1969 · Задача 5
На плоскости даны \(n > 4\) точек, никакие три из которых не лежат на одной прямой. Докажите, что существует не менее \(\binom{n-3}{2}\) выпуклых четырёхугольников, вершинами которых служат четыре из данных точек.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Сначала докажем, что среди любых пяти точек плоскости, никакие три из которых не лежат на одной прямой, найдутся четыре вершины выпуклого четырёхугольника.
Если их выпуклая оболочка имеет хотя бы четыре вершины, выберем любые четыре из этих вершин. Они образуют выпуклый четырёхугольник, поскольку ни одна из них не может лежать в треугольнике, образованном остальными тремя.
В противном случае их выпуклая оболочка — треугольник \(ABC\), а оставшиеся точки \(D,E\) лежат строго внутри него. Отрезки \(AD,BD,CD\) разбивают \(ABC\) на три треугольника. Поскольку никакие три точки не лежат на одной прямой, \(E\) лежит строго внутри одного из этих треугольников; переобозначив \(A,B,C\), будем считать, что она лежит внутри \(ABD\).
Отрезок \(CE\) начинается вне треугольника \(ABD\) и заканчивается внутри него, поэтому он пересекает его границу. Он не может пересекать \(AB\), поскольку \(C\) и \(E\) лежат строго по одну сторону от прямой \(AB\). Значит, \(CE\) пересекает \(AD\) или \(BD\). Точка пересечения лежит внутри обоих отрезков: прохождение через вершину означало бы, что три данные точки лежат на одной прямой.
Четыре конца двух таких пересекающихся отрезков образуют выпуклый четырёхугольник. Действительно, прямая, содержащая любой из этих отрезков, разделяет концы другого, поэтому каждый конец лежит вне треугольника, образованного остальными тремя. Утверждение доказано.
Теперь пусть \(q\) — число выпуклых четырёхугольников, определяемых данными \(n\) точками. Подсчитаем пары \((S,Q)\), где \(S\) — множество из пяти данных точек, а \(Q\) — выпуклый четырёхугольник, вершины которого принадлежат \(S\).
По доказанному утверждению каждый из \(\binom n5\) вариантов выбора \(S\) даёт хотя бы одну пару. С другой стороны, каждый четырёхугольник \(Q\) принадлежит ровно \(n-4\) таким множествам \(S\), получаемым добавлением одной из оставшихся точек. Поэтому \[ (n-4)q\geq \binom n5, \] и, следовательно, \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
Наконец, \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] Это выражение неотрицательно для любого целого \(n\geq5\): оно равно нулю при \(n=5,6\) и положительно при \(n\geq7\). Следовательно, \[ \boxed{q\geq \binom{n-3}{2}}. \]
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1969 · المسألة 5
أُعطيت \(n > 4\) نقاط في المستوى، لا تقع أي ثلاث منها على استقامة واحدة. أثبت أن هناك ما لا يقل عن \(\binom{n-3}{2}\) رباعيًا محدبًا رؤوس كل منها أربع من النقاط المعطاة.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نثبت أولًا أن أي خمس نقاط في المستوى، لا تقع أي ثلاث منها على استقامة واحدة، تحتوي على أربع نقاط تشكّل رؤوس رباعي محدب.
إذا كان لغلافها المحدب أربعة رؤوس على الأقل، نختار أي أربعة من تلك الرؤوس. وهي تشكّل رباعيًا محدبًا، إذ لا يمكن أن يقع أي منها في المثلث الذي تشكّله الثلاثة الأخرى.
وإلا فإن غلافها المحدب مثلث \(ABC\)، وتقع النقطتان الباقيتان \(D,E\) في داخله تمامًا. تقسّم القطع \(AD,BD,CD\) المثلث \(ABC\) إلى ثلاثة مثلثات. وبما أن أي ثلاث نقاط لا تقع على استقامة واحدة، فإن \(E\) تقع في داخل أحد هذه المثلثات تمامًا؛ وبإعادة تسمية \(A,B,C\)، نفترض أنها تقع داخل \(ABD\).
تبدأ القطعة \(CE\) خارج المثلث \(ABD\) وتنتهي داخله، لذا فهي تقطع حدوده. ولا يمكنها أن تقطع \(AB\)، لأن \(C\) و\(E\) تقعان تمامًا في جهة واحدة من المستقيم \(AB\). ومن ثم فإن \(CE\) تقطع \(AD\) أو \(BD\). وتقع نقطة التقاطع في داخل كلتا القطعتين: إذ إن المرور برأس يجعل ثلاثًا من النقاط المعطاة على استقامة واحدة.
تشكّل النهايات الأربع لقطعتين متقاطعتين بهذه الصورة رباعيًا محدبًا. بالفعل، يفصل المستقيم الحامل لكل من القطعتين بين نهايتي القطعة الأخرى، لذا تقع كل نهاية خارج المثلث الذي تشكّله النهايات الثلاث الأخرى. وهذا يثبت الادعاء.
لنرمز الآن بـ\(q\) إلى عدد الرباعيات المحدبة التي تحددها النقاط المعطاة وعددها \(n\). نعدّ الأزواج \((S,Q)\)، حيث \(S\) مجموعة من خمس نقاط معطاة، و\(Q\) رباعي محدب تنتمي رؤوسه إلى \(S\).
وفقًا للادعاء، يساهم كل اختيار من الاختيارات \(\binom n5\) للمجموعة \(S\) بزوج واحد على الأقل. ومن جهة أخرى، ينتمي كل رباعي \(Q\) إلى \(n-4\) مجموعة من هذه المجموعات \(S\) بالضبط، نحصل عليها بإضافة إحدى النقاط الباقية. ولذلك \[ (n-4)q\geq \binom n5, \] ومن ثم \[ q\geq \frac{\binom n5}{n-4} =\frac{n(n-1)(n-2)(n-3)}{120}. \]
وأخيرًا، \[ \frac{n(n-1)(n-2)(n-3)}{120} -\binom{n-3}{2} = \frac{(n-3)(n-5)(n-6)(n+8)}{120}. \] هذا المقدار غير سالب لكل عدد صحيح \(n\geq5\): فهو يساوي صفرًا عندما \(n=5,6\)، ويكون موجبًا عندما \(n\geq7\). وبالتالي، \[ \boxed{q\geq \binom{n-3}{2}}. \]
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).