IMO 2014 · Problem 6
A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large \(n\), in any set of \(n\) lines in general position it is possible to colour at least \(\sqrt{n}\) of the lines blue in such a way that none of its finite regions has a completely blue boundary.
Note: Results with \(\sqrt{n}\) replaced by \(c\sqrt{n}\) will be awarded points depending on the value of the constant \(c\).
Official text of the problem. Official problem paper (PDF)
Solution
We prove the stronger assertion that the required colouring exists for every positive integer \(n\). Throughout the proof, regions refer to the regions of the original arrangement of all \(n\) lines.
Choose an inclusion-maximal set \(B\) of lines such that no finite region has all its boundary lines in \(B\). Such a set exists because the empty set has this property and there are only finitely many subsets of lines. Colour the lines in \(B\) blue and all remaining lines red, and put \(k=|B|\).
For every red line \(r\), maximality implies that changing \(r\) to blue would produce a finite region with a completely blue boundary. Consequently, there is a finite region \(F_r\) whose only red boundary line is \(r\). Choose one such region for each red line and call these regions marked. There are exactly \(n-k\) marked regions, and their red boundary lines are pairwise distinct.
Every finite region is a convex polygon: it is the intersection of the half-planes determined by its boundary lines. Each line contributes at most one side. Thus a marked region with \(s\) sides has one red side and \(s-1\) blue sides. The two endpoints of its red side are intersections of a red and a blue line, while its other \(s-2\) vertices are intersections of two blue lines. Call these latter intersections blue vertices.
We first establish a restriction on marked triangles. Let \(T\) be a marked triangle, let \(r\) be its red boundary line, and let \(v\) be its unique blue vertex. Consider either blue side of \(T\), and the region immediately across that side. At the endpoint different from \(v\), the blue side meets \(r\). Because no third line passes through this point, \(r\) also supplies a boundary side of the adjacent region. If that region were marked, its unique red boundary line would therefore be \(r\), contradicting the fact that distinct marked regions have distinct red boundary lines.
Hence, at the blue vertex of a marked triangle, the two neighbouring sectors belong to unmarked regions.
Now assign weights to blue vertices as follows:
- Each marked triangle contributes weight \(2\) to its unique blue vertex.
- Each marked region with at least four sides contributes weight \(1\) to each of its blue vertices.
A marked region with \(s\geq4\) sides has \(s-2\geq2\) blue vertices. Therefore every marked region contributes total weight at least \(2\), and the total weight is at least \[ 2(n-k). \]
On the other hand, the weight received by any blue vertex is at most \(4\). Indeed, exactly four regions meet there, one in each sector.
- If none is a marked triangle, each contributes at most \(1\), giving total weight at most \(4\).
- If exactly one is a marked triangle, its two neighbouring sectors are unmarked. Only the opposite sector can contribute further weight, so the total is at most \(2+1=3\).
- If two are marked triangles, they must occupy opposite sectors, and the other two sectors are unmarked. The total weight is \(2+2=4\).
More than two marked triangles are impossible by the same neighbouring-sector restriction.
Since the blue lines are in general position, they determine exactly \(\binom{k}{2}\) distinct blue vertices. Summing the weight bounds gives \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] Thus \[ n-k\leq k^2-k, \qquad\text{so}\qquad n\leq k^2. \] Therefore \(k\geq\sqrt n\). By the defining property of \(B\), these blue lines give the required colouring. \(\square\)
The solution was checked against the official IMO shortlist solutions.
IMO 2014 · Aufgabe 6
Eine Menge von Geraden in der Ebene ist in allgemeiner Lage, falls keine zwei Geraden parallel sind und keine drei einen gemeinsamen Punkt haben. Eine Menge von Geraden in allgemeiner Lage teilt die Ebene in Bereiche auf. Diejenigen dieser Bereiche, die eine endliche Fläche besitzen, nennen wir endliche Bereiche. Man beweise für alle hinreichend große \(n\), dass es für jede Menge von \(n\) Geraden in allgemeiner Lage möglich ist, mindestens \(\sqrt n\) der Geraden blau zu färben, sodass keiner ihrer endlichen Bereiche komplett blau umrandet ist.
Hinweis: Falls die Behauptung für \(c\sqrt n\) statt \(\sqrt n\) bewiesen wird, werden, abhängig von der Konstanten \(c\), Punkte vergeben.
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Lösung
Wir beweisen die stärkere Aussage, dass die geforderte Färbung für jede positive ganze Zahl \(n\) existiert. Im gesamten Beweis sind mit Bereichen die Bereiche der ursprünglichen Anordnung aller \(n\) Geraden gemeint.
Wir wählen eine bezüglich Inklusion maximale Menge \(B\) von Geraden, sodass bei keinem endlichen Bereich alle Randgeraden in \(B\) liegen. Eine solche Menge existiert, da die leere Menge diese Eigenschaft besitzt und es nur endlich viele Teilmengen der Geradenmenge gibt. Wir färben die Geraden in \(B\) blau und alle übrigen Geraden rot und setzen \(k=|B|\).
Für jede rote Gerade \(r\) folgt aus der Maximalität, dass durch Umfärben von \(r\) in Blau ein endlicher Bereich mit vollständig blauem Rand entstehen würde. Folglich gibt es einen endlichen Bereich \(F_r\), dessen einzige rote Randgerade \(r\) ist. Für jede rote Gerade wählen wir einen solchen Bereich und nennen diese Bereiche markiert. Es gibt genau \(n-k\) markierte Bereiche, und ihre roten Randgeraden sind paarweise verschieden.
Jeder endliche Bereich ist ein konvexes Vieleck: Er ist der Schnitt der durch seine Randgeraden bestimmten Halbebenen. Jede Gerade trägt höchstens eine Seite bei. Ein markierter Bereich mit \(s\) Seiten hat somit eine rote Seite und \(s-1\) blaue Seiten. Die beiden Endpunkte seiner roten Seite sind Schnittpunkte einer roten und einer blauen Geraden, während seine übrigen \(s-2\) Eckpunkte Schnittpunkte zweier blauer Geraden sind. Diese letzteren Schnittpunkte nennen wir blaue Eckpunkte.
Zunächst leiten wir eine Einschränkung für markierte Dreiecke her. Sei \(T\) ein markiertes Dreieck, \(r\) seine rote Randgerade und \(v\) sein einziger blauer Eckpunkt. Wir betrachten eine beliebige blaue Seite von \(T\) und den unmittelbar jenseits dieser Seite liegenden Bereich. Am von \(v\) verschiedenen Endpunkt trifft die blaue Seite auf \(r\). Da keine dritte Gerade durch diesen Punkt geht, liegt auch eine Randseite des benachbarten Bereichs auf \(r\). Wäre dieser Bereich markiert, so wäre seine einzige rote Randgerade daher \(r\), im Widerspruch dazu, dass verschiedene markierte Bereiche verschiedene rote Randgeraden haben.
Am blauen Eckpunkt eines markierten Dreiecks gehören die beiden benachbarten Sektoren also zu unmarkierten Bereichen.
Nun weisen wir den blauen Eckpunkten wie folgt Gewichte zu:
- Jedes markierte Dreieck trägt zu seinem einzigen blauen Eckpunkt das Gewicht \(2\) bei.
- Jeder markierte Bereich mit mindestens vier Seiten trägt zu jedem seiner blauen Eckpunkte das Gewicht \(1\) bei.
Ein markierter Bereich mit \(s\geq4\) Seiten hat \(s-2\geq2\) blaue Eckpunkte. Daher trägt jeder markierte Bereich insgesamt mindestens das Gewicht \(2\) bei, und das Gesamtgewicht beträgt mindestens \[ 2(n-k). \]
Andererseits erhält jeder blaue Eckpunkt höchstens das Gewicht \(4\). Dort treffen nämlich genau vier Bereiche zusammen, einer in jedem Sektor.
- Ist keiner davon ein markiertes Dreieck, so trägt jeder höchstens \(1\) bei, was ein Gesamtgewicht von höchstens \(4\) ergibt.
- Ist genau einer ein markiertes Dreieck, so sind seine beiden benachbarten Sektoren unmarkiert. Nur der gegenüberliegende Sektor kann weiteres Gewicht beitragen, also beträgt die Summe höchstens \(2+1=3\).
- Sind zwei davon markierte Dreiecke, so müssen sie gegenüberliegende Sektoren einnehmen, und die anderen beiden Sektoren sind unmarkiert. Das Gesamtgewicht ist \(2+2=4\).
Mehr als zwei markierte Dreiecke sind aufgrund derselben Einschränkung für benachbarte Sektoren unmöglich.
Da die blauen Geraden in allgemeiner Lage sind, bestimmen sie genau \(\binom{k}{2}\) verschiedene blaue Eckpunkte. Durch Summieren der Gewichtsschranken erhalten wir \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] Somit gilt \[ n-k\leq k^2-k, \qquad\text{also}\qquad n\leq k^2. \] Folglich ist \(k\geq\sqrt n\). Nach der definierenden Eigenschaft von \(B\) liefern diese blauen Geraden die geforderte Färbung. \(\square\)
Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.
IMO 2014 · Soru 6
Düzlemde herhangi ikisi paralel olmayan ve herhangi üçü noktadaş olmayan doğrulara genel durum özelliği olan doğrular diyelim. Genel durum özelliği olan doğrular, düzlemi bazılarının alanları sonlu olan bölgelere ayırıyor; alanı sonlu olan her bölgeye sonlu bölge diyelim. \(n\) nin yeterince büyük tüm değerleri için, genel durum özelliği olan herhangi \(n\) doğrunun en az \(\sqrt{n}\) tanesinin mavi renge; hiçbir sonlu bölgenin tüm sınırları mavi olmayacak biçimde boyanabileceğini gösteriniz.
Not: Soruyu \(\sqrt{n}\) yerine \(c\sqrt{n}\) için çözenlere \(c\) sabitinin değerine göre puan verilecektir.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Çözüm
İstenen boyamanın her pozitif \(n\) tam sayısı için var olduğu şeklindeki daha güçlü iddiayı kanıtlayacağız. Kanıt boyunca bölgeler denildiğinde, başlangıçtaki \(n\) doğrunun tümünün oluşturduğu düzenlemenin bölgeleri kastedilecektir.
Hiçbir sonlu bölgenin tüm sınır doğrularının içinde bulunmadığı, içerilmeye göre maksimal bir \(B\) doğrular kümesi seçelim. Boş küme bu özelliğe sahip olduğundan ve doğruların yalnızca sonlu sayıda alt kümesi bulunduğundan böyle bir küme vardır. \(B\)'deki doğruları maviye, kalan tüm doğruları kırmızıya boyayalım ve \(k=|B|\) alalım.
Her kırmızı \(r\) doğrusu için maksimallik, \(r\)'nin rengini maviye değiştirmenin sınırı tamamen mavi olan bir sonlu bölge oluşturacağını gösterir. Dolayısıyla tek kırmızı sınır doğrusu \(r\) olan bir \(F_r\) sonlu bölgesi vardır. Her kırmızı doğru için böyle bir bölge seçelim ve bu bölgelere işaretli diyelim. Tam olarak \(n-k\) işaretli bölge vardır ve bunların kırmızı sınır doğruları ikişer ikişer farklıdır.
Her sonlu bölge konveks bir çokgendir: sınır doğrularının belirlediği yarı düzlemlerin kesişimidir. Her doğru en fazla bir kenar oluşturur. Dolayısıyla \(s\) kenarlı işaretli bir bölgenin bir kırmızı kenarı ve \(s-1\) mavi kenarı vardır. Kırmızı kenarının iki uç noktası, bir kırmızı doğruyla bir mavi doğrunun kesişimidir; diğer \(s-2\) köşesi ise iki mavi doğrunun kesişimidir. Bu son kesişimlere mavi köşeler diyelim.
Önce işaretli üçgenler için bir kısıtlama ortaya koyacağız. \(T\) işaretli bir üçgen, \(r\) bu üçgenin kırmızı sınır doğrusu ve \(v\) tek mavi köşesi olsun. \(T\)'nin mavi kenarlarından herhangi birini ve bu kenarın hemen karşı tarafındaki bölgeyi ele alalım. Mavi kenar, \(v\)'den farklı olan uç noktasında \(r\) ile kesişir. Bu noktadan üçüncü bir doğru geçmediğinden \(r\), komşu bölgenin de bir sınır kenarını oluşturur. Bu bölge işaretli olsaydı, tek kırmızı sınır doğrusu da \(r\) olurdu; bu ise farklı işaretli bölgelerin kırmızı sınır doğrularının farklı olmasıyla çelişir.
Dolayısıyla işaretli bir üçgenin mavi köşesinde, iki komşu açısal bölge işaretli olmayan bölgelere aittir.
Şimdi mavi köşelere aşağıdaki gibi ağırlıklar verelim:
- Her işaretli üçgen, tek mavi köşesine \(2\) ağırlık verir.
- En az dört kenarlı her işaretli bölge, mavi köşelerinin her birine \(1\) ağırlık verir.
\(s\geq4\) kenarlı işaretli bir bölgenin \(s-2\geq2\) mavi köşesi vardır. Dolayısıyla her işaretli bölgenin verdiği toplam ağırlık en az \(2\)'dir ve toplam ağırlık en az \[ 2(n-k) \] olur.
Öte yandan, herhangi bir mavi köşenin aldığı ağırlık en fazla \(4\)'tür. Gerçekten de burada, her açısal bölgede bir tane olmak üzere tam olarak dört bölge buluşur.
- Hiçbiri işaretli bir üçgen değilse, her biri en fazla \(1\) ağırlık verir ve toplam ağırlık en fazla \(4\) olur.
- Tam olarak biri işaretli bir üçgense, ona komşu iki açısal bölgedeki bölgeler işaretli değildir. Yalnızca karşı açısal bölge ek ağırlık verebilir; dolayısıyla toplam en fazla \(2+1=3\) olur.
- İkisi işaretli üçgense, bunlar karşı açısal bölgelerde bulunmalıdır ve diğer iki açısal bölgedeki bölgeler işaretli değildir. Toplam ağırlık \(2+2=4\) olur.
Aynı komşu açısal bölge kısıtlaması nedeniyle ikiden fazla işaretli üçgen bulunması mümkün değildir.
Mavi doğrular genel durum özelliğine sahip olduklarından, tam olarak \(\binom{k}{2}\) farklı mavi köşe belirlerler. Ağırlık sınırlarını toplayarak \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1) \] elde ederiz. Böylece \[ n-k\leq k^2-k, \qquad\text{dolayısıyla}\qquad n\leq k^2. \] O hâlde \(k\geq\sqrt n\) olur. \(B\)'nin tanımlayıcı özelliği gereği, bu mavi doğrular istenen boyamayı verir. \(\square\)
Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.
IMO 2014 · Problema 6
Un conjunto de rectas en el plano está en posición general si no hay dos que sean paralelas ni tres que pasen por el mismo punto. Un conjunto de rectas en posición general separa el plano en regiones, algunas de las cuales tienen área finita; a estas las llamamos sus regiones finitas. Demostrar que para cada \(n\) suficientemente grande, en cualquier conjunto de \(n\) rectas en posición general es posible colorear de azul al menos \(\sqrt{n}\) de ellas de tal manera que ninguna de sus regiones finitas tenga todos los lados de su frontera azules.
Nota: A las soluciones que reemplacen \(\sqrt{n}\) por \(c\sqrt{n}\) se les otorgarán puntos dependiendo del valor de \(c\).
Texto oficial en español del problema. Enunciado oficial (PDF)
Solución
Demostraremos la afirmación más fuerte de que la coloración requerida existe para todo entero positivo \(n\). A lo largo de la demostración, las regiones son las de la disposición original de las \(n\) rectas.
Elijamos un conjunto \(B\) de rectas maximal por inclusión tal que ninguna región finita tenga todas las rectas de su frontera en \(B\). Tal conjunto existe porque el conjunto vacío tiene esta propiedad y solo hay un número finito de subconjuntos de rectas. Coloreemos de azul las rectas de \(B\) y de rojo todas las rectas restantes, y pongamos \(k=|B|\).
Para cada recta roja \(r\), la maximalidad implica que cambiar el color de \(r\) a azul produciría una región finita con la frontera completamente azul. Por consiguiente, existe una región finita \(F_r\) cuya única recta roja de la frontera es \(r\). Elijamos una de estas regiones para cada recta roja y llamemos marcadas a estas regiones. Hay exactamente \(n-k\) regiones marcadas, y las rectas rojas de sus fronteras son distintas dos a dos.
Toda región finita es un polígono convexo: es la intersección de los semiplanos determinados por las rectas de su frontera. Cada recta aporta a lo sumo un lado. Así, una región marcada de \(s\) lados tiene un lado rojo y \(s-1\) lados azules. Los dos extremos de su lado rojo son intersecciones de una recta roja y una azul, mientras que sus otros \(s-2\) vértices son intersecciones de dos rectas azules. Llamemos vértices azules a estas últimas intersecciones.
Primero estableceremos una restricción para los triángulos marcados. Sea \(T\) un triángulo marcado, sea \(r\) la recta roja de su frontera y sea \(v\) su único vértice azul. Consideremos cualquiera de los dos lados azules de \(T\) y la región situada inmediatamente al otro lado de ese lado. En el extremo distinto de \(v\), el lado azul se encuentra con \(r\). Como ninguna tercera recta pasa por este punto, \(r\) también contiene un lado de la frontera de la región adyacente. Si esa región estuviera marcada, su única recta roja de la frontera sería, por tanto, \(r\), lo que contradice que regiones marcadas distintas tienen rectas rojas distintas en sus fronteras.
Por tanto, en el vértice azul de un triángulo marcado, los dos sectores vecinos pertenecen a regiones no marcadas.
Asignemos ahora pesos a los vértices azules de la siguiente manera:
- Cada triángulo marcado aporta un peso de \(2\) a su único vértice azul.
- Cada región marcada de al menos cuatro lados aporta un peso de \(1\) a cada uno de sus vértices azules.
Una región marcada de \(s\geq4\) lados tiene \(s-2\geq2\) vértices azules. Por tanto, cada región marcada aporta un peso total de al menos \(2\), y el peso total es al menos \[ 2(n-k). \]
Por otra parte, el peso recibido por cualquier vértice azul es a lo sumo \(4\). En efecto, en él se encuentran exactamente cuatro regiones, una en cada sector.
- Si ninguna es un triángulo marcado, cada una aporta a lo sumo \(1\), lo que da un peso total de a lo sumo \(4\).
- Si exactamente una es un triángulo marcado, sus dos sectores vecinos no están marcados. Solo el sector opuesto puede aportar peso adicional, de modo que el total es a lo sumo \(2+1=3\).
- Si dos son triángulos marcados, deben ocupar sectores opuestos, y los otros dos sectores no están marcados. El peso total es \(2+2=4\).
No puede haber más de dos triángulos marcados por la misma restricción sobre los sectores vecinos.
Como las rectas azules están en posición general, determinan exactamente \(\binom{k}{2}\) vértices azules distintos. Sumando las cotas de los pesos, obtenemos \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] Así, \[ n-k\leq k^2-k, \qquad\text{por tanto}\qquad n\leq k^2. \] Por tanto, \(k\geq\sqrt n\). Por la propiedad que define a \(B\), estas rectas azules dan la coloración requerida. \(\square\)
La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.
IMO 2014 · 问题 6
平面上的一族直线被称为是 处于一般位置的, 如果其中没有两条直线平行, 没有三条直线共点. 一族处于一般位置的直线把平面分割成若干区域, 我们把其中面积有限的区域称为这族直线的 有限区域. 证明: 对于充分大的 \(n\) 和任意处于一般位置的 \(n\) 条直线, 我们都可以把其中至少 \(\sqrt n\) 条直线染成蓝色, 使得每一个有限区域的边界都不全是蓝色的.
注: 如果你的答卷上证明的是 \(c\sqrt n\)(而不是 \(\sqrt n\)) 的情形, 那么将会根据常数 \(c\) 的值给分.
题目为官方中文译本。 官方试卷 (PDF)
解答
我们证明一个更强的断言：对每个正整数 \(n\)，都存在所要求的染色。在整个证明中，区域均指原来全部 \(n\) 条直线所划分出的区域。
选取一个按包含关系极大的直线集合 \(B\)，使得没有任何有限区域的所有边界直线都属于 \(B\)。这样的集合存在，因为空集具有此性质，而且直线集合的子集只有有限个。将 \(B\) 中的直线染成蓝色，其余直线全部染成红色，并记 \(k=|B|\)。
对于每条红色直线 \(r\)，由极大性可知，将 \(r\) 改染为蓝色就会产生一个边界全为蓝色的有限区域。因此，存在一个有限区域 \(F_r\)，其唯一的红色边界直线为 \(r\)。对每条红色直线选取一个这样的区域，并称这些区域为标记区域。标记区域恰有 \(n-k\) 个，且它们的红色边界直线两两不同。
每个有限区域都是凸多边形：它是由其边界直线所确定的半平面的交集。每条直线至多提供一条边。因此，一个有 \(s\) 条边的标记区域有一条红边和 \(s-1\) 条蓝边。红边的两个端点都是一条红色直线与一条蓝色直线的交点，其余 \(s-2\) 个顶点则都是两条蓝色直线的交点。称后一类交点为蓝色顶点。
我们先证明关于标记三角形的一条限制。设 \(T\) 是一个标记三角形，\(r\) 是其红色边界直线，\(v\) 是其唯一的蓝色顶点。考虑 \(T\) 的任意一条蓝边，以及紧邻这条边另一侧的区域。在不同于 \(v\) 的那个端点处，这条蓝边与 \(r\) 相交。由于没有第三条直线经过此点，\(r\) 也提供了相邻区域的一条边界边。如果该区域是标记区域，那么其唯一的红色边界直线也必为 \(r\)，这与不同标记区域的红色边界直线互不相同矛盾。
因此，在一个标记三角形的蓝色顶点处，与该三角形所在扇形相邻的两个扇形均属于未标记区域。
现在，按以下方式给蓝色顶点赋予权重：
- 每个标记三角形向其唯一的蓝色顶点贡献权重 \(2\)。
- 每个至少有四条边的标记区域向其每个蓝色顶点贡献权重 \(1\)。
一个有 \(s\geq4\) 条边的标记区域有 \(s-2\geq2\) 个蓝色顶点。因此，每个标记区域贡献的总权重至少为 \(2\)，故总权重至少为 \[ 2(n-k). \]
另一方面，每个蓝色顶点收到的权重至多为 \(4\)。事实上，恰有四个区域在此相交，每个扇形内各有一个。
- 如果其中没有标记三角形，则每个区域至多贡献 \(1\)，总权重至多为 \(4\)。
- 如果其中恰有一个标记三角形，则其相邻的两个扇形均未被标记。只有对面的扇形还能贡献权重，所以总权重至多为 \(2+1=3\)。
- 如果其中有两个标记三角形，则它们必定位于相对的两个扇形内，而另外两个扇形均未被标记。总权重为 \(2+2=4\)。
由同一条相邻扇形的限制可知，不可能出现两个以上的标记三角形。
由于蓝色直线处于一般位置，它们恰好确定 \(\binom{k}{2}\) 个不同的蓝色顶点。将权重的界求和，得到 \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] 因此 \[ n-k\leq k^2-k, \qquad\text{所以}\qquad n\leq k^2. \] 故 \(k\geq\sqrt n\)。由 \(B\) 的定义性质，这些蓝色直线给出了所要求的染色。\(\square\)
解答已与 IMO 官方预选题（shortlist）解答核对。
IMO 2014 · Задача 6
Будем говорить, что прямые на плоскости являются прямыми общего положения, если никакие две из них не параллельны и никакие три из них не проходят через одну точку. Любые несколько прямых общего положения разбивают плоскость на части; ограниченными частями разбиения будем называть те из частей, которые имеют конечную площадь. Докажите, что для всех достаточно больших \(n\) верно следующее утверждение: в каждом множестве из \(n\) прямых общего положения можно покрасить не менее \(\sqrt n\) прямых в синий цвет так, чтобы граница любой из ограниченных частей разбиения не оказалась полностью синей.
Замечание: за доказательство утверждения задачи, в котором \(\sqrt n\) заменено на \(c\sqrt n\), будут начисляться баллы, в зависимости от константы \(c\).
Официальный русский текст задачи. Официальный текст задач (PDF)
Решение
Докажем более сильное утверждение: требуемая раскраска существует для каждого положительного целого \(n\). На протяжении всего доказательства под частями понимаются части исходного разбиения всеми \(n\) прямыми.
Выберем максимальное по включению множество \(B\) прямых такое, что ни у одной ограниченной части все прямые, содержащие её стороны, не принадлежат \(B\). Такое множество существует, поскольку пустое множество обладает этим свойством, а число подмножеств множества прямых конечно. Покрасим прямые из \(B\) в синий цвет, а все остальные прямые — в красный и положим \(k=|B|\).
Для каждой красной прямой \(r\) из максимальности следует, что её перекрашивание в синий цвет привело бы к появлению ограниченной части с полностью синей границей. Следовательно, существует ограниченная часть \(F_r\), у которой единственная красная прямая, содержащая сторону, — это \(r\). Выберем по одной такой части для каждой красной прямой и назовём эти части отмеченными. Имеется ровно \(n-k\) отмеченных частей, и красные прямые, содержащие их стороны, попарно различны.
Каждая ограниченная часть является выпуклым многоугольником: она представляет собой пересечение полуплоскостей, определяемых прямыми, содержащими её стороны. Каждая прямая содержит не более одной стороны. Поэтому у отмеченной части с \(s\) сторонами одна сторона красная, а \(s-1\) сторон синие. Два конца её красной стороны являются точками пересечения красной и синей прямых, а остальные \(s-2\) вершины — точками пересечения двух синих прямых. Назовём эти последние точки пересечения синими вершинами.
Сначала установим ограничение для отмеченных треугольников. Пусть \(T\) — отмеченный треугольник, \(r\) — прямая, содержащая его красную сторону, а \(v\) — его единственная синяя вершина. Рассмотрим любую синюю сторону \(T\) и часть разбиения, непосредственно прилегающую к ней с другой стороны. В конце, отличном от \(v\), синяя сторона встречается с \(r\). Поскольку через эту точку не проходит третья прямая, \(r\) содержит также сторону соседней части. Если бы эта часть была отмеченной, единственной красной прямой, содержащей её сторону, также была бы \(r\), что противоречит тому, что у различных отмеченных частей красные прямые, содержащие их стороны, различны.
Следовательно, при синей вершине отмеченного треугольника два соседних сектора принадлежат неотмеченным частям.
Теперь припишем синим вершинам веса следующим образом:
- Каждый отмеченный треугольник добавляет вес \(2\) своей единственной синей вершине.
- Каждая отмеченная часть, у которой не менее четырёх сторон, добавляет вес \(1\) каждой своей синей вершине.
У отмеченной части с \(s\geq4\) сторонами имеется \(s-2\geq2\) синих вершин. Поэтому каждая отмеченная часть добавляет суммарный вес не менее \(2\), и общий вес не меньше \[ 2(n-k). \]
С другой стороны, вес, полученный любой синей вершиной, не превосходит \(4\). Действительно, в ней сходятся ровно четыре части, по одной в каждом секторе.
- Если ни одна из них не является отмеченным треугольником, каждая добавляет не более \(1\), что даёт общий вес не более \(4\).
- Если ровно одна является отмеченным треугольником, два соседних с ней сектора не отмечены. Дополнительный вес может дать только противоположный сектор, поэтому общий вес не превосходит \(2+1=3\).
- Если две являются отмеченными треугольниками, они должны занимать противоположные секторы, а два остальных сектора не отмечены. Общий вес равен \(2+2=4\).
Более двух отмеченных треугольников быть не может в силу того же ограничения на соседние секторы.
Поскольку синие прямые находятся в общем положении, они определяют ровно \(\binom{k}{2}\) различных синих вершин. Суммируя оценки весов, получаем \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] Таким образом, \[ n-k\leq k^2-k, \qquad\text{откуда}\qquad n\leq k^2. \] Следовательно, \(k\geq\sqrt n\). По определяющему свойству \(B\) эти синие прямые дают требуемую раскраску. \(\square\)
Решение проверено по официальным решениям шортлиста IMO.
IMO 2014 · المسألة 6
يقال عن مجموعة مستقيمات في المستوى إنّها في الوضع العام إذا لم يتواز أيّ مستقيمين فيها ولم يتقاطع أيّ ثلاث مستقيمات فيها في نقطة واحدة. تُجزّئ أيّ مجموعة من المستقيمات في الوضع العام المستوى إلى مناطق تكون مساحة بعضها منتهية. نشير إلى هذه المناطق على أنّها مناطق منتهية. برهن أنّه لكلّ عدد \(n\)، كبير بما فيه الكفاية، يمكننا التلوين بالأزرق \(\sqrt{n}\) مستقيما على الأقل وذلك في أيّ مجموعة مكوّنة من \(n\) مستقيما في الوضع العام، بحيث لا توجد منطقة منتهية جميع حدودها مستقيمات زرقاء.
ملاحظة: تعطى درجات لمن يحصل على \(c\sqrt{n}\) بدلا من \(\sqrt{n}\) وذلك اعتمادا على قيمة الثابت \(c\).
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الحل
نثبت العبارة الأقوى، وهي أنّ التلوين المطلوب موجود لكل عدد صحيح موجب \(n\). طوال البرهان، يُقصد بالمناطق مناطق الترتيب الأصلي لجميع المستقيمات \(n\).
نختار مجموعة \(B\) من المستقيمات عظمى بالنسبة إلى الاحتواء، بحيث لا توجد منطقة منتهية تنتمي جميع مستقيمات حدودها إلى \(B\). توجد مثل هذه المجموعة لأنّ المجموعة الخالية تتمتع بهذه الخاصية، ولأنّ عدد المجموعات الجزئية من المستقيمات منته. نلوّن المستقيمات في \(B\) بالأزرق وجميع المستقيمات المتبقية بالأحمر، ونضع \(k=|B|\).
لكل مستقيم أحمر \(r\)، تقتضي عظمية المجموعة أنّ تغيير لون \(r\) إلى الأزرق سيُنتج منطقة منتهية حدودها زرقاء بالكامل. وبالتالي، توجد منطقة منتهية \(F_r\) يكون \(r\) مستقيم حدودها الأحمر الوحيد. نختار منطقة واحدة من هذا النوع لكل مستقيم أحمر ونسمّي هذه المناطق معلّمة. يوجد بالضبط \(n-k\) منطقة معلّمة، ومستقيمات حدودها الحمراء مختلفة مثنى مثنى.
كل منطقة منتهية هي مضلّع محدّب: فهي تقاطع أنصاف المستويات التي تحدّدها مستقيمات حدودها. ويساهم كل مستقيم بضلع واحد على الأكثر. ومن ثمّ فإنّ المنطقة المعلّمة ذات \(s\) أضلاع لها ضلع أحمر واحد و\(s-1\) ضلع أزرق. طرفا ضلعها الأحمر هما نقطتا تقاطع مستقيم أحمر ومستقيم أزرق، أما رؤوسها الأخرى وعددها \(s-2\) فهي نقاط تقاطع مستقيمين أزرقين. نسمّي نقاط التقاطع الأخيرة هذه رؤوسا زرقاء.
نثبت أولا قيدا على المثلثات المعلّمة. ليكن \(T\) مثلثا معلّما، وليكن \(r\) مستقيم حدوده الأحمر، وليكن \(v\) رأسه الأزرق الوحيد. لننظر إلى أيّ من ضلعي \(T\) الأزرقين، وإلى المنطقة المجاورة له مباشرة من الجهة الأخرى لذلك الضلع. عند الطرف المختلف عن \(v\)، يلتقي الضلع الأزرق بالمستقيم \(r\). وبما أنّه لا يمرّ مستقيم ثالث بهذه النقطة، فإنّ \(r\) يحتوي أيضا على ضلع من حدود المنطقة المجاورة. لو كانت تلك المنطقة معلّمة، لكان مستقيم حدودها الأحمر الوحيد هو \(r\)، وهذا يناقض كون المناطق المعلّمة المختلفة ذات مستقيمات حدود حمراء مختلفة.
إذن، عند الرأس الأزرق لمثلث معلّم، ينتمي القطاعان المجاوران إلى منطقتين غير معلّمتين.
نوزّع الآن أوزانا على الرؤوس الزرقاء كما يلي:
- يساهم كل مثلث معلّم بوزن \(2\) عند رأسه الأزرق الوحيد.
- تساهم كل منطقة معلّمة لها أربعة أضلاع على الأقل بوزن \(1\) عند كل رأس من رؤوسها الزرقاء.
للمنطقة المعلّمة ذات \(s\geq4\) أضلاع عدد من الرؤوس الزرقاء يساوي \(s-2\geq2\). ولذلك تساهم كل منطقة معلّمة بوزن إجمالي لا يقلّ عن \(2\)، ويكون الوزن الإجمالي على الأقل \[ 2(n-k). \]
من جهة أخرى، لا يتجاوز الوزن الذي يتلقّاه أي رأس أزرق \(4\). بالفعل، تلتقي عنده أربع مناطق بالضبط، واحدة في كل قطاع.
- إذا لم تكن أيّ منها مثلثا معلّما، فإنّ كل واحدة تساهم بوزن لا يتجاوز \(1\)، فيكون الوزن الإجمالي على الأكثر \(4\).
- إذا كانت واحدة منها بالضبط مثلثا معلّما، فإنّ القطاعين المجاورين لها غير معلّمين. ولا يمكن أن يساهم بوزن إضافي إلا القطاع المقابل، ولذلك لا يتجاوز المجموع \(2+1=3\).
- إذا كانت اثنتان منها مثلثين معلّمين، فلا بدّ أن تشغلا قطاعين متقابلين، ويكون القطاعان الآخران غير معلّمين. والوزن الإجمالي هو \(2+2=4\).
يستحيل وجود أكثر من مثلثين معلّمين بموجب القيد نفسه المتعلق بالقطاعين المجاورين.
بما أنّ المستقيمات الزرقاء في الوضع العام، فإنّها تحدّد بالضبط \(\binom{k}{2}\) رأسا أزرق مختلفا. بجمع حدود الأوزان نحصل على \[ 2(n-k)\leq 4\binom{k}{2}=2k(k-1). \] إذن \[ n-k\leq k^2-k, \qquad\text{ومن ثمّ}\qquad n\leq k^2. \] وبالتالي \(k\geq\sqrt n\). وبحسب الخاصية التي عرّفنا بها \(B\)، تعطي هذه المستقيمات الزرقاء التلوين المطلوب. \(\square\)
تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.