IMO 1978 · Problem 6
An international society has its members from six different countries. The list of members contains 1978 names, numbered \(1, 2, \ldots, 1978\). Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
Official text of the problem. Official problem paper (PDF)
Solution
Assign a different color to each country. Form a complete graph with vertices \[ 0,1,2,\ldots,1978, \] and color the edge joining \(i\) and \(j\) according to the country of the member numbered \(|i-j|\).
A triangle whose three edges have the same color gives the desired conclusion. Indeed, write its vertices as \(x<y<z\). The members numbered \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] then belong to the same country, and \(c=a+b\). If \(a\ne b\), this is the first alternative in the problem; if \(a=b\), then \(c=2a\), giving the second alternative.
It therefore suffices to prove that our graph contains such a triangle.
Suppose, for a contradiction, that it does not. We use the following observation: if a complete subgraph has \(m\) vertices and its edges use at most \(r\) colors, it contains a complete subgraph with at least \[ \left\lceil\frac{m-1}{r}\right\rceil \] vertices whose edges use at most \(r-1\) colors.
To prove the observation, choose a vertex \(v\). By the pigeonhole principle, at least \(\lceil(m-1)/r\rceil\) edges from \(v\) have one common color. Let \(T\) be their other endpoints. No edge between two vertices of \(T\) can have that color, since it would form a triangle of that color together with \(v\). Thus the edges within \(T\) use at most the other \(r-1\) colors, proving the observation.
Starting with our \(1979\) vertices and six colors, apply this observation repeatedly:
| Maximum number of colors | Guaranteed number of vertices |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
The last subgraph has at least three vertices and all its edges have the same color. Any three of its vertices therefore form a triangle of that color, contradicting our supposition.
Consequently such a triangle exists, and the corresponding members satisfy one of the two required alternatives. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1978 · Aufgabe 6
Die Mitglieder einer internationalen Gesellschaft stammen aus sechs verschiedenen Ländern. Die Mitgliederliste enthält 1978 Namen, die mit \(1, 2, \ldots, 1978\) nummeriert sind. Beweise, dass es mindestens ein Mitglied gibt, dessen Nummer die Summe der Nummern zweier Mitglieder aus seinem eigenen Land oder doppelt so groß wie die Nummer eines Mitglieds aus seinem eigenen Land ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Ordne jedem Land eine andere Farbe zu. Bilde einen vollständigen Graphen mit den Knoten \[ 0,1,2,\ldots,1978, \] und färbe die Kante zwischen \(i\) und \(j\) entsprechend dem Herkunftsland des Mitglieds mit der Nummer \(|i-j|\).
Ein Dreieck, dessen drei Kanten dieselbe Farbe haben, liefert die gewünschte Schlussfolgerung. Bezeichne dazu seine Knoten mit \(x<y<z\). Die Mitglieder mit den Nummern \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] stammen dann aus demselben Land, und es gilt \(c=a+b\). Falls \(a\ne b\), ist dies die erste Alternative der Aufgabe; falls \(a=b\), gilt \(c=2a\), was die zweite Alternative ergibt.
Es genügt daher zu beweisen, dass unser Graph ein solches Dreieck enthält.
Nehmen wir zum Widerspruch an, dass dies nicht der Fall ist. Wir verwenden die folgende Beobachtung: Wenn ein vollständiger Teilgraph \(m\) Knoten hat und seine Kanten mit höchstens \(r\) Farben gefärbt sind, enthält er einen vollständigen Teilgraphen mit mindestens \[ \left\lceil\frac{m-1}{r}\right\rceil \] Knoten, dessen Kanten mit höchstens \(r-1\) Farben gefärbt sind.
Um die Beobachtung zu beweisen, wähle einen Knoten \(v\). Nach dem Schubfachprinzip haben mindestens \(\lceil(m-1)/r\rceil\) von \(v\) ausgehende Kanten eine gemeinsame Farbe. Sei \(T\) die Menge ihrer anderen Endpunkte. Keine Kante zwischen zwei Knoten aus \(T\) kann diese Farbe haben, da sie zusammen mit \(v\) ein Dreieck dieser Farbe bilden würde. Somit werden für die Kanten innerhalb von \(T\) höchstens die übrigen \(r-1\) Farben verwendet, womit die Beobachtung bewiesen ist.
Ausgehend von unseren \(1979\) Knoten und sechs Farben wenden wir diese Beobachtung wiederholt an:
| Höchstzahl der Farben | Garantierte Anzahl der Knoten |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
Der letzte Teilgraph hat mindestens drei Knoten, und alle seine Kanten haben dieselbe Farbe. Je drei seiner Knoten bilden daher ein Dreieck dieser Farbe, im Widerspruch zu unserer Annahme.
Folglich existiert ein solches Dreieck, und die entsprechenden Mitglieder erfüllen eine der beiden geforderten Alternativen. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1978 · Soru 6
Uluslararası bir topluluğun üyeleri altı farklı ülkedendir. Üye listesinde \(1, 2, \ldots, 1978\) ile numaralandırılmış 1978 isim bulunmaktadır. Numarası, kendi ülkesinden iki üyenin numaralarının toplamına veya kendi ülkesinden bir üyenin numarasının iki katına eşit olan en az bir üye bulunduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Her ülkeye farklı bir renk atayalım. Köşeleri \[ 0,1,2,\ldots,1978, \] olan bir tam çizge oluşturalım ve \(i\) ile \(j\)'yi birleştiren kenarı, \(|i-j|\) numaralı üyenin ülkesine göre renklendirelim.
Üç kenarı da aynı renkte olan bir üçgen, istenen sonucu verir. Gerçekten de bu üçgenin köşelerini \(x<y<z\) biçiminde yazalım. Bu durumda \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] numaralı üyeler aynı ülkedendir ve \(c=a+b\) olur. \(a\ne b\) ise sorudaki ilk seçenek sağlanır; \(a=b\) ise \(c=2a\) olur ve ikinci seçenek sağlanır.
Dolayısıyla çizgemizin böyle bir üçgen içerdiğini kanıtlamak yeterlidir.
Çelişki elde etmek için böyle bir üçgen içermediğini varsayalım. Şu gözlemi kullanacağız: Bir tam alt çizgenin \(m\) köşesi varsa ve kenarlarında en fazla \(r\) renk kullanılıyorsa, bu alt çizge, en az \[ \left\lceil\frac{m-1}{r}\right\rceil \] köşesi olan ve kenarlarında en fazla \(r-1\) renk kullanılan bir tam alt çizge içerir.
Bu gözlemi kanıtlamak için bir \(v\) köşesi seçelim. Güvercin yuvası ilkesine göre, \(v\)'den çıkan en az \(\lceil(m-1)/r\rceil\) kenar aynı renktedir. Bu kenarların diğer uç noktalarının kümesi \(T\) olsun. \(T\)'nin iki köşesi arasındaki hiçbir kenar bu renkte olamaz; çünkü böyle bir kenar, \(v\) ile birlikte bu renkte bir üçgen oluştururdu. Dolayısıyla \(T\) içindeki kenarlarda yalnızca diğer \(r-1\) renk kullanılabilir; bu da gözlemi kanıtlar.
\(1979\) köşemiz ve altı rengimizle başlayarak bu gözlemi art arda uygulayalım:
| En fazla renk sayısı | Garanti edilen köşe sayısı |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
Son alt çizgenin en az üç köşesi vardır ve tüm kenarları aynı renktedir. Dolayısıyla herhangi üç köşesi bu renkte bir üçgen oluşturur; bu da varsayımımızla çelişir.
Sonuç olarak böyle bir üçgen vardır ve buna karşılık gelen üyeler, istenen iki seçenekten birini sağlar. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1978 · Problema 6
Una sociedad internacional tiene miembros de seis países distintos. La lista de miembros contiene 1978 nombres, numerados \(1, 2, \ldots, 1978\). Demostrar que existe al menos un miembro cuyo número es la suma de los números de dos miembros de su mismo país, o el doble del número de un miembro de su mismo país.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Asignemos un color distinto a cada país. Construyamos un grafo completo con vértices \[ 0,1,2,\ldots,1978, \] y coloreemos la arista que une \(i\) y \(j\) según el país del miembro cuyo número es \(|i-j|\).
Un triángulo cuyas tres aristas tengan el mismo color da la conclusión deseada. En efecto, escribamos sus vértices como \(x<y<z\). Los miembros cuyos números son \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] pertenecen entonces al mismo país, y \(c=a+b\). Si \(a\ne b\), esta es la primera alternativa del problema; si \(a=b\), entonces \(c=2a\), lo que da la segunda alternativa.
Por tanto, basta demostrar que nuestro grafo contiene un triángulo de este tipo.
Supongamos, por reducción al absurdo, que no lo contiene. Usaremos la siguiente observación: si un subgrafo completo tiene \(m\) vértices y sus aristas usan a lo sumo \(r\) colores, contiene un subgrafo completo con al menos \[ \left\lceil\frac{m-1}{r}\right\rceil \] vértices cuyas aristas usan a lo sumo \(r-1\) colores.
Para demostrar la observación, elijamos un vértice \(v\). Por el principio del palomar, al menos \(\lceil(m-1)/r\rceil\) aristas que parten de \(v\) tienen un mismo color. Sea \(T\) el conjunto de sus otros extremos. Ninguna arista entre dos vértices de \(T\) puede tener ese color, pues formaría, junto con \(v\), un triángulo de ese color. Por tanto, las aristas dentro de \(T\) usan a lo sumo los otros \(r-1\) colores, lo que demuestra la observación.
Partiendo de nuestros \(1979\) vértices y seis colores, apliquemos esta observación repetidamente:
| Número máximo de colores | Número garantizado de vértices |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
El último subgrafo tiene al menos tres vértices y todas sus aristas tienen el mismo color. Por tanto, tres cualesquiera de sus vértices forman un triángulo de ese color, lo que contradice nuestra suposición.
En consecuencia, existe un triángulo de este tipo, y los miembros correspondientes satisfacen una de las dos alternativas requeridas. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1978 · 问题 6
一个国际学会的会员来自六个不同的国家。会员名册上共有 1978 个姓名，编号为 \(1, 2, \ldots, 1978\)。证明：至少有一位会员，其编号等于与他同国的两位会员的编号之和，或等于与他同国的一位会员的编号的两倍。
题目译自官方英文原文。 官方试卷 (PDF)
解答
给每个国家指定一种不同的颜色。构造一个完全图，其顶点为 \[ 0,1,2,\ldots,1978, \] 并根据编号为 \(|i-j|\) 的会员所属的国家，给连接 \(i\) 与 \(j\) 的边着色。
一个三条边颜色相同的三角形即可给出所需的结论。事实上，将它的顶点记为 \(x<y<z\)。那么，编号为 \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] 的会员属于同一个国家，且 \(c=a+b\)。若 \(a\ne b\)，这就是题目中的第一种情形；若 \(a=b\)，则 \(c=2a\)，得到第二种情形。
因此，只需证明我们的图中含有这样的三角形。
用反证法，假设图中没有这样的三角形。我们使用下面的观察结论：若一个完全子图有 \(m\) 个顶点，且其边至多使用 \(r\) 种颜色，则它含有一个完全子图，其顶点数至少为 \[ \left\lceil\frac{m-1}{r}\right\rceil \] 且其边至多使用 \(r-1\) 种颜色。
为证明这一结论，选取一个顶点 \(v\)。由抽屉原理，从 \(v\) 出发的边中，至少有 \(\lceil(m-1)/r\rceil\) 条具有同一种颜色。设 \(T\) 为这些边的另一端点构成的集合。连接 \(T\) 中任意两个顶点的边都不能具有这种颜色，否则它与 \(v\) 一起构成一个这种颜色的三角形。因此，\(T\) 内部的边至多使用其余 \(r-1\) 种颜色，观察结论得证。
从我们的 \(1979\) 个顶点和六种颜色出发，反复应用这一观察结论：
| 颜色种数的上限 | 保证存在的顶点数 |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
最后得到的子图至少有三个顶点，且其所有边的颜色相同。因此，它的任意三个顶点都构成一个这种颜色的三角形，与我们的假设矛盾。
所以，这样的三角形必定存在，而相应的会员满足题目所要求的两种情形之一。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1978 · Задача 6
Члены международного общества представляют шесть различных стран. Список членов общества содержит 1978 имён, пронумерованных числами \(1, 2, \ldots, 1978\). Докажите, что найдётся хотя бы один член общества, номер которого равен сумме номеров двух членов общества из той же страны или удвоенному номеру одного члена общества из той же страны.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Сопоставим каждой стране свой цвет. Построим полный граф с вершинами \[ 0,1,2,\ldots,1978, \] и покрасим ребро, соединяющее \(i\) и \(j\), в цвет страны, которую представляет член общества с номером \(|i-j|\).
Треугольник, все три ребра которого имеют один цвет, даёт требуемое утверждение. Действительно, обозначим его вершины через \(x<y<z\). Тогда члены общества с номерами \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] представляют одну и ту же страну, причём \(c=a+b\). Если \(a\ne b\), получаем первый из случаев, указанных в условии; если \(a=b\), то \(c=2a\), что даёт второй случай.
Таким образом, достаточно доказать, что наш граф содержит такой треугольник.
Предположим противное: такого треугольника нет. Воспользуемся следующим наблюдением: если полный подграф имеет \(m\) вершин и его рёбра окрашены не более чем в \(r\) цветов, то он содержит полный подграф, имеющий не менее \[ \left\lceil\frac{m-1}{r}\right\rceil \] вершин, рёбра которого окрашены не более чем в \(r-1\) цветов.
Для доказательства этого наблюдения выберем вершину \(v\). По принципу Дирихле хотя бы \(\lceil(m-1)/r\rceil\) рёбер, выходящих из \(v\), имеют один и тот же цвет. Обозначим через \(T\) множество их других концов. Ни одно ребро между двумя вершинами из \(T\) не может иметь этот цвет, поскольку вместе с \(v\) оно образовало бы треугольник этого цвета. Таким образом, рёбра внутри \(T\) окрашены не более чем в остальные \(r-1\) цветов, что доказывает наблюдение.
Начиная с нашего графа на \(1979\) вершинах, рёбра которого окрашены в шесть цветов, последовательно применим это наблюдение:
| Максимальное число цветов | Гарантированное число вершин |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
Последний подграф имеет хотя бы три вершины, и все его рёбра имеют один цвет. Поэтому любые три его вершины образуют треугольник этого цвета, что противоречит нашему предположению.
Следовательно, такой треугольник существует, и соответствующие члены общества удовлетворяют одному из двух требуемых условий. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1978 · المسألة 6
ينتمي أعضاء جمعية دولية إلى ست دول مختلفة. تضم قائمة الأعضاء 1978 اسمًا، مرقمة بالأعداد \(1, 2, \ldots, 1978\). أثبت وجود عضو واحد على الأقل يساوي رقمه مجموع رقمي عضوين من دولته، أو يساوي ضعفي رقم عضو من دولته.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نخصص لونًا مختلفًا لكل دولة. ننشئ رسمًا بيانيًا كاملًا رؤوسه \[ 0,1,2,\ldots,1978, \] ونلون الحافة الواصلة بين \(i\) و\(j\) وفقًا لدولة العضو ذي الرقم \(|i-j|\).
يعطينا مثلث تكون حوافه الثلاث كلها من اللون نفسه النتيجة المطلوبة. بالفعل، لنكتب رؤوسه على الصورة \(x<y<z\). عندئذ يكون الأعضاء ذوو الأرقام \[ a=y-x,\qquad b=z-y,\qquad c=z-x \] من الدولة نفسها، ويكون \(c=a+b\). إذا كان \(a\ne b\)، فهذه هي الحالة الأولى في المسألة؛ وإذا كان \(a=b\)، فإن \(c=2a\)، وهذا يعطينا الحالة الثانية.
إذن يكفي إثبات أن رسمنا البياني يحتوي على مثل هذا المثلث.
لنفترض، طلبًا للتناقض، أنه لا يحتوي عليه. نستخدم الملاحظة التالية: إذا كان لرسم بياني جزئي كامل \(m\) رأسًا، وكانت حوافه تستخدم \(r\) لونًا على الأكثر، فإنه يحتوي على رسم بياني جزئي كامل له على الأقل \[ \left\lceil\frac{m-1}{r}\right\rceil \] رأسًا، وتستخدم حوافه \(r-1\) لونًا على الأكثر.
لإثبات الملاحظة، نختار رأسًا \(v\). بحسب مبدأ الحمام، يوجد على الأقل \(\lceil(m-1)/r\rceil\) حافة منطلقة من \(v\) لها لون واحد مشترك. لتكن \(T\) مجموعة أطرافها الأخرى. لا يمكن لأي حافة بين رأسين من \(T\) أن تحمل ذلك اللون، لأنها ستشكل مع \(v\) مثلثًا من ذلك اللون. ومن ثم فإن الحواف داخل \(T\) تستخدم على الأكثر الألوان الأخرى وعددها \(r-1\)، وهذا يثبت الملاحظة.
بدءًا من رؤوس رسمنا البالغ عددها \(1979\) ومن ألوانه الستة، نطبق هذه الملاحظة مرارًا:
| العدد الأقصى للألوان | العدد المضمون للرؤوس |
|---|---|
| \(6\) | \(1979\) |
| \(5\) | \(\left\lceil1978/6\right\rceil=330\) |
| \(4\) | \(\left\lceil329/5\right\rceil=66\) |
| \(3\) | \(\left\lceil65/4\right\rceil=17\) |
| \(2\) | \(\left\lceil16/3\right\rceil=6\) |
| \(1\) | \(\left\lceil5/2\right\rceil=3\) |
للرسم البياني الجزئي الأخير ثلاثة رؤوس على الأقل، وجميع حوافه من اللون نفسه. ومن ثم فإن أي ثلاثة من رؤوسه تشكل مثلثًا من ذلك اللون، وهذا يناقض فرضنا.
وعليه، يوجد مثل هذا المثلث، ويحقق الأعضاء المقابلون له إحدى الحالتين المطلوبتين. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).