IMO 1992 · Problem 3
Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of \(n\) such that whenever exactly \(n\) edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.
Official text of the problem. Official problem paper (PDF)
Answer
\[ \boxed{n=33}. \]
Solution
No three of the points are collinear: otherwise those three together with any fourth point would be coplanar. Thus every three points determine a nondegenerate triangle.
First, \(33\) colored edges always suffice. There are \[ \binom{9}{2}=36 \] edges altogether, so exactly three edges are uncolored. Choose one endpoint of each uncolored edge and remove all the chosen points. At most three points are removed, leaving at least six points with every edge between them colored.
Choose six of these points and fix one of them, \(P\). Of the five edges joining \(P\) to the other points, at least three have the same color, say red. Denote their other endpoints by \(A,B,C\). If any of \(AB,BC,CA\) is red, it forms a red triangle with \(P\). Otherwise all three are blue, and \(ABC\) is a blue triangle. Hence \(33\) colored edges guarantee a monochromatic triangle.
Next, \(32\) colored edges need not suffice. Partition the nine points into five groups \[ V_0,V_1,V_2,V_3,V_4 \] of sizes \(2,2,2,2,1\), respectively. Leave edges within each group uncolored. For points in distinct groups \(V_i,V_j\), color their edge:
- red if \(j-i\equiv \pm1\pmod 5\);
- blue if \(j-i\equiv \pm2\pmod 5\).
Exactly four edges are uncolored, one within each two-point group. Thus there are \(36-4=32\) colored edges.
Any triangle whose three edges are colored must have its vertices in three distinct groups. Suppose one vertex belongs to \(V_i\).
If the triangle were entirely red, the other two vertices would have to belong to \(V_{i-1}\) and \(V_{i+1}\). But the edge between those groups is blue, since their indices differ by \(2\).
If the triangle were entirely blue, the other two vertices would have to belong to \(V_{i-2}\) and \(V_{i+2}\). But the edge between those groups is red, since their indices differ by \(4\equiv-1\pmod5\).
Consequently this coloring has no monochromatic triangle. Uncoloring further edges gives such an example with any smaller number of colored edges. Therefore the smallest required value is \(\boxed{33}\).
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1992 · Aufgabe 3
Gegeben seien neun Punkte im Raum, von denen keine vier in einer Ebene liegen. Je zwei Punkte werden durch eine Kante (also eine Strecke) verbunden, und jede Kante wird entweder blau oder rot gefärbt oder bleibt ungefärbt. Bestimme den kleinsten Wert von \(n\), für den gilt: Sind genau \(n\) Kanten gefärbt, so enthält die Menge der gefärbten Kanten notwendigerweise ein Dreieck, dessen Kanten alle dieselbe Farbe haben.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
\[ \boxed{n=33}. \]
Lösung
Keine drei der Punkte liegen auf einer Geraden: Andernfalls würden diese drei zusammen mit einem beliebigen vierten Punkt in einer Ebene liegen. Somit bestimmen je drei Punkte ein nicht entartetes Dreieck.
Zunächst zeigen wir, dass \(33\) gefärbte Kanten stets ausreichen. Insgesamt gibt es \[ \binom{9}{2}=36 \] Kanten, also sind genau drei Kanten ungefärbt. Wir wählen von jeder ungefärbten Kante einen Endpunkt und entfernen alle gewählten Punkte. Dabei werden höchstens drei Punkte entfernt, sodass mindestens sechs Punkte übrig bleiben, zwischen denen jede Kante gefärbt ist.
Wir wählen sechs dieser Punkte und halten einen davon, \(P\), fest. Von den fünf Kanten, die \(P\) mit den anderen Punkten verbinden, haben mindestens drei dieselbe Farbe, etwa Rot. Ihre anderen Endpunkte bezeichnen wir mit \(A,B,C\). Ist eine der Kanten \(AB,BC,CA\) rot, so bildet sie mit \(P\) ein rotes Dreieck. Andernfalls sind alle drei blau, und \(ABC\) ist ein blaues Dreieck. Somit garantieren \(33\) gefärbte Kanten ein einfarbiges Dreieck.
Als Nächstes zeigen wir, dass \(32\) gefärbte Kanten nicht ausreichen müssen. Wir teilen die neun Punkte in fünf Gruppen \[ V_0,V_1,V_2,V_3,V_4 \] mit jeweils \(2,2,2,2,1\) Punkten ein. Die Kanten innerhalb jeder Gruppe lassen wir ungefärbt. Die Kante zwischen Punkten aus verschiedenen Gruppen \(V_i,V_j\) färben wir:
- rot, falls \(j-i\equiv \pm1\pmod 5\);
- blau, falls \(j-i\equiv \pm2\pmod 5\).
Genau vier Kanten sind ungefärbt, jeweils eine innerhalb jeder Gruppe aus zwei Punkten. Somit gibt es \(36-4=32\) gefärbte Kanten.
Jedes Dreieck, dessen drei Kanten gefärbt sind, muss seine Eckpunkte in drei verschiedenen Gruppen haben. Ein Eckpunkt gehöre zu \(V_i\).
Wäre das Dreieck vollständig rot, so müssten die anderen beiden Eckpunkte zu \(V_{i-1}\) und \(V_{i+1}\) gehören. Die Kante zwischen diesen Gruppen ist jedoch blau, da sich ihre Indizes um \(2\) unterscheiden.
Wäre das Dreieck vollständig blau, so müssten die anderen beiden Eckpunkte zu \(V_{i-2}\) und \(V_{i+2}\) gehören. Die Kante zwischen diesen Gruppen ist jedoch rot, da sich ihre Indizes um \(4\equiv-1\pmod5\) unterscheiden.
Folglich enthält diese Färbung kein einfarbiges Dreieck. Entfernt man die Farbe weiterer Kanten, so erhält man ein solches Beispiel mit jeder kleineren Anzahl gefärbter Kanten. Daher ist der gesuchte kleinste Wert \(\boxed{33}\).
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1992 · Soru 3
Uzayda herhangi dördü aynı düzlemde bulunmayan dokuz nokta veriliyor. Her nokta çifti bir kenarla (yani bir doğru parçasıyla) birleştiriliyor ve her kenar ya maviye ya kırmızıya boyanıyor ya da boyanmadan bırakılıyor. Tam olarak \(n\) kenar boyandığında, boyalı kenarlar kümesinin mutlaka tüm kenarları aynı renkte olan bir üçgen içermesini sağlayan en küçük \(n\) değerini bulunuz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
\[ \boxed{n=33}. \]
Çözüm
Noktaların herhangi üçü doğrusal değildir: aksi takdirde bu üç nokta, herhangi bir dördüncü noktayla birlikte aynı düzlemde olurdu. Dolayısıyla her üç nokta dejenere olmayan bir üçgen belirler.
Önce, \(33\) boyalı kenarın her zaman yeterli olduğunu gösterelim. Toplam \[ \binom{9}{2}=36 \] kenar olduğundan tam olarak üç kenar boyasızdır. Her boyasız kenarın bir uç noktasını seçip seçilen tüm noktaları çıkaralım. En fazla üç nokta çıkarıldığı için geriye, aralarındaki tüm kenarlar boyalı olan en az altı nokta kalır.
Bu noktalardan altısını seçip bunlardan birini \(P\) olarak sabitleyelim. \(P\)'yi diğer noktalara birleştiren beş kenarın en az üçü aynı renktedir; bu renk kırmızı olsun. Bu kenarların diğer uç noktalarını \(A,B,C\) ile gösterelim. \(AB,BC,CA\) kenarlarından herhangi biri kırmızıysa \(P\) ile birlikte kırmızı bir üçgen oluşturur. Aksi takdirde üçü de mavidir ve \(ABC\) mavi bir üçgendir. O hâlde \(33\) boyalı kenar, tek renkli bir üçgenin varlığını garanti eder.
Şimdi, \(32\) boyalı kenarın yeterli olmayabileceğini gösterelim. Dokuz noktayı, eleman sayıları sırasıyla \(2,2,2,2,1\) olan \[ V_0,V_1,V_2,V_3,V_4 \] şeklinde beş gruba ayıralım. Her grubun içindeki kenarları boyasız bırakalım. Farklı \(V_i,V_j\) gruplarındaki noktaları birleştiren kenarı:
- \(j-i\equiv \pm1\pmod 5\) ise kırmızıya;
- \(j-i\equiv \pm2\pmod 5\) ise maviye boyayalım.
Her iki noktalı grubun içinde bir tane olmak üzere tam olarak dört kenar boyasızdır. Dolayısıyla \(36-4=32\) boyalı kenar vardır.
Üç kenarı da boyalı olan herhangi bir üçgenin köşeleri üç farklı grupta bulunmalıdır. Köşelerden birinin \(V_i\)'ye ait olduğunu varsayalım.
Üçgenin tüm kenarları kırmızı olsaydı diğer iki köşenin \(V_{i-1}\) ve \(V_{i+1}\)'e ait olması gerekirdi. Ancak bu grupların indisleri arasındaki fark \(2\) olduğundan aralarındaki kenar mavidir.
Üçgenin tüm kenarları mavi olsaydı diğer iki köşenin \(V_{i-2}\) ve \(V_{i+2}\)'ye ait olması gerekirdi. Ancak bu grupların indisleri arasındaki fark \(4\equiv-1\pmod5\) olduğundan aralarındaki kenar kırmızıdır.
Sonuç olarak bu boyamada tek renkli üçgen yoktur. Daha fazla kenarın boyasını kaldırarak, boyalı kenar sayısının daha küçük herhangi bir değeri için de böyle bir örnek elde edilir. Dolayısıyla istenen en küçük değer \(\boxed{33}\)'tür.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1992 · Problema 3
Consideremos nueve puntos en el espacio, de los cuales no hay cuatro coplanarios. Cada par de puntos se une mediante una arista (es decir, un segmento de recta), y cada arista se colorea de azul o de rojo, o se deja sin colorear. Hallar el menor valor de \(n\) tal que, siempre que se coloreen exactamente \(n\) aristas, el conjunto de aristas coloreadas contenga necesariamente un triángulo cuyas aristas sean todas del mismo color.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
\[ \boxed{n=33}. \]
Solución
No hay tres puntos colineales: de lo contrario, esos tres puntos junto con cualquier cuarto punto serían coplanarios. Por tanto, cada tres puntos determinan un triángulo no degenerado.
Primero, \(33\) aristas coloreadas siempre bastan. Hay \[ \binom{9}{2}=36 \] aristas en total, por lo que quedan exactamente tres aristas sin colorear. Elijamos un extremo de cada arista sin colorear y eliminemos todos los puntos elegidos. Se eliminan a lo sumo tres puntos, por lo que quedan al menos seis puntos con todas las aristas que los unen coloreadas.
Elijamos seis de estos puntos y fijemos uno de ellos, \(P\). De las cinco aristas que unen \(P\) con los demás puntos, al menos tres tienen el mismo color, digamos rojo. Denotemos sus otros extremos por \(A,B,C\). Si alguna de las aristas \(AB,BC,CA\) es roja, forma un triángulo rojo con \(P\). En caso contrario, las tres son azules, y \(ABC\) es un triángulo azul. Por tanto, \(33\) aristas coloreadas garantizan un triángulo monocromático.
A continuación, \(32\) aristas coloreadas no siempre bastan. Dividamos los nueve puntos en cinco grupos \[ V_0,V_1,V_2,V_3,V_4 \] de tamaños \(2,2,2,2,1\), respectivamente. Dejemos sin colorear las aristas que unen puntos de un mismo grupo. Para los puntos de grupos distintos \(V_i,V_j\), coloreemos la arista que los une:
- de rojo si \(j-i\equiv \pm1\pmod 5\);
- de azul si \(j-i\equiv \pm2\pmod 5\).
Quedan exactamente cuatro aristas sin colorear, una en cada grupo de dos puntos. Por tanto, hay \(36-4=32\) aristas coloreadas.
Cualquier triángulo cuyas tres aristas estén coloreadas debe tener sus vértices en tres grupos distintos. Supongamos que un vértice pertenece a \(V_i\).
Si el triángulo fuera enteramente rojo, los otros dos vértices tendrían que pertenecer a \(V_{i-1}\) y \(V_{i+1}\). Pero la arista entre esos grupos es azul, pues sus índices difieren en \(2\).
Si el triángulo fuera enteramente azul, los otros dos vértices tendrían que pertenecer a \(V_{i-2}\) y \(V_{i+2}\). Pero la arista entre esos grupos es roja, pues sus índices difieren en \(4\equiv-1\pmod5\).
En consecuencia, esta coloración no contiene ningún triángulo monocromático. Al quitar el color a más aristas se obtiene un ejemplo de este tipo con cualquier número menor de aristas coloreadas. Por tanto, el menor valor requerido es \(\boxed{33}\).
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1992 · 问题 3
空间中有九个点，其中任意四点不共面。将每对点用一条边（即线段）连接，并将每条边染成蓝色、染成红色或不染色。求 \(n\) 的最小值，使得只要恰有 \(n\) 条边被染色，染色边中就必然包含一个三条边颜色相同的三角形。
题目译自官方英文原文。 官方试卷 (PDF)
答案
\[ \boxed{n=33}. \]
解答
这些点中任意三点不共线：否则，这三个点与任意第四个点都会共面。因此，任意三个点都确定一个非退化三角形。
首先，染色边数为 \(33\) 时总能保证结论成立。 边的总数为 \[ \binom{9}{2}=36 \] 条，因此恰有三条边未染色。从每条未染色的边中选取一个端点，并删去所有选中的点。至多删去三个点，故至少剩下六个点，且它们之间的每条边都已染色。
从这些点中选取六个，并固定其中一点 \(P\)。连接 \(P\) 与其余各点的五条边中，至少有三条颜色相同，不妨设为红色。将这三条边的另一个端点分别记为 \(A,B,C\)。若 \(AB,BC,CA\) 中有任意一条是红色，它就与 \(P\) 构成一个红色三角形。否则，这三条边全为蓝色，\(ABC\) 就是一个蓝色三角形。因此，\(33\) 条染色边能保证存在单色三角形。
其次，\(32\) 条染色边未必足够。 将九个点分为五组 \[ V_0,V_1,V_2,V_3,V_4 \] 各组的点数依次为 \(2,2,2,2,1\)。同组内的边不染色。对于不同组 \(V_i,V_j\) 中的点，将它们之间的边按如下规则染色：
- 若 \(j-i\equiv \pm1\pmod 5\)，则染成红色；
- 若 \(j-i\equiv \pm2\pmod 5\)，则染成蓝色。
恰有四条边未染色，即每个含两个点的组内各有一条。因此，染色边共有 \(36-4=32\) 条。
任意一个三条边都已染色的三角形，其顶点必定属于三个不同的组。设其中一个顶点属于 \(V_i\)。
若该三角形全为红色，则另外两个顶点必须分别属于 \(V_{i-1}\) 和 \(V_{i+1}\)。但这两组之间的边为蓝色，因为它们的下标相差 \(2\)。
若该三角形全为蓝色，则另外两个顶点必须分别属于 \(V_{i-2}\) 和 \(V_{i+2}\)。但这两组之间的边为红色，因为它们的下标相差 \(4\equiv-1\pmod5\)。
因此，这种染色不存在单色三角形。继续去掉一些边的颜色，就能得到染色边数为任意更小数目的此类例子。因此，所求最小值为 \(\boxed{33}\)。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1992 · Задача 3
Даны девять точек в пространстве, никакие четыре из которых не лежат в одной плоскости. Каждая пара точек соединена ребром (то есть отрезком), и каждое ребро либо окрашено в синий или красный цвет, либо не окрашено. Найдите наименьшее значение \(n\), при котором, если окрашено ровно \(n\) рёбер, среди окрашенных рёбер обязательно найдётся треугольник, все рёбра которого имеют один и тот же цвет.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
\[ \boxed{n=33}. \]
Решение
Никакие три из данных точек не лежат на одной прямой: иначе эти три точки вместе с любой четвёртой лежали бы в одной плоскости. Таким образом, любые три точки задают невырожденный треугольник.
Сначала покажем, что \(33\) окрашенных рёбер всегда достаточно. Всего имеется \[ \binom{9}{2}=36 \] рёбер, поэтому ровно три ребра не окрашены. Выберем по одному концу каждого неокрашенного ребра и удалим все выбранные точки. Будет удалено не более трёх точек, так что останется не менее шести точек, все рёбра между которыми окрашены.
Выберем шесть из этих точек и зафиксируем одну из них, \(P\). Среди пяти рёбер, соединяющих \(P\) с остальными точками, хотя бы три имеют один и тот же цвет, скажем красный. Обозначим их другие концы через \(A,B,C\). Если хотя бы одно из рёбер \(AB,BC,CA\) красное, то вместе с \(P\) оно образует красный треугольник. В противном случае все три ребра синие, и \(ABC\) — синий треугольник. Следовательно, \(33\) окрашенных ребра гарантируют наличие одноцветного треугольника.
Теперь покажем, что \(32\) окрашенных рёбер может быть недостаточно. Разобьём девять точек на пять групп \[ V_0,V_1,V_2,V_3,V_4 \] численности \(2,2,2,2,1\) соответственно. Рёбра внутри каждой группы оставим неокрашенными. Ребро, соединяющее точки из различных групп \(V_i,V_j\), окрасим:
- в красный цвет, если \(j-i\equiv \pm1\pmod 5\);
- в синий цвет, если \(j-i\equiv \pm2\pmod 5\).
Неокрашенными остаются ровно четыре ребра, по одному внутри каждой группы из двух точек. Таким образом, окрашено \(36-4=32\) ребра.
У любого треугольника, все три ребра которого окрашены, вершины должны принадлежать трём различным группам. Пусть одна из вершин принадлежит \(V_i\).
Если бы треугольник был целиком красным, то две другие вершины должны были бы принадлежать \(V_{i-1}\) и \(V_{i+1}\). Но ребро между этими группами синее, поскольку их индексы отличаются на \(2\).
Если бы треугольник был целиком синим, то две другие вершины должны были бы принадлежать \(V_{i-2}\) и \(V_{i+2}\). Но ребро между этими группами красное, поскольку их индексы отличаются на \(4\equiv-1\pmod5\).
Следовательно, в этой раскраске нет одноцветного треугольника. Снимая окраску с дополнительных рёбер, получаем такой пример с любым меньшим числом окрашенных рёбер. Поэтому наименьшее искомое значение равно \(\boxed{33}\).
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1992 · المسألة 3
لتكن لدينا تسع نقاط في الفضاء، لا تقع أي أربع منها في مستوى واحد. نصل كل زوج من النقاط بحافة (أي قطعة مستقيمة)، ونلوّن كل حافة بالأزرق أو بالأحمر أو نتركها دون تلوين. أوجد أصغر قيمة لـ\(n\) بحيث، كلما لوّنا \(n\) حافة بالضبط، احتوت مجموعة الحواف الملوّنة بالضرورة على مثلث جميع حوافه من اللون نفسه.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
\[ \boxed{n=33}. \]
الحل
لا تقع أي ثلاث من النقاط على استقامة واحدة: وإلا لوقعت هذه النقاط الثلاث مع أي نقطة رابعة في مستوى واحد. ومن ثم تحدد كل ثلاث نقاط مثلثًا غير منعدم المساحة.
أولًا، يكفي دائمًا تلوين \(33\) حافة. يبلغ عدد الحواف الكلي \[ \binom{9}{2}=36 \] حافة، لذا تبقى ثلاث حواف بالضبط دون تلوين. نختار أحد طرفي كل حافة غير ملوّنة ونحذف جميع النقاط المختارة. بذلك نحذف ثلاث نقاط على الأكثر، وتبقى ست نقاط على الأقل، كل حافة تصل بين اثنتين منها ملوّنة.
نختار ستًا من هذه النقاط ونثبت إحداها، \(P\). من بين الحواف الخمس التي تصل \(P\) بالنقاط الأخرى، توجد ثلاث على الأقل من اللون نفسه، وليكن الأحمر. نرمز إلى أطرافها الأخرى بـ\(A,B,C\). إذا كانت أي من الحواف \(AB,BC,CA\) حمراء، فإنها تشكل مع \(P\) مثلثًا أحمر. وإلا كانت الحواف الثلاث جميعها زرقاء، وكان \(ABC\) مثلثًا أزرق. إذن يضمن تلوين \(33\) حافة وجود مثلث أحادي اللون.
ثانيًا، قد لا يكفي تلوين \(32\) حافة. نقسّم النقاط التسع إلى خمس مجموعات \[ V_0,V_1,V_2,V_3,V_4 \] أعداد عناصرها \(2,2,2,2,1\)، على الترتيب. نترك الحواف داخل كل مجموعة دون تلوين. أما النقطتان اللتان تنتميان إلى مجموعتين مختلفتين \(V_i,V_j\)، فنلوّن الحافة بينهما:
- بالأحمر إذا كان \(j-i\equiv \pm1\pmod 5\)؛
- بالأزرق إذا كان \(j-i\equiv \pm2\pmod 5\).
تبقى أربع حواف بالضبط دون تلوين، واحدة داخل كل مجموعة ذات نقطتين. لذا يكون عدد الحواف الملوّنة \(36-4=32\).
كل مثلث حوافه الثلاث ملوّنة لا بد أن تقع رؤوسه في ثلاث مجموعات مختلفة. لنفترض أن أحد رؤوسه ينتمي إلى \(V_i\).
لو كان المثلث أحمر بالكامل، لوجب أن ينتمي الرأسان الآخران إلى \(V_{i-1}\) و\(V_{i+1}\). لكن الحافة بين هاتين المجموعتين زرقاء، لأن الفرق بين دليليهما هو \(2\).
ولو كان المثلث أزرق بالكامل، لوجب أن ينتمي الرأسان الآخران إلى \(V_{i-2}\) و\(V_{i+2}\). لكن الحافة بين هاتين المجموعتين حمراء، لأن الفرق بين دليليهما هو \(4\equiv-1\pmod5\).
وبالتالي لا يوجد في هذا التلوين أي مثلث أحادي اللون. وبإزالة اللون عن مزيد من الحواف نحصل على مثال مماثل لأي عدد أصغر من الحواف الملوّنة. إذن أصغر قيمة مطلوبة هي \(\boxed{33}\).
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).