IMO 1986 · Problem 6
One is given a finite set of points in the plane, each point having integer coordinates. Is it always possible to color some of the points in the set red and the remaining points white in such a way that for any straight line \(L\) parallel to either one of the coordinate axes the difference (in absolute value) between the numbers of white point and red points on \(L\) is not greater than 1?
Official text of the problem. Official problem paper (PDF)
Answer
Yes, it is always possible.
Solution
Let \(S\) be the given finite set. If \(S\) is empty, the conclusion is immediate. Otherwise, construct pairs of points as follows:
- On each horizontal line containing points of \(S\), list those points from left to right and pair the first with the second, the third with the fourth, and so on. At most one point on that line remains unpaired.
- Independently, do the same on each vertical line, listing its points from bottom to top.
Form a graph whose vertices are the points of \(S\), with an edge joining each chosen pair. Call an edge horizontal or vertical according to the pairing that produced it. Two distinct points cannot form both a horizontal and a vertical pair, since that would require both their coordinates to agree.
Each vertex belongs to at most one horizontal pair and at most one vertical pair, so its degree is at most two. Consequently, every connected component is an isolated vertex, a path, or a cycle. To see this, if a component contains a cycle, each vertex on that cycle already has two incident edges, so no additional vertices can attach to it. If it contains no cycle, a longest path exhausts the component: an additional vertex would either extend the path or force an internal vertex to have degree at least three.
Every cycle has even length. Indeed, the two edges meeting at any vertex of a cycle must be one horizontal and one vertical. Thus horizontal and vertical edges alternate around the cycle, which requires an even number of edges.
We can therefore color every component so that the endpoints of every edge have opposite colors: color isolated vertices arbitrarily, alternate red and white along each path, and alternate around each cycle. The latter coloring is consistent because every cycle has even length.
Now let \(L\) be any horizontal line. Each horizontal pair on \(L\) contributes one red point and one white point. Since these pairs cover all points of \(S\) on \(L\) except possibly one, the two color counts differ by at most one. The identical argument using vertical pairs applies to every vertical line. Lines containing no points have difference zero.
Hence the required coloring always exists.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1986 · Aufgabe 6
Gegeben ist eine endliche Menge von Punkten in der Ebene, deren Koordinaten jeweils ganzzahlig sind. Ist es stets möglich, einige Punkte der Menge rot und die übrigen weiß zu färben, sodass für jede Gerade \(L\), die zu einer der beiden Koordinatenachsen parallel ist, der Betrag der Differenz zwischen der Anzahl der weißen und der Anzahl der roten Punkte auf \(L\) nicht größer als 1 ist?
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Ja, dies ist stets möglich.
Lösung
Sei \(S\) die gegebene endliche Menge. Ist \(S\) leer, so ist die Behauptung unmittelbar klar. Andernfalls bilden wir wie folgt Paare von Punkten:
- Auf jeder horizontalen Geraden, die Punkte von \(S\) enthält, ordnen wir diese Punkte von links nach rechts und paaren den ersten mit dem zweiten, den dritten mit dem vierten und so weiter. Höchstens ein Punkt auf dieser Geraden bleibt ungepaart.
- Unabhängig davon verfahren wir auf jeder vertikalen Geraden ebenso, wobei wir ihre Punkte von unten nach oben ordnen.
Wir bilden einen Graphen, dessen Knoten die Punkte von \(S\) sind und in dem jedes gewählte Paar durch eine Kante verbunden wird. Wir nennen eine Kante horizontal oder vertikal, je nachdem, durch welche Paarung sie entstanden ist. Zwei verschiedene Punkte können nicht zugleich ein horizontales und ein vertikales Paar bilden, da dafür ihre beiden Koordinaten übereinstimmen müssten.
Jeder Knoten gehört zu höchstens einem horizontalen und höchstens einem vertikalen Paar, hat also höchstens den Grad zwei. Folglich ist jede Zusammenhangskomponente ein isolierter Knoten, ein Pfad oder ein Kreis. Um dies einzusehen, betrachten wir zunächst eine Komponente, die einen Kreis enthält: Jeder Knoten auf diesem Kreis ist bereits mit zwei Kanten inzident, sodass keine weiteren Knoten daran angeschlossen sein können. Enthält sie keinen Kreis, so umfasst ein längster Pfad die gesamte Komponente: Ein zusätzlicher Knoten würde entweder den Pfad verlängern oder erzwingen, dass ein innerer Knoten mindestens den Grad drei hat.
Jeder Kreis hat gerade Länge. Tatsächlich müssen von den beiden Kanten, die an einem Knoten eines Kreises zusammentreffen, eine horizontal und eine vertikal sein. Somit wechseln sich horizontale und vertikale Kanten entlang des Kreises ab, was eine gerade Anzahl von Kanten erfordert.
Wir können daher jede Komponente so färben, dass die Endknoten jeder Kante verschiedene Farben haben: Wir färben isolierte Knoten beliebig, färben entlang jedes Pfades abwechselnd rot und weiß und ebenso entlang jedes Kreises. Die letztere Färbung ist widerspruchsfrei, weil jeder Kreis gerade Länge hat.
Sei nun \(L\) eine beliebige horizontale Gerade. Jedes horizontale Paar auf \(L\) trägt einen roten und einen weißen Punkt bei. Da diese Paare alle Punkte von \(S\) auf \(L\) bis auf höchstens einen erfassen, unterscheiden sich die Anzahlen der beiden Farben um höchstens eins. Dasselbe Argument mit vertikalen Paaren gilt für jede vertikale Gerade. Auf Geraden, die keine Punkte enthalten, ist die Differenz null.
Somit existiert die geforderte Färbung stets.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1986 · Soru 6
Düzlemde, her noktasının koordinatları tam sayı olan sonlu bir nokta kümesi veriliyor. Kümedeki noktaların bir kısmını kırmızıya, geri kalanını beyaza, koordinat eksenlerinden herhangi birine paralel olan her \(L\) doğrusu üzerindeki beyaz noktaların sayısı ile kırmızı noktaların sayısının farkının mutlak değeri 1'den büyük olmayacak şekilde boyamak her zaman mümkün müdür?
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Evet, her zaman mümkündür.
Çözüm
Verilen sonlu küme \(S\) olsun. \(S\) boşsa sonuç açıktır. Aksi hâlde, noktaları aşağıdaki gibi eşleştirelim:
- \(S\)'nin noktalarını içeren her yatay doğru üzerinde, bu noktaları soldan sağa sıralayalım ve birinciyi ikinciyle, üçüncüyü dördüncüyle, bu şekilde devam ederek eşleştirelim. O doğru üzerinde en fazla bir nokta eşleşmeden kalır.
- Bundan bağımsız olarak, her düşey doğru üzerindeki noktaları aşağıdan yukarıya sıralayarak aynı işlemi yapalım.
Köşeleri \(S\)'nin noktaları olan ve seçilen her çifti bir kenarla birleştiren bir çizge oluşturalım. Her kenarı, onu oluşturan eşleştirmeye göre yatay veya düşey olarak adlandıralım. Birbirinden farklı iki nokta hem yatay hem de düşey bir çift oluşturamaz; çünkü bu, her iki koordinatlarının da aynı olmasını gerektirirdi.
Her köşe en fazla bir yatay ve en fazla bir düşey çifte ait olduğundan, derecesi en fazla ikidir. Dolayısıyla her bağlantılı bileşen ya yalıtılmış bir köşe, ya bir yol ya da bir çevrimdir. Bunu görmek için, bir bileşen bir çevrim içeriyorsa o çevrim üzerindeki her köşeye zaten iki kenarın bağlı olduğuna, dolayısıyla ona başka hiçbir köşenin bağlanamayacağına dikkat edelim. Bileşen çevrim içermiyorsa en uzun yollardan biri bileşenin tamamını kapsar: ek bir köşe ya yolu uzatır ya da bir iç köşenin derecesinin en az üç olmasını gerektirir.
Her çevrimin uzunluğu çifttir. Gerçekten, bir çevrimin herhangi bir köşesinde birleşen iki kenardan biri yatay, diğeri düşey olmak zorundadır. Dolayısıyla çevrim boyunca yatay ve düşey kenarlar dönüşümlü olarak yer alır; bu da kenar sayısının çift olmasını gerektirir.
Bu nedenle her bileşeni, her kenarın uçları farklı renklerde olacak şekilde boyayabiliriz: yalıtılmış köşeleri herhangi bir renge boyayalım, her yol boyunca kırmızı ve beyazı dönüşümlü kullanalım ve her çevrim boyunca da renkleri dönüşümlü kullanalım. Her çevrimin uzunluğu çift olduğundan, son boyama tutarlıdır.
Şimdi \(L\) herhangi bir yatay doğru olsun. \(L\) üzerindeki her yatay çift, bir kırmızı ve bir beyaz nokta sağlar. Bu çiftler, olası bir nokta dışında, \(S\)'nin \(L\) üzerindeki tüm noktalarını kapsadığından, iki rengin nokta sayıları arasındaki fark en fazla birdir. Düşey çiftleri kullanan aynı akıl yürütme her düşey doğru için geçerlidir. Hiç nokta içermeyen doğrularda fark sıfırdır.
Böylece istenen boyama her zaman vardır.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1986 · Problema 6
Se da un conjunto finito de puntos del plano, cada uno de ellos con coordenadas enteras. ¿Es siempre posible colorear de rojo algunos de los puntos del conjunto y de blanco los restantes, de tal manera que, para cualquier recta \(L\) paralela a cualquiera de los ejes de coordenadas, la diferencia (en valor absoluto) entre el número de puntos blancos y el de puntos rojos sobre \(L\) no sea mayor que 1?
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Sí, siempre es posible.
Solución
Sea \(S\) el conjunto finito dado. Si \(S\) es vacío, la conclusión es inmediata. En caso contrario, construyamos pares de puntos de la siguiente manera:
- En cada recta horizontal que contenga puntos de \(S\), ordenemos esos puntos de izquierda a derecha y emparejemos el primero con el segundo, el tercero con el cuarto, y así sucesivamente. A lo sumo un punto de esa recta queda sin emparejar.
- De forma independiente, hagamos lo mismo en cada recta vertical, ordenando sus puntos de abajo arriba.
Formemos un grafo cuyos vértices sean los puntos de \(S\), con una arista que una cada par elegido. Llamemos horizontal o vertical a una arista según el emparejamiento del que proceda. Dos puntos distintos no pueden formar a la vez un par horizontal y un par vertical, pues para ello tendrían que coincidir ambas coordenadas.
Cada vértice pertenece a lo sumo a un par horizontal y a lo sumo a un par vertical, por lo que su grado es a lo sumo dos. En consecuencia, cada componente conexa es un vértice aislado, un camino o un ciclo. Para verlo, si una componente contiene un ciclo, cada vértice de ese ciclo ya tiene dos aristas incidentes, por lo que no puede haber vértices adicionales unidos a él. Si no contiene ningún ciclo, un camino de longitud máxima abarca toda la componente: un vértice adicional permitiría prolongar el camino o forzaría a que un vértice interior tuviera grado al menos tres.
Todo ciclo tiene longitud par. En efecto, las dos aristas que concurren en cualquier vértice de un ciclo deben ser una horizontal y una vertical. Así, las aristas horizontales y verticales se alternan a lo largo del ciclo, lo cual exige un número par de aristas.
Por tanto, podemos colorear cada componente de modo que los extremos de toda arista tengan colores distintos: coloreamos los vértices aislados arbitrariamente, alternamos rojo y blanco a lo largo de cada camino y los alternamos a lo largo de cada ciclo. Esta última coloración es coherente porque todo ciclo tiene longitud par.
Sea ahora \(L\) una recta horizontal cualquiera. Cada par horizontal de \(L\) aporta un punto rojo y un punto blanco. Como estos pares cubren todos los puntos de \(S\) sobre \(L\), salvo posiblemente uno, los números de puntos de los dos colores difieren a lo sumo en uno. El mismo argumento, usando pares verticales, se aplica a toda recta vertical. En las rectas que no contienen puntos, la diferencia es cero.
Por tanto, siempre existe la coloración requerida.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1986 · 问题 6
给定平面内的一个有限点集，每个点的坐标均为整数。是否总能将集合中的一部分点染成红色，其余点染成白色，使得对于任意一条平行于某一坐标轴的直线 \(L\)，\(L\) 上白点数与红点数之差的绝对值不大于 1？
题目译自官方英文原文。 官方试卷 (PDF)
答案
是，总能做到。
解答
设给定的有限集为 \(S\)。若 \(S\) 为空集，则结论显然成立。否则，按如下方式将点配对：
- 在每条含有 \(S\) 中的点的水平直线上，将这些点从左到右排列，把第一个点与第二个点、第三个点与第四个点配对，依此类推。该直线上至多剩下一个点未配对。
- 独立地，在每条竖直直线上做同样的操作，将其上的点从下到上排列。
构造一个图，以 \(S\) 中的点为顶点，在每对配好的点之间连一条边。根据产生该边的配对方式，将其称为水平边或竖直边。两个不同的点不可能既构成水平配对又构成竖直配对，因为这将要求它们的两个坐标都相同。
每个顶点至多属于一个水平配对和一个竖直配对，所以它的度数至多为二。因此，每个连通分支都是一个孤立顶点、一条路径或一个圈。为说明这一点，若某个连通分支包含一个圈，则圈上每个顶点已经关联两条边，因此不可能有其他顶点与该圈相连。若它不含圈，则一条最长路径就包含了该连通分支的所有顶点：若还有其他顶点，则要么可以延长这条路径，要么会迫使某个内部顶点的度数至少为三。
每个圈的长度都为偶数。事实上，在圈的任意一个顶点处相接的两条边必定一条是水平边，另一条是竖直边。因此，沿着圈，水平边与竖直边交替出现，这就要求边数为偶数。
因此，我们可以给每个连通分支染色，使每条边的两个端点颜色不同：孤立顶点任意染色，沿每条路径交替染成红色和白色，沿每个圈也交替染色。由于每个圈的长度都是偶数，后一种染色不会产生矛盾。
现在设 \(L\) 为任意一条水平直线。\(L\) 上的每个水平配对都贡献一个红点和一个白点。由于这些配对覆盖了 \(L\) 上 \(S\) 中的所有点，至多漏掉一个点，因此两种颜色的点数之差至多为一。对每条竖直直线，利用竖直配对可作完全相同的论证。不含任何点的直线上，两种颜色的点数之差为零。
所以，所要求的染色总是存在。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1986 · Задача 6
Дано конечное множество точек на плоскости, каждая из которых имеет целочисленные координаты. Всегда ли можно раскрасить часть точек этого множества в красный цвет, а остальные — в белый так, чтобы для любой прямой \(L\), параллельной одной из координатных осей, разность (по абсолютной величине) между числом белых и числом красных точек на \(L\) не превышала 1?
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Да, это всегда возможно.
Решение
Пусть \(S\) — данное конечное множество. Если \(S\) пусто, утверждение очевидно. В противном случае составим пары точек следующим образом:
- На каждой горизонтальной прямой, содержащей точки множества \(S\), упорядочим эти точки слева направо и объединим в пары первую со второй, третью с четвёртой и так далее. На этой прямой без пары останется не более одной точки.
- Независимо от этого проделаем то же самое на каждой вертикальной прямой, упорядочив её точки снизу вверх.
Построим граф, вершинами которого служат точки множества \(S\), соединив ребром каждую выбранную пару. Назовём ребро горизонтальным или вертикальным в зависимости от того, при каком разбиении на пары оно возникло. Две различные точки не могут образовывать одновременно горизонтальную и вертикальную пару, поскольку для этого у них должны совпадать обе координаты.
Каждая вершина принадлежит не более чем одной горизонтальной паре и не более чем одной вертикальной паре, поэтому её степень не превосходит двух. Следовательно, каждая компонента связности является изолированной вершиной, путём или циклом. Чтобы убедиться в этом, заметим: если компонента содержит цикл, то каждая вершина этого цикла уже имеет два инцидентных ребра, поэтому к нему не могут присоединяться дополнительные вершины. Если же циклов нет, то самый длинный путь содержит всю компоненту: дополнительная вершина либо позволила бы удлинить путь, либо вынудила бы одну из его внутренних вершин иметь степень не менее трёх.
Каждый цикл имеет чётную длину. Действительно, из двух рёбер, сходящихся в любой вершине цикла, одно должно быть горизонтальным, а другое — вертикальным. Поэтому при обходе цикла горизонтальные и вертикальные рёбра чередуются, что возможно лишь при чётном числе рёбер.
Таким образом, каждую компоненту можно раскрасить так, чтобы концы каждого ребра имели разные цвета: изолированные вершины раскрасим произвольно, вдоль каждого пути будем чередовать красный и белый цвета, и так же будем чередовать цвета вдоль каждого цикла. Последняя раскраска согласована, поскольку каждый цикл имеет чётную длину.
Теперь пусть \(L\) — произвольная горизонтальная прямая. Каждая горизонтальная пара на \(L\) содержит одну красную и одну белую точку. Поскольку эти пары охватывают все точки множества \(S\) на \(L\), кроме, быть может, одной, количества точек двух цветов отличаются не более чем на один. Точно такое же рассуждение с использованием вертикальных пар применимо к каждой вертикальной прямой. Для прямых, не содержащих точек, разность равна нулю.
Следовательно, требуемая раскраска всегда существует.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1986 · المسألة 6
أُعطيت مجموعة منتهية من النقاط في المستوى، إحداثيا كل نقطة منها عددان صحيحان. هل يمكن دائمًا تلوين بعض نقاط المجموعة بالأحمر وبقية النقاط بالأبيض، بحيث، لأي مستقيم \(L\) موازٍ لأحد محوري الإحداثيات، لا تزيد القيمة المطلقة للفرق بين عدد النقاط البيضاء وعدد النقاط الحمراء الواقعة على \(L\) على 1؟
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
نعم، هذا ممكن دائمًا.
الحل
لتكن \(S\) المجموعة المنتهية المعطاة. إذا كانت \(S\) خالية، فالنتيجة فورية. وإلا، فننشئ أزواجًا من النقاط كما يأتي:
- على كل مستقيم أفقي يحتوي نقاطًا من \(S\)، نرتب تلك النقاط من اليسار إلى اليمين، ونقرن الأولى بالثانية، والثالثة بالرابعة، وهكذا. تبقى على ذلك المستقيم نقطة واحدة على الأكثر غير مقترنة.
- وبصورة مستقلة، نفعل الشيء نفسه على كل مستقيم رأسي، مرتبين نقاطه من الأسفل إلى الأعلى.
ننشئ رسمًا بيانيًا رؤوسه نقاط \(S\)، وتصل فيه حافة بين نقطتي كل زوج مختار. نسمي الحافة أفقية أو رأسية بحسب الاقتران الذي أنتجها. لا يمكن لنقطتين مختلفتين أن تشكّلا زوجًا أفقيًا وزوجًا رأسيًا معًا، لأن ذلك يستلزم تطابق إحداثييهما كليهما.
ينتمي كل رأس إلى زوج أفقي واحد على الأكثر وإلى زوج رأسي واحد على الأكثر، لذا لا تزيد درجته على اثنتين. وعليه، فإن كل مكوّن متصل إما رأس معزول، أو مسار، أو دورة. لرؤية ذلك، إذا احتوى مكوّن على دورة، فإن كل رأس على تلك الدورة تتصل به بالفعل حافتان، فلا يمكن أن تتصل به رؤوس إضافية. وإذا لم يحتوِ على دورة، فإن مسارًا أطول فيه يشمل المكوّن كله: إذ إن وجود رأس إضافي إما أن يتيح إطالة المسار، أو يفرض أن تكون درجة أحد رؤوسه الداخلية ثلاثة على الأقل.
طول كل دورة زوجي. بالفعل، لا بد أن تكون إحدى الحافتين الملتقيتين عند أي رأس في دورة أفقية والأخرى رأسية. وهكذا تتناوب الحواف الأفقية والرأسية حول الدورة، مما يستلزم أن يكون عدد الحواف زوجيًا.
لذلك يمكننا تلوين كل مكوّن بحيث يكون طرفا كل حافة بلونين مختلفين: نلوّن الرؤوس المعزولة كيفما شئنا، ونتناوب بين الأحمر والأبيض على طول كل مسار، وكذلك حول كل دورة. والتلوين الأخير متسق لأن طول كل دورة زوجي.
ليكن الآن \(L\) أي مستقيم أفقي. يضيف كل زوج أفقي على \(L\) نقطة حمراء واحدة ونقطة بيضاء واحدة. وبما أن هذه الأزواج تشمل جميع نقاط \(S\) الواقعة على \(L\)، باستثناء نقطة واحدة على الأكثر، فإن الفرق بين عددي النقاط من اللونين لا يزيد على واحد. وتنطبق الحجة نفسها، باستخدام الأزواج الرأسية، على كل مستقيم رأسي. أما المستقيمات التي لا تحتوي أي نقطة، فالفرق عليها يساوي صفرًا.
إذن يوجد التلوين المطلوب دائمًا.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).