IMO 1971 · Problem 5
Prove that for every natural number \(m\), there exists a finite set \(S\) of points in a plane with the following property: For every point \(A\) in \(S\), there are exactly \(m\) points in \(S\) which are at unit distance from \(A\).
Official text of the problem. Official problem paper (PDF)
Solution
We prove the assertion by induction, including \(m=0\). For \(m=0\), a set consisting of one point suffices.
Suppose that a finite nonempty set \(S\) has exactly \(m\) points at unit distance from each of its points. We shall construct a suitable set for \(m+1\) by adjoining a translated copy of \(S\).
Identify the plane with \(\mathbb R^2\), and let \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] We claim that there is a unit vector \(u\) such that, for every \(d\in D\), \[ u\ne d \qquad\text{and}\qquad \|u-d\|\ne1. \] Indeed, for each fixed nonzero \(d\), the first condition excludes at most one point of the unit circle. On that circle, the equality \(\|u-d\|=1\) is equivalent to \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{or}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] Since \(d\ne0\), this is the equation of a line, which meets the unit circle in at most two points. Thus each \(d\) excludes at most three choices of \(u\). Because \(D\) is finite and the unit circle has infinitely many points, the required \(u\) exists.
Now set \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] The two copies are disjoint: an equality \(p=q+u\) would imply \(u=p-q\), which is impossible when \(p=q\) because \(\|u\|=1\), and is excluded by our choice of \(u\) when \(p\ne q\).
Translation preserves distances, so every point has exactly \(m\) unit-distance neighbours within its own copy. Between the two copies, \(p\) and \(p+u\) are at unit distance. Moreover, if \(p,q\in S\) are distinct, then \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] Hence the only unit-distance pairs between the copies are the corresponding pairs \(p,p+u\). Every point of \(T\) therefore has exactly \(m+1\) unit-distance neighbours.
The finite set \(T\) completes the induction, proving the assertion for every natural number \(m\).
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1971 · Aufgabe 5
Beweise, dass es zu jeder natürlichen Zahl \(m\) eine endliche Menge \(S\) von Punkten in einer Ebene mit der folgenden Eigenschaft gibt: Zu jedem Punkt \(A\) in \(S\) gibt es genau \(m\) Punkte in \(S\), die von \(A\) den Abstand eins haben.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir beweisen die Behauptung durch vollständige Induktion, wobei wir \(m=0\) einschließen. Für \(m=0\) genügt eine Menge, die aus einem einzigen Punkt besteht.
Angenommen, eine endliche nichtleere Menge \(S\) enthält zu jedem ihrer Punkte genau \(m\) Punkte im Abstand eins. Wir konstruieren eine geeignete Menge für \(m+1\), indem wir eine verschobene Kopie von \(S\) hinzufügen.
Wir identifizieren die Ebene mit \(\mathbb R^2\) und setzen \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] Wir behaupten, dass es einen Einheitsvektor \(u\) gibt, sodass für jedes \(d\in D\) gilt: \[ u\ne d \qquad\text{und}\qquad \|u-d\|\ne1. \] Tatsächlich schließt die erste Bedingung für jedes feste von null verschiedene \(d\) höchstens einen Punkt des Einheitskreises aus. Auf diesem Kreis ist die Gleichung \(\|u-d\|=1\) äquivalent zu \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{oder}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] Da \(d\ne0\) ist, ist dies die Gleichung einer Geraden, die den Einheitskreis in höchstens zwei Punkten schneidet. Somit schließt jedes \(d\) höchstens drei Möglichkeiten für \(u\) aus. Da \(D\) endlich ist und der Einheitskreis unendlich viele Punkte hat, existiert das gesuchte \(u\).
Nun setzen wir \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] Die beiden Kopien sind disjunkt: Aus einer Gleichheit \(p=q+u\) würde \(u=p-q\) folgen, was für \(p=q\) wegen \(\|u\|=1\) unmöglich ist und für \(p\ne q\) durch unsere Wahl von \(u\) ausgeschlossen wird.
Verschiebungen erhalten Abstände, also hat jeder Punkt innerhalb seiner eigenen Kopie genau \(m\) Nachbarn im Abstand eins. Zwischen den beiden Kopien haben \(p\) und \(p+u\) den Abstand eins. Sind außerdem \(p,q\in S\) verschieden, so gilt \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] Daher sind die einzigen Punktpaare im Abstand eins zwischen den Kopien die einander entsprechenden Paare \(p,p+u\). Jeder Punkt von \(T\) hat somit genau \(m+1\) Nachbarn im Abstand eins.
Die endliche Menge \(T\) schließt den Induktionsschritt ab und beweist damit die Behauptung für jede natürliche Zahl \(m\).
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1971 · Soru 5
Her \(m\) doğal sayısı için, düzlemde şu özelliğe sahip sonlu bir \(S\) noktalar kümesinin var olduğunu kanıtlayınız: \(S\)'deki her \(A\) noktası için, \(S\)'de \(A\)'ya uzaklığı bir birim olan tam olarak \(m\) nokta vardır.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Önermeyi \(m=0\) durumunu da kapsayacak biçimde tümevarımla kanıtlayacağız. \(m=0\) için tek bir noktadan oluşan bir küme yeterlidir.
Sonlu ve boş olmayan bir \(S\) kümesinde, her noktaya bir birim uzaklıkta tam olarak \(m\) nokta bulunduğunu varsayalım. \(S\)'nin ötelenmiş bir kopyasını ekleyerek \(m+1\) için uygun bir küme oluşturacağız.
Düzlemi \(\mathbb R^2\) ile özdeşleştirelim ve \[ D=\{p-q:p,q\in S,\ p\ne q\} \] olsun. Her \(d\in D\) için \[ u\ne d \qquad\text{ve}\qquad \|u-d\|\ne1 \] koşullarını sağlayan bir \(u\) birim vektörünün var olduğunu iddia ediyoruz. Gerçekten de sıfırdan farklı her sabit \(d\) için ilk koşul, birim çemberin en fazla bir noktasını dışlar. Bu çember üzerinde \(\|u-d\|=1\) eşitliği, \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{veya}\qquad u\cdot d=\frac{\|d\|^2}{2} \] ile eşdeğerdir. \(d\ne0\) olduğundan bu, birim çemberle en fazla iki noktada kesişen bir doğrunun denklemidir. Dolayısıyla her \(d\), \(u\) için en fazla üç seçeneği dışlar. \(D\) sonlu olduğundan ve birim çember sonsuz sayıda nokta içerdiğinden, istenen \(u\) vardır.
Şimdi \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\} \] olarak tanımlayalım. İki kopya ayrıktır: \(p=q+u\) eşitliği \(u=p-q\) sonucunu doğururdu; bu ise \(p=q\) olduğunda \(\|u\|=1\) nedeniyle olanaksızdır, \(p\ne q\) olduğunda da \(u\)'nun seçimi gereği mümkün değildir.
Öteleme uzaklıkları koruduğundan her noktanın kendi kopyası içinde bir birim uzaklıkta tam olarak \(m\) komşusu vardır. İki kopya arasında \(p\) ile \(p+u\) bir birim uzaklıktadır. Ayrıca, \(p,q\in S\) farklı noktalar ise \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] Dolayısıyla kopyalar arasında bir birim uzaklıktaki tek nokta çiftleri, birbirine karşılık gelen \(p,p+u\) çiftleridir. Böylece \(T\)'nin her noktasının bir birim uzaklıkta tam olarak \(m+1\) komşusu vardır.
Sonlu \(T\) kümesi tümevarımı tamamlar ve önermeyi her \(m\) doğal sayısı için kanıtlar.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1971 · Problema 5
Demuestre que, para todo número natural \(m\), existe un conjunto finito \(S\) de puntos de un plano con la siguiente propiedad: para todo punto \(A\) de \(S\), hay exactamente \(m\) puntos de \(S\) que están a distancia unidad de \(A\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Demostramos la afirmación por inducción, incluyendo \(m=0\). Para \(m=0\), basta un conjunto formado por un solo punto.
Supongamos que un conjunto finito no vacío \(S\) tiene exactamente \(m\) puntos a distancia unidad de cada uno de sus puntos. Construiremos un conjunto adecuado para \(m+1\) añadiendo una copia trasladada de \(S\).
Identifiquemos el plano con \(\mathbb R^2\), y sea \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] Afirmamos que existe un vector unitario \(u\) tal que, para todo \(d\in D\), \[ u\ne d \qquad\text{y}\qquad \|u-d\|\ne1. \] En efecto, para cada \(d\) no nulo fijo, la primera condición excluye a lo sumo un punto de la circunferencia unidad. En esa circunferencia, la igualdad \(\|u-d\|=1\) equivale a \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{o bien}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] Como \(d\ne0\), esta es la ecuación de una recta, que corta a la circunferencia unidad en a lo sumo dos puntos. Por tanto, cada \(d\) excluye a lo sumo tres elecciones de \(u\). Como \(D\) es finito y la circunferencia unidad tiene infinitos puntos, existe el \(u\) requerido.
Definamos ahora \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] Las dos copias son disjuntas: una igualdad \(p=q+u\) implicaría \(u=p-q\), lo cual es imposible cuando \(p=q\) porque \(\|u\|=1\), y queda excluido por nuestra elección de \(u\) cuando \(p\ne q\).
La traslación conserva las distancias, por lo que cada punto tiene exactamente \(m\) vecinos a distancia unidad dentro de su propia copia. Entre las dos copias, \(p\) y \(p+u\) están a distancia unidad. Además, si \(p,q\in S\) son distintos, entonces \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] Por ello, los únicos pares a distancia unidad entre las copias son los pares correspondientes \(p,p+u\). Por tanto, cada punto de \(T\) tiene exactamente \(m+1\) vecinos a distancia unidad.
El conjunto finito \(T\) completa la inducción y demuestra la afirmación para todo número natural \(m\).
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1971 · 问题 5
证明：对于每个自然数 \(m\)，平面内都存在一个有限点集 \(S\)，具有如下性质：对于 \(S\) 中的每一点 \(A\)，\(S\) 中恰有 \(m\) 个点与 \(A\) 的距离为单位长度。
题目译自官方英文原文。 官方试卷 (PDF)
解答
我们用数学归纳法证明此命题，并将 \(m=0\) 的情形也包括在内。当 \(m=0\) 时，取只含一个点的集合即可。
假设有限非空点集 \(S\) 满足：对于其中的每一点，\(S\) 中恰有 \(m\) 个点与它的距离为单位长度。我们将添入 \(S\) 的一个平移副本，构造一个适用于 \(m+1\) 的点集。
将平面视为 \(\mathbb R^2\)，并令 \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] 我们断言，存在一个单位向量 \(u\)，使得对每个 \(d\in D\)，都有 \[ u\ne d \qquad\text{且}\qquad \|u-d\|\ne1. \] 事实上，对于每个固定的非零向量 \(d\)，第一个条件至多排除单位圆上的一个点。在单位圆上，等式 \(\|u-d\|=1\) 等价于 \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{即}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] 由于 \(d\ne0\)，这是一条直线的方程，而直线与单位圆至多有两个交点。因此，每个 \(d\) 至多排除 \(u\) 的三种选择。由于 \(D\) 是有限集，而单位圆上有无穷多个点，故所需的 \(u\) 存在。
现令 \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] 这两个副本互不相交：若有等式 \(p=q+u\)，则 \(u=p-q\)；当 \(p=q\) 时，这与 \(\|u\|=1\) 矛盾，而当 \(p\ne q\) 时，这又被我们对 \(u\) 的选择所排除。
平移保持距离不变，因此每个点在其所属的副本内都恰有 \(m\) 个与它相距单位长度的点。在两个副本之间，\(p\) 与 \(p+u\) 的距离为单位长度。此外，若 \(p,q\in S\) 互不相同，则 \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] 所以，两个副本之间距离为单位长度的点对只有对应的点对 \(p,p+u\)。因此，\(T\) 中的每一点都恰有 \(m+1\) 个与它相距单位长度的点。
有限点集 \(T\) 完成了归纳步骤，从而证明了命题对每个自然数 \(m\) 都成立。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1971 · Задача 5
Докажите, что для каждого натурального числа \(m\) существует конечное множество \(S\) точек плоскости со следующим свойством: для каждой точки \(A\) из \(S\) в \(S\) имеется ровно \(m\) точек, находящихся на единичном расстоянии от \(A\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Докажем утверждение индукцией, включив также \(m=0\). При \(m=0\) достаточно множества, состоящего из одной точки.
Предположим, что в конечном непустом множестве \(S\) для каждой его точки имеется ровно \(m\) точек на единичном расстоянии от неё. Построим подходящее множество для \(m+1\), добавив к \(S\) его образ при параллельном переносе.
Отождествим плоскость с \(\mathbb R^2\) и положим \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] Утверждаем, что существует единичный вектор \(u\), для которого при каждом \(d\in D\) \[ u\ne d \qquad\text{и}\qquad \|u-d\|\ne1. \] Действительно, для каждого фиксированного ненулевого \(d\) первое условие исключает не более одной точки единичной окружности. На этой окружности равенство \(\|u-d\|=1\) равносильно \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{или}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] Поскольку \(d\ne0\), это уравнение прямой, которая пересекает единичную окружность не более чем в двух точках. Таким образом, каждое \(d\) исключает не более трёх вариантов выбора \(u\). Поскольку \(D\) конечно, а единичная окружность содержит бесконечно много точек, требуемый \(u\) существует.
Теперь положим \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] Эти две копии не пересекаются: из равенства \(p=q+u\) следовало бы \(u=p-q\), что невозможно при \(p=q\), поскольку \(\|u\|=1\), и исключено выбором \(u\) при \(p\ne q\).
Параллельный перенос сохраняет расстояния, поэтому каждая точка имеет ровно \(m\) соседей на единичном расстоянии в своей копии. Среди точек разных копий \(p\) и \(p+u\) находятся на единичном расстоянии. Кроме того, если \(p,q\in S\) различны, то \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] Следовательно, единственные пары точек из разных копий, находящихся на единичном расстоянии друг от друга, — это соответствующие пары \(p,p+u\). Поэтому каждая точка \(T\) имеет ровно \(m+1\) соседей на единичном расстоянии.
Конечное множество \(T\) завершает шаг индукции, что доказывает утверждение для каждого натурального числа \(m\).
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1971 · المسألة 5
أثبت أنه لكل عدد طبيعي \(m\)، توجد مجموعة منتهية \(S\) من النقاط في مستوى لها الخاصية الآتية: لكل نقطة \(A\) في \(S\)، توجد بالضبط \(m\) نقاط في \(S\) تبعد مسافة الوحدة عن \(A\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نثبت العبارة بالاستقراء، بما في ذلك \(m=0\). عندما \(m=0\)، تكفي مجموعة مؤلفة من نقطة واحدة.
لنفترض أن \(S\) مجموعة منتهية غير خالية، وفيها بالضبط \(m\) نقاط تبعد مسافة الوحدة عن كل نقطة من نقاطها. سننشئ مجموعة مناسبة لـ \(m+1\) بإضافة نسخة من \(S\) ناتجة عن انسحاب.
نطابق المستوى مع \(\mathbb R^2\)، ولتكن \[ D=\{p-q:p,q\in S,\ p\ne q\}. \] ندعي وجود متجه وحدة \(u\) بحيث يتحقق، لكل \(d\in D\)، \[ u\ne d \qquad\text{و}\qquad \|u-d\|\ne1. \] فبالفعل، لكل \(d\) ثابت غير صفري، يستبعد الشرط الأول نقطة واحدة على الأكثر من دائرة الوحدة. وعلى هذه الدائرة، تكافئ المساواة \(\|u-d\|=1\) ما يأتي \[ 1-2u\cdot d+\|d\|^2=1, \qquad\text{أو}\qquad u\cdot d=\frac{\|d\|^2}{2}. \] بما أن \(d\ne0\)، فهذه معادلة مستقيم يقطع دائرة الوحدة في نقطتين على الأكثر. لذا فإن كل \(d\) يستبعد ثلاثة اختيارات لـ \(u\) على الأكثر. وبما أن \(D\) منتهية ودائرة الوحدة تحتوي على عدد غير منتهٍ من النقاط، فإن \(u\) المطلوب موجود.
نضع الآن \[ T=S\cup(S+u), \qquad S+u=\{p+u:p\in S\}. \] النسختان متباينتان: فالمساواة \(p=q+u\) تستلزم \(u=p-q\)، وهذا مستحيل عندما \(p=q\) لأن \(\|u\|=1\)، ويستبعده اختيارنا لـ \(u\) عندما \(p\ne q\).
يحفظ الانسحاب المسافات، لذا فإن لكل نقطة بالضبط \(m\) جيران يبعدون عنها مسافة الوحدة ضمن نسختها. وبين النسختين، تبعد \(p\) و\(p+u\) إحداهما عن الأخرى مسافة الوحدة. وعلاوة على ذلك، إذا كانت \(p,q\in S\) نقطتين مختلفتين، فإن \[ \|p-(q+u)\|=\|u-(p-q)\|\ne1. \] إذن الأزواج الوحيدة بين النسختين التي تفصل بين نقطتيها مسافة الوحدة هي الأزواج المتناظرة \(p,p+u\). ومن ثم فإن لكل نقطة من \(T\) بالضبط \(m+1\) جيران يبعدون عنها مسافة الوحدة.
تكمل المجموعة المنتهية \(T\) خطوة الاستقراء، وبذلك تثبت العبارة لكل عدد طبيعي \(m\).
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).