IMO 2013 · Problem 2
A configuration of 4027 points in the plane is called Colombian if it consists of 2013 red points and 2014 blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied:
- no line passes through any point of the configuration;
- no region contains points of both colours.
Find the least value of \(k\) such that for any Colombian configuration of 4027 points, there is a good arrangement of \(k\) lines.
Official text of the problem. Official problem paper (PDF)
Answer
\[ \boxed{k=2013}. \]
Solution
We first prove that 2013 lines always suffice.
For any two points of the same colour, their joining line contains no other point of the configuration. Consequently, we can draw two parallel lines on opposite sides of it, sufficiently close that the open strip between them contains precisely those two points. Neither boundary line passes through a point of the configuration: choose the strip’s half-width smaller than the minimum distance from any other point to the joining line.
We will cover all points of one colour by such strips and one half-plane, each containing no point of the other colour. Drawing their boundary lines then gives a good arrangement. Indeed, a region containing a covered point lies entirely within every strip or half-plane containing that point, because their boundaries belong to the arrangement.
Let \(H\) be the convex hull of the configuration. There are two cases.
Case 1: Some vertex of \(H\) is red.
Let this vertex be \(R\). There is a supporting line of \(H\) whose only point of contact with \(H\) is \(R\): choose its direction strictly between the directions of the two supporting edges incident to \(R\). Moving this line a sufficiently small distance towards the interior of \(H\) gives a line separating \(R\) from every other point, without passing through any point. Thus one of its open half-planes contains precisely \(R\).
Partition the remaining 2012 red points into 1006 pairs, and surround each pair by a strip as described above. All red points are now covered by a half-plane and strips containing no blue points. Their boundaries give a good arrangement using at most \[ 1+2\cdot1006=2013 \] lines.
Case 2: Every vertex of \(H\) is blue.
Choose an edge \(UV\) of \(H\). Both endpoints are blue, and all other points lie strictly on the same side of the line \(UV\), since no three points are collinear. Translating this line a sufficiently small distance towards the interior of \(H\) therefore produces a line separating \(U,V\) from all other points, without passing through any point.
Partition the remaining 2012 blue points into 1006 pairs and surround each pair by a strip. Now all blue points are covered by a half-plane and strips containing no red points. Again their boundaries give a good arrangement using at most \[ 1+2\cdot1006=2013 \] lines.
If the construction produces fewer distinct lines, we may add lines avoiding all configuration points until there are exactly 2013. Adding lines only subdivides existing regions, so the arrangement remains good.
We next show that fewer lines do not always suffice.
Place 4027 distinct points on a circle, coloured in the following cyclic order: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] This is a Colombian configuration, since a line meets a circle in at most two points. Of the 4027 sides of the convex polygon formed by these points, exactly 4026 have endpoints of different colours; only \(B_{2013}B_0\) has endpoints of the same colour.
In any good arrangement, each of those 4026 sides must be crossed by at least one line. Otherwise its entire segment would avoid all the lines, joining its differently coloured endpoints within a single region.
A line avoiding the polygon’s vertices crosses at most two of its sides: its intersection with the convex polygon, when nonempty, is a segment, and crossings occur only at that segment’s two endpoints. Hence an arrangement of \(k\) lines can cross at most \(2k\) of the 4026 required sides. Therefore \[ 2k\ge4026, \qquad\text{so}\qquad k\ge2013. \]
Together with the construction, this proves that the least value is \(\boxed{2013}\).
The solution was checked against the official IMO shortlist solutions.
IMO 2013 · Aufgabe 2
Eine Konfiguration aus 4027 Punkten in der Ebene heißt kolumbianisch, wenn sie aus 2013 roten und 2014 blauen Punkten besteht, von denen keine drei Punkte auf einer Geraden liegen. Durch das Einzeichnen einiger Geraden wird die Ebene in mehrere Regionen unterteilt. Eine Menge von Geraden heißt gut für eine kolumbianische Konfiguration, wenn die beiden folgenden Bedingungen erfüllt sind:
- Keine Gerade geht durch einen Punkt der Konfiguration.
- Keine Region enthält Punkte beider Farben.
Man bestimme den minimalen Wert von \(k\), so dass es für jede kolumbianische Konfiguration von 4027 Punkten eine gute Menge von \(k\) Geraden gibt.
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Antwort
\[ \boxed{k=2013}. \]
Lösung
Wir beweisen zunächst, dass 2013 Geraden stets ausreichen.
Für je zwei Punkte derselben Farbe enthält ihre Verbindungsgerade keinen weiteren Punkt der Konfiguration. Daher können wir auf ihren beiden Seiten zwei parallele Geraden so nahe an ihr zeichnen, dass der offene Streifen zwischen ihnen genau diese beiden Punkte enthält. Keine der beiden Randgeraden geht durch einen Punkt der Konfiguration: Dazu wählen wir die halbe Breite des Streifens kleiner als den kleinsten Abstand eines anderen Punktes von der Verbindungsgeraden.
Wir werden alle Punkte einer Farbe durch solche Streifen und eine Halbebene überdecken, die jeweils keinen Punkt der anderen Farbe enthalten. Ihre Randgeraden bilden dann eine gute Menge von Geraden. Tatsächlich liegt eine Region, die einen überdeckten Punkt enthält, vollständig in jedem Streifen beziehungsweise jeder Halbebene, die diesen Punkt enthält, da deren Randgeraden zur Geradenmenge gehören.
Sei \(H\) die konvexe Hülle der Konfiguration. Es gibt zwei Fälle.
Fall 1: Ein Eckpunkt von \(H\) ist rot.
Sei \(R\) dieser Eckpunkt. Es gibt eine Stützgerade von \(H\), deren einziger gemeinsamer Punkt mit \(H\) der Punkt \(R\) ist: Wir wählen ihre Richtung strikt zwischen den Richtungen der beiden in \(R\) zusammentreffenden Kanten. Verschieben wir diese Gerade um eine hinreichend kleine Strecke ins Innere von \(H\), so erhalten wir eine Gerade, die \(R\) von allen anderen Punkten trennt, ohne durch einen Punkt zu gehen. Somit enthält eine ihrer offenen Halbebenen genau \(R\).
Wir teilen die verbleibenden 2012 roten Punkte in 1006 Paare ein und umgeben jedes Paar wie oben beschrieben mit einem Streifen. Nun sind alle roten Punkte durch eine Halbebene und Streifen überdeckt, die keine blauen Punkte enthalten. Ihre Randgeraden bilden eine gute Menge aus höchstens \[ 1+2\cdot1006=2013 \] Geraden.
Fall 2: Jeder Eckpunkt von \(H\) ist blau.
Wir wählen eine Kante \(UV\) von \(H\). Beide Endpunkte sind blau, und alle anderen Punkte liegen strikt auf derselben Seite der Geraden \(UV\), da keine drei Punkte auf einer Geraden liegen. Verschieben wir diese Gerade um eine hinreichend kleine Strecke ins Innere von \(H\), so erhalten wir daher eine Gerade, die \(U,V\) von allen anderen Punkten trennt, ohne durch einen Punkt zu gehen.
Wir teilen die verbleibenden 2012 blauen Punkte in 1006 Paare ein und umgeben jedes Paar mit einem Streifen. Nun sind alle blauen Punkte durch eine Halbebene und Streifen überdeckt, die keine roten Punkte enthalten. Wieder bilden ihre Randgeraden eine gute Menge aus höchstens \[ 1+2\cdot1006=2013 \] Geraden.
Falls die Konstruktion weniger verschiedene Geraden liefert, können wir weitere Geraden hinzufügen, die durch keinen Punkt der Konfiguration gehen, bis es genau 2013 sind. Durch das Hinzufügen von Geraden werden bestehende Regionen lediglich weiter unterteilt, so dass die Geradenmenge gut bleibt.
Als Nächstes zeigen wir, dass weniger Geraden nicht immer ausreichen.
Wir platzieren 4027 verschiedene Punkte auf einem Kreis und färben sie in der folgenden zyklischen Reihenfolge: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] Dies ist eine kolumbianische Konfiguration, da eine Gerade einen Kreis in höchstens zwei Punkten schneidet. Von den 4027 Seiten des konvexen Vielecks, das diese Punkte bilden, haben genau 4026 verschiedenfarbige Endpunkte; nur \(B_{2013}B_0\) hat gleichfarbige Endpunkte.
In jeder guten Geradenmenge muss jede dieser 4026 Seiten von mindestens einer Geraden geschnitten werden. Andernfalls würde die gesamte Strecke keine der Geraden treffen und ihre verschiedenfarbigen Endpunkte innerhalb einer einzigen Region verbinden.
Eine Gerade, die durch keinen Eckpunkt des Vielecks geht, schneidet höchstens zwei seiner Seiten: Ihr Schnitt mit dem konvexen Vieleck ist, sofern er nicht leer ist, eine Strecke, und die Seiten werden nur an den beiden Endpunkten dieser Strecke geschnitten. Daher können \(k\) Geraden höchstens \(2k\) der 4026 erforderlichen Seiten schneiden. Folglich gilt \[ 2k\ge4026, \qquad\text{also}\qquad k\ge2013. \]
Zusammen mit der Konstruktion beweist dies, dass der minimale Wert \(\boxed{2013}\) ist.
Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.
IMO 2013 · Soru 2
Düzlem üzerindeki 4027 noktanın herhangi üçü doğrusal olmayıp, 2013 tanesi kırmızı ve 2014 tanesi mavi ise, bu 4027 noktaya bir Kolombiya konfigürasyonu diyelim. Düzlemde çizilen birkaç doğru düzlemi bölgelere ayırır. Bir doğrular kümesi, bir Kolombiya konfigürasyonu için aşağıdaki iki koşulu sağlıyorsa, bu küme bu konfigürasyon için iyi kabul ediliyor.
- doğrulardan her biri, konfigürasyonun hiçbir noktasından geçmemektedir;
- her iki rengi birden içeren bölge bulunmamaktadır.
4027 noktalı herhangi bir Kolombiya konfigürasyonu verildiğinde, bu konfigürasyon için iyi olan ve \(k\) doğrudan oluşan bir küme bulunuyorsa, \(k\) nin alabileceği en küçük değeri bulunuz.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Cevap
\[ \boxed{k=2013}. \]
Çözüm
Önce 2013 doğrunun her zaman yeterli olduğunu kanıtlayacağız.
Aynı renkteki herhangi iki noktayı birleştiren doğru, konfigürasyonun başka hiçbir noktasını içermez. Dolayısıyla bu doğrunun iki yanında, aralarındaki açık şerit tam olarak bu iki noktayı içerecek kadar yakın iki paralel doğru çizebiliriz. Sınır doğrularının hiçbiri konfigürasyonun bir noktasından geçmez: şeridin yarı genişliğini, diğer noktaların birleştiren doğruya olan uzaklıklarının en küçüğünden küçük seçelim.
Bir renkteki tüm noktaları, her biri diğer renkten hiçbir nokta içermeyen bu tür şeritler ve bir yarı düzlem ile örteceğiz. Bunların sınır doğrularını çizmek iyi bir doğrular kümesi verir. Gerçekten de, örtülen bir noktayı içeren bölge, o noktayı içeren her şeridin veya yarı düzlemin bütünüyle içinde kalır; çünkü bunların sınırları doğrular kümesine aittir.
Konfigürasyonun dışbükey örtüsü \(H\) olsun. İki durum vardır.
Durum 1: \(H\)'nin bir köşesi kırmızıdır.
Bu köşe \(R\) olsun. \(H\) ile tek ortak noktası \(R\) olan bir destek doğrusu vardır: yönünü, \(R\)'de birleşen iki destek kenarının yönleri arasında, bu yönlerden farklı olacak şekilde seçelim. Bu doğruyu \(H\)'nin içine doğru yeterince küçük bir miktar kaydırmak, hiçbir noktadan geçmeden \(R\)'yi diğer tüm noktalardan ayıran bir doğru verir. Böylece bu doğrunun belirlediği açık yarı düzlemlerden biri tam olarak \(R\)'yi içerir.
Kalan 2012 kırmızı noktayı 1006 çifte ayıralım ve her çifti yukarıda açıklanan bir şeritle çevreleyelim. Artık tüm kırmızı noktalar, hiçbir mavi nokta içermeyen bir yarı düzlem ve şeritlerle örtülmüştür. Bunların sınırları, en fazla \[ 1+2\cdot1006=2013 \] doğru kullanan iyi bir doğrular kümesi verir.
Durum 2: \(H\)'nin her köşesi mavidir.
\(H\)'nin bir \(UV\) kenarını seçelim. Her iki uç nokta da mavidir ve herhangi üç nokta doğrusal olmadığından, diğer tüm noktalar \(UV\) doğrusunun kesin olarak aynı tarafında yer alır. Dolayısıyla bu doğruyu \(H\)'nin içine doğru yeterince küçük bir miktar ötelemek, hiçbir noktadan geçmeden \(U,V\)'yi diğer tüm noktalardan ayıran bir doğru verir.
Kalan 2012 mavi noktayı 1006 çifte ayıralım ve her çifti bir şeritle çevreleyelim. Artık tüm mavi noktalar, hiçbir kırmızı nokta içermeyen bir yarı düzlem ve şeritlerle örtülmüştür. Bunların sınırları yine en fazla \[ 1+2\cdot1006=2013 \] doğru kullanan iyi bir doğrular kümesi verir.
Bu inşa daha az sayıda farklı doğru verirse, tam olarak 2013 doğru elde edene kadar konfigürasyonun hiçbir noktasından geçmeyen doğrular ekleyebiliriz. Doğru eklemek yalnızca mevcut bölgeleri daha küçük bölgelere ayırır; dolayısıyla doğrular kümesi iyi kalır.
Şimdi daha az sayıda doğrunun her zaman yeterli olmadığını göstereceğiz.
Bir çember üzerine, aşağıdaki çevrimsel sırada renklendirilmiş 4027 farklı nokta yerleştirelim: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] Bir doğru bir çemberi en fazla iki noktada kestiği için bu bir Kolombiya konfigürasyonudur. Bu noktaların oluşturduğu dışbükey çokgenin 4027 kenarından tam olarak 4026 tanesinin uç noktaları farklı renktedir; yalnızca \(B_{2013}B_0\) kenarının uç noktaları aynı renktedir.
Herhangi bir iyi doğrular kümesinde, bu 4026 kenarın her birini en az bir doğru kesmelidir. Aksi takdirde kenarın tamamı tüm doğrulardan kaçınır ve farklı renklerdeki uç noktalarını tek bir bölge içinde birleştirirdi.
Çokgenin köşelerinden geçmeyen bir doğru, çokgenin en fazla iki kenarını keser: dışbükey çokgenle kesişimi, boş değilse, bir doğru parçasıdır ve kenar kesişimleri yalnızca bu doğru parçasının iki uç noktasında gerçekleşir. Bu nedenle \(k\) doğrudan oluşan bir küme, kesilmesi gereken 4026 kenarın en fazla \(2k\) tanesini kesebilir. Dolayısıyla \[ 2k\ge4026, \qquad\text{dolayısıyla}\qquad k\ge2013. \]
Bu sonuç, verdiğimiz inşa ile birlikte, en küçük değerin \(\boxed{2013}\) olduğunu kanıtlar.
Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.
IMO 2013 · Problema 2
Una configuración de 4027 puntos del plano, de los cuales 2013 son rojos y 2014 azules, y no hay tres de ellos que sean colineales, se llama colombiana. Trazando algunas rectas, el plano queda dividido en varias regiones. Una colección de rectas es buena para una configuración colombiana si se cumplen las dos siguientes condiciones:
- ninguna recta pasa por ninguno de los puntos de la configuración;
- ninguna región contiene puntos de ambos colores.
Hallar el menor valor de \(k\) tal que para cualquier configuración colombiana de 4027 puntos hay una colección buena de \(k\) rectas.
Texto oficial en español del problema. Enunciado oficial (PDF)
Respuesta
\[ \boxed{k=2013}. \]
Solución
Primero demostramos que 2013 rectas siempre bastan.
Para cualesquiera dos puntos del mismo color, la recta que los une no contiene ningún otro punto de la configuración. Por consiguiente, podemos trazar dos rectas paralelas a ambos lados de ella, lo suficientemente próximas como para que la franja abierta entre ellas contenga exactamente esos dos puntos. Ninguna de las rectas que delimitan la franja pasa por un punto de la configuración: basta elegir la semianchura de la franja menor que la distancia mínima de cualquier otro punto a la recta que une los dos puntos.
Cubriremos todos los puntos de un color con franjas de este tipo y un semiplano, cada uno de los cuales no contiene ningún punto del otro color. Al trazar las rectas que los delimitan, obtenemos una colección buena. En efecto, una región que contiene un punto cubierto está contenida por completo en cada franja o semiplano que contiene ese punto, porque sus fronteras pertenecen a la colección.
Sea \(H\) la envolvente convexa de la configuración. Hay dos casos.
Caso 1: Algún vértice de \(H\) es rojo.
Sea \(R\) ese vértice. Existe una recta de apoyo de \(H\) cuyo único punto de contacto con \(H\) es \(R\): elegimos su dirección estrictamente entre las direcciones de las dos aristas que concurren en \(R\). Al desplazar esta recta una distancia suficientemente pequeña hacia el interior de \(H\), obtenemos una recta que separa \(R\) de todos los demás puntos, sin pasar por ningún punto. Así, uno de sus semiplanos abiertos contiene exactamente a \(R\).
Dividimos los 2012 puntos rojos restantes en 1006 pares y rodeamos cada par con una franja como la descrita anteriormente. Todos los puntos rojos quedan ahora cubiertos por un semiplano y franjas que no contienen puntos azules. Sus fronteras dan una colección buena que utiliza a lo sumo \[ 1+2\cdot1006=2013 \] rectas.
Caso 2: Todos los vértices de \(H\) son azules.
Elegimos una arista \(UV\) de \(H\). Ambos extremos son azules y todos los demás puntos están estrictamente en el mismo lado de la recta \(UV\), ya que no hay tres puntos colineales. Por tanto, al trasladar esta recta una distancia suficientemente pequeña hacia el interior de \(H\), obtenemos una recta que separa \(U,V\) de todos los demás puntos, sin pasar por ningún punto.
Dividimos los 2012 puntos azules restantes en 1006 pares y rodeamos cada par con una franja. Ahora todos los puntos azules quedan cubiertos por un semiplano y franjas que no contienen puntos rojos. De nuevo, sus fronteras dan una colección buena que utiliza a lo sumo \[ 1+2\cdot1006=2013 \] rectas.
Si la construcción produce menos rectas distintas, podemos añadir rectas que no pasen por ningún punto de la configuración hasta tener exactamente 2013. Añadir rectas solo subdivide las regiones existentes, por lo que la colección sigue siendo buena.
A continuación demostramos que un número menor de rectas no siempre basta.
Colocamos 4027 puntos distintos en una circunferencia, coloreados en el siguiente orden cíclico: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] Esta es una configuración colombiana, ya que una recta corta una circunferencia en a lo sumo dos puntos. De los 4027 lados del polígono convexo formado por estos puntos, exactamente 4026 tienen extremos de colores distintos; solo \(B_{2013}B_0\) tiene extremos del mismo color.
En cualquier colección buena, cada uno de esos 4026 lados debe ser atravesado por al menos una recta. De lo contrario, su segmento completo no cortaría ninguna de las rectas y uniría sus extremos de distintos colores dentro de una misma región.
Una recta que no pasa por los vértices del polígono atraviesa a lo sumo dos de sus lados: su intersección con el polígono convexo, cuando no es vacía, es un segmento, y los cruces se producen únicamente en los dos extremos de ese segmento. Por tanto, una colección de \(k\) rectas puede atravesar a lo sumo \(2k\) de los 4026 lados que deben ser atravesados. En consecuencia, \[ 2k\ge4026, \qquad\text{por lo que}\qquad k\ge2013. \]
Junto con la construcción, esto demuestra que el menor valor es \(\boxed{2013}\).
La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.
IMO 2013 · 问题 2
平面上的 4027 个点称为是一个哥伦比亚式点集，如果其中任意三点不共线，且有 2013 个点是红色的，2014 个点是蓝色的。在平面上画出一组直线，可以将平面分成若干区域。如果一组直线对于一个哥伦比亚式点集满足下述两个条件，我们就称这是一个好直线组：
- 这些直线不经过该哥伦比亚式点集中的任何一个点；
- 每个区域中都不会同时出现两种颜色的点。
求 \(k\) 的最小值，使得对于任意的哥伦比亚式点集，都存在由 \(k\) 条直线构成的好直线组。
题目为官方中文译本。 官方试卷 (PDF)
答案
\[ \boxed{k=2013}. \]
解答
我们先证明 2013 条直线总是足够的。
对于任意两个同色点，它们的连线不包含点集中的其他点。因此，我们可以在这条直线两侧各画一条与之平行的直线，使它们足够靠近，从而两条平行直线之间的开带状区域恰好包含这两个点。两条边界直线均不经过点集中的点：只需使带状区域的半宽小于其余各点到这两个点的连线的距离的最小值。
我们将用这样的带状区域和一个半平面覆盖某一种颜色的所有点，并使每个区域均不包含另一种颜色的点。画出它们的边界直线，就得到一个好直线组。事实上，包含某个被覆盖点的区域完全位于包含该点的每个带状区域或半平面内，因为它们的边界均属于所画的直线组。
设 \(H\) 为该点集的凸包。分两种情形讨论。
情形 1：\(H\) 的某个顶点为红色。
设这个顶点为 \(R\)。存在一条 \(H\) 的支撑直线，它与 \(H\) 的唯一公共点是 \(R\)：只需选取其方向严格介于经过 \(R\) 的两条相邻边的支撑方向之间。将这条直线朝 \(H\) 的内部平移足够小的距离，就得到一条将 \(R\) 与所有其他点分隔开、且不经过任何点的直线。因此，它的一个开半平面恰好包含 \(R\)。
将其余 2012 个红点分成 1006 对，并按上述方法用一个带状区域围住每一对点。现在，所有红点都被一个半平面和若干不含蓝点的带状区域覆盖。它们的边界给出一个好直线组，所用直线至多为 \[ 1+2\cdot1006=2013 \] 条。
情形 2：\(H\) 的每个顶点都是蓝色。
选取 \(H\) 的一条边 \(UV\)。它的两个端点都是蓝色，且由于任意三点不共线，所有其他点都严格位于直线 \(UV\) 的同一侧。因此，将这条直线朝 \(H\) 的内部平移足够小的距离，就得到一条将 \(U,V\) 与所有其他点分隔开、且不经过任何点的直线。
将其余 2012 个蓝点分成 1006 对，并用一个带状区域围住每一对点。现在，所有蓝点都被一个半平面和若干不含红点的带状区域覆盖。它们的边界同样给出一个好直线组，所用直线至多为 \[ 1+2\cdot1006=2013 \] 条。
若构造中得到的互不相同的直线不足 2013 条，我们可以添加不经过点集中任何点的直线，直到恰好有 2013 条为止。添加直线只会将已有区域进一步分割，因此该直线组仍然是好直线组。
接下来证明，更少的直线并非总是足够的。
在一个圆上取 4027 个互不相同的点，并按以下循环顺序着色： \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] 这是一个哥伦比亚式点集，因为一条直线与一个圆至多有两个交点。这些点构成的凸多边形共有 4027 条边，其中恰有 4026 条边的两个端点颜色不同；只有 \(B_{2013}B_0\) 的两个端点颜色相同。
在任意一个好直线组中，这 4026 条边中的每一条都必须被至少一条直线穿过。否则，这条边的整条线段都不与任何直线相交，从而在同一个区域内连接了两个颜色不同的端点。
一条不经过多边形顶点的直线至多穿过它的两条边：该直线与凸多边形的交集若非空，就是一条线段，而穿越边界只会发生在这条线段的两个端点处。因此，由 \(k\) 条直线组成的直线组至多能穿过上述 4026 条边中的 \(2k\) 条。所以 \[ 2k\ge4026, \qquad\text{所以}\qquad k\ge2013. \]
结合前面的构造，便证明了最小值为 \(\boxed{2013}\)。
解答已与 IMO 官方预选题（shortlist）解答核对。
IMO 2013 · Задача 2
Будем называть колумбийской конфигурацией точек набор из 4027 точек на плоскости, никакие три из которых не лежат на одной прямой, при этом 2013 из них покрашены в красный цвет, а остальные 2014 — в синий. Рассмотрим набор прямых, делящих плоскость на несколько областей. Назовем этот набор хорошим для данной колумбийской конфигурации точек, если выполнены следующие два условия:
- никакая прямая не проходит ни через одну из точек конфигурации;
- никакая область разбиения не содержит точек обоих цветов.
Найдите наименьшее \(k\) такое, что для любой колумбийской конфигурации из 4027 точек найдется хороший набор из \(k\) прямых.
Официальный русский текст задачи. Официальный текст задач (PDF)
Ответ
\[ \boxed{k=2013}. \]
Решение
Сначала докажем, что 2013 прямых всегда достаточно.
Для любых двух точек одного цвета проходящая через них прямая не содержит других точек конфигурации. Поэтому по разные стороны от неё можно провести две параллельные прямые настолько близко к ней, чтобы открытая полоса между ними содержала ровно эти две точки. Ни одна из граничных прямых не проходит через точку конфигурации: для этого выберем половину ширины полосы меньше минимального расстояния от любой другой точки до прямой, соединяющей выбранные точки.
Мы покроем все точки одного цвета такими полосами и одной полуплоскостью, каждая из которых не содержит точек другого цвета. Тогда их граничные прямые образуют хороший набор. Действительно, область, содержащая покрытую точку, целиком лежит в каждой полосе или полуплоскости, содержащей эту точку, поскольку их границы входят в набор прямых.
Пусть \(H\) — выпуклая оболочка конфигурации. Возможны два случая.
Случай 1: Некоторая вершина \(H\) красная.
Обозначим эту вершину через \(R\). Существует опорная прямая к \(H\), единственная общая точка которой с \(H\) — это \(R\): выберем её направление строго между направлениями двух опорных рёбер, выходящих из \(R\). Сдвинув эту прямую на достаточно малое расстояние внутрь \(H\), получим прямую, отделяющую \(R\) от всех остальных точек и не проходящую ни через одну точку. Таким образом, одна из её открытых полуплоскостей содержит ровно точку \(R\).
Разобьём оставшиеся 2012 красных точек на 1006 пар и заключим каждую пару в полосу, как описано выше. Теперь все красные точки покрыты полуплоскостью и полосами, не содержащими синих точек. Их границы образуют хороший набор, в котором не более \[ 1+2\cdot1006=2013 \] прямых.
Случай 2: Все вершины \(H\) синие.
Выберем ребро \(UV\) многоугольника \(H\). Оба его конца синие, а все остальные точки лежат строго по одну сторону от прямой \(UV\), поскольку никакие три точки не лежат на одной прямой. Поэтому, сдвинув эту прямую на достаточно малое расстояние внутрь \(H\), получим прямую, отделяющую \(U,V\) от всех остальных точек и не проходящую ни через одну точку.
Разобьём оставшиеся 2012 синих точек на 1006 пар и заключим каждую пару в полосу. Теперь все синие точки покрыты полуплоскостью и полосами, не содержащими красных точек. Их границы снова образуют хороший набор, в котором не более \[ 1+2\cdot1006=2013 \] прямых.
Если при построении получилось меньше различных прямых, можно добавлять прямые, не проходящие через точки конфигурации, пока их не станет ровно 2013. Добавление прямых лишь разбивает уже имеющиеся области на части, поэтому набор остаётся хорошим.
Теперь покажем, что меньшего числа прямых не всегда достаточно.
Расположим 4027 различных точек на окружности, раскрасив их в следующем циклическом порядке: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] Это колумбийская конфигурация, поскольку прямая пересекает окружность не более чем в двух точках. Из 4027 сторон выпуклого многоугольника, образованного этими точками, ровно 4026 имеют концы разных цветов; только у стороны \(B_{2013}B_0\) концы одного цвета.
В любом хорошем наборе каждую из этих 4026 сторон должна пересекать хотя бы одна прямая. Иначе весь этот отрезок не пересекал бы ни одной прямой и соединял бы свои концы разных цветов внутри одной области.
Прямая, не проходящая через вершины многоугольника, пересекает не более двух его сторон: её пересечение с выпуклым многоугольником, если оно непусто, представляет собой отрезок, и пересечения со сторонами происходят только в двух концах этого отрезка. Следовательно, набор из \(k\) прямых может пересечь не более \(2k\) из 4026 необходимых сторон. Поэтому \[ 2k\ge4026, \qquad\text{откуда}\qquad k\ge2013. \]
Вместе с приведённым построением это доказывает, что наименьшее значение равно \(\boxed{2013}\).
Решение проверено по официальным решениям шортлиста IMO.
IMO 2013 · المسألة 2
لدينا تشكيلة مكوّنة من \(4027\) نقطة في المستوي. تسمّى هذه التّشكيلة كولومبيّة إذا كانت \(2013\) من نقطها حمراء، و \(2014\) من نقطها زرقاء، ولا تكون أيّ ثلاث نقاط من التّشكيلة على استقامة واحدة. يمكن تقسيم المستوي إلى مناطق بواسطة خطوط مستقيمة. يوصف هذا التّقسيم بالخطوط المستقيمة للتّشكيلة الكولومبيّة بأنّه جيّد إذا تحقّق فيه ما يلي:
- لا يمرّ أيّ من الخطوط المستقيمة بأيّ نقطة من التّشكيلة.
- لا تحوي أيّ من المناطق على نقطتين بلونين مختلفين.
جد أصغر قيمة للعدد \(k\) بحيث يوجد لأيّ تشكيلة كولومبيّة من \(4027\) نقطة، تقسيم جيّد بواسطة \(k\) من الخطوط المستقيمة.
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الإجابة
\[ \boxed{k=2013}. \]
الحل
نثبت أولًا أن 2013 مستقيمًا تكفي دائمًا.
لكل نقطتين من اللون نفسه، لا يحتوي المستقيم الواصل بينهما على أي نقطة أخرى من التشكيلة. لذلك يمكننا رسم مستقيمين متوازيين على جانبيه، قريبين منه بما يكفي ليحتوي الشريط المفتوح المحصور بينهما على هاتين النقطتين فقط. ولا يمر أي من مستقيمي الحد بأي نقطة من التشكيلة: نختار نصف عرض الشريط أصغر من أدنى مسافة بين أي نقطة أخرى والمستقيم الواصل بين النقطتين.
سنغطي جميع نقاط أحد اللونين بأشرطة من هذا النوع وبنصف مستوٍ واحد، بحيث لا يحتوي أي منها على نقطة من اللون الآخر. وعندئذ يعطي رسم المستقيمات التي تحدها تقسيمًا جيدًا. بالفعل، تقع أي منطقة تحتوي على نقطة مغطاة بكاملها داخل كل شريط أو نصف مستوٍ يحتوي على تلك النقطة، لأن حدوده من مستقيمات التقسيم.
ليكن \(H\) الغلاف المحدب للتشكيلة. لدينا حالتان.
الحالة 1: أحد رؤوس \(H\) أحمر.
ليكن هذا الرأس \(R\). يوجد مستقيم داعم لـ\(H\) تكون نقطة التقائه الوحيدة مع \(H\) هي \(R\): نختار اتجاهه بين اتجاهي الضلعين الداعمين الملتقيين عند \(R\) تمامًا. وبإزاحة هذا المستقيم مسافة صغيرة بما يكفي نحو داخل \(H\)، نحصل على مستقيم يفصل \(R\) عن كل نقطة أخرى، ولا يمر بأي نقطة. ومن ثم يحتوي أحد نصفي المستوي المفتوحين اللذين يحددهما على \(R\) فقط.
نقسم النقاط الحمراء الـ2012 الباقية إلى 1006 أزواج، ونحيط كل زوج بشريط كما وصفنا أعلاه. أصبحت جميع النقاط الحمراء مغطاة بنصف مستوٍ وأشرطة لا تحتوي على نقاط زرقاء. وتعطي حدودها تقسيمًا جيدًا يستخدم على الأكثر \[ 1+2\cdot1006=2013 \] مستقيمًا.
الحالة 2: كل رأس من رؤوس \(H\) أزرق.
نختار ضلعًا \(UV\) من أضلاع \(H\). طرفاه أزرقان، وتقع جميع النقاط الأخرى في جهة واحدة من المستقيم \(UV\) دون أن تقع عليه، إذ لا توجد ثلاث نقاط على استقامة واحدة. ولذلك فإن إزاحة هذا المستقيم مسافة صغيرة بما يكفي نحو داخل \(H\) تنتج مستقيمًا يفصل \(U,V\) عن جميع النقاط الأخرى، دون أن يمر بأي نقطة.
نقسم النقاط الزرقاء الـ2012 الباقية إلى 1006 أزواج، ونحيط كل زوج بشريط. أصبحت جميع النقاط الزرقاء مغطاة بنصف مستوٍ وأشرطة لا تحتوي على نقاط حمراء. ومرة أخرى تعطي حدودها تقسيمًا جيدًا يستخدم على الأكثر \[ 1+2\cdot1006=2013 \] مستقيمًا.
إذا نتج عن الإنشاء عدد أقل من المستقيمات المختلفة، أمكننا إضافة مستقيمات تتجنب جميع نقاط التشكيلة حتى يصبح عددها 2013 بالضبط. ولا تؤدي إضافة المستقيمات إلا إلى تقسيم المناطق الموجودة إلى مناطق أصغر، ولذلك يبقى التقسيم جيدًا.
نبين الآن أن عددًا أقل من المستقيمات لا يكفي دائمًا.
نضع 4027 نقطة مختلفة على دائرة، ونلونها وفق الترتيب الدوري الآتي: \[ B_0,R_1,B_1,R_2,B_2,\ldots,R_{2013},B_{2013}. \] هذه تشكيلة كولومبية، لأن المستقيم يلتقي الدائرة في نقطتين على الأكثر. ومن بين أضلاع المضلع المحدب الذي تشكله هذه النقاط، وعددها 4027، يوجد 4026 ضلعًا بالضبط طرفا كل منها مختلفا اللون؛ أما الضلع \(B_{2013}B_0\) وحده فطرفاه من اللون نفسه.
في أي تقسيم جيد، يجب أن يقطع مستقيم واحد على الأقل كل ضلع من تلك الأضلاع الـ4026. وإلا فإن قطعة الضلع بأكملها ستتجنب جميع المستقيمات، فتصل بين طرفيها المختلفي اللون داخل منطقة واحدة.
كل مستقيم يتجنب رؤوس المضلع يقطع ضلعين على الأكثر: فتقاطعه مع المضلع المحدب، متى كان غير خالٍ، قطعة مستقيمة، ولا يحدث قطع الأضلاع إلا عند طرفي هذه القطعة. ومن ثم فإن تقسيمًا بـ\(k\) من المستقيمات يمكن أن يقطع على الأكثر \(2k\) من الأضلاع الـ4026 المطلوب قطعها. وبالتالي \[ 2k\ge4026, \qquad\text{ومن ثم}\qquad k\ge2013. \]
وبالاقتران مع الإنشاء السابق، يثبت هذا أن أصغر قيمة هي \(\boxed{2013}\).
تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.