IMO 1986 · Problem 3
To each vertex of a regular pentagon an integer is assigned in such a way that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers \(x, y, z\) respectively and \(y < 0\) then the following operation is allowed: the numbers \(x, y, z\) are replaced by \(x+y, -y, z+y\) respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to and end after a finite number of steps.
Official text of the problem. Official problem paper (PDF)
Answer
Yes. The procedure terminates after finitely many steps, regardless of which negative number is chosen at each step.
Solution
Let the numbers, in cyclic order, be \(a,b,c,d,e\), and let \[ S=a+b+c+d+e>0. \] Every allowed operation preserves \(S\), since \[ (x+y)+(-y)+(z+y)=x+y+z. \] The numbers also remain integers.
Consider the nonnegative integer \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] We prove that every allowed operation strictly decreases \(\Phi\).
The definition of \(\Phi\) is unchanged by cyclic relabeling, so we may label the chosen negative number \(b\). The operation replaces \[ (a,b,c,d,e)\quad\text{by}\quad(a+b,-b,c+b,d,e). \] The new value of \(\Phi\) is therefore \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] Subtracting and expanding gives \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] Since \(b\) is a negative integer, \(b\le -1\). Thus every operation decreases \(\Phi\) by at least \(2S>0\).
If \(\Phi_0\) is the initial value, then after \(k\) operations, \[ 0\le \Phi_k\le \Phi_0-2Sk. \] Consequently, there can be at most \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] operations. The procedure must therefore terminate. At termination no negative number can remain, because any negative number would permit another operation. This argument applies to every possible choice of operations.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1986 · Aufgabe 3
Jedem Eckpunkt eines regelmäßigen Fünfecks wird eine ganze Zahl so zugeordnet, dass die Summe aller fünf Zahlen positiv ist. Sind drei aufeinanderfolgenden Eckpunkten die Zahlen \(x, y, z\) in dieser Reihenfolge zugeordnet und gilt \(y < 0\), so ist folgende Operation erlaubt: Die Zahlen \(x, y, z\) werden durch \(x+y, -y, z+y\) in dieser Reihenfolge ersetzt. Eine solche Operation wird wiederholt ausgeführt, solange mindestens eine der fünf Zahlen negativ ist. Entscheide, ob dieses Verfahren notwendigerweise nach endlich vielen Schritten endet.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Ja. Das Verfahren endet nach endlich vielen Schritten, unabhängig davon, welche negative Zahl in jedem Schritt gewählt wird.
Lösung
Die Zahlen seien in zyklischer Reihenfolge \(a,b,c,d,e\), und es sei \[ S=a+b+c+d+e>0. \] Jede erlaubte Operation lässt \(S\) unverändert, denn \[ (x+y)+(-y)+(z+y)=x+y+z. \] Die Zahlen bleiben außerdem ganzzahlig.
Betrachten wir die nichtnegative ganze Zahl \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] Wir beweisen, dass jede erlaubte Operation \(\Phi\) echt verkleinert.
Die Definition von \(\Phi\) bleibt bei zyklischer Umbenennung unverändert, sodass wir die gewählte negative Zahl mit \(b\) bezeichnen dürfen. Die Operation ersetzt \[ (a,b,c,d,e)\quad\text{durch}\quad(a+b,-b,c+b,d,e). \] Der neue Wert von \(\Phi\) ist daher \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] Subtraktion und Ausmultiplizieren ergeben \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] Da \(b\) eine negative ganze Zahl ist, gilt \(b\le -1\). Somit verkleinert jede Operation \(\Phi\) um mindestens \(2S>0\).
Ist \(\Phi_0\) der Anfangswert, so gilt nach \(k\) Operationen \[ 0\le \Phi_k\le \Phi_0-2Sk. \] Folglich können höchstens \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] Operationen ausgeführt werden. Das Verfahren muss daher enden. Am Ende kann keine negative Zahl übrig bleiben, da jede negative Zahl eine weitere Operation ermöglichen würde. Dieses Argument gilt für jede mögliche Wahl der Operationen.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1986 · Soru 3
Bir düzgün beşgenin her köşesine, beş sayının toplamı pozitif olacak şekilde bir tam sayı yazılıyor. Ardışık üç köşeye sırasıyla \(x, y, z\) sayıları yazılmışsa ve \(y < 0\) ise şu işlemin yapılmasına izin veriliyor: \(x, y, z\) sayıları sırasıyla \(x+y, -y, z+y\) ile değiştiriliyor. Beş sayıdan en az biri negatif olduğu sürece bu işlem tekrarlanıyor. Bu sürecin sonlu sayıda adımdan sonra mutlaka sona erip ermeyeceğini belirleyiniz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Evet. Her adımda hangi negatif sayının seçildiğinden bağımsız olarak süreç sonlu sayıda adımdan sonra sona erer.
Çözüm
Sayılar, çevresel sırayla \(a,b,c,d,e\) olsun ve \[ S=a+b+c+d+e>0 \] olarak tanımlansın. İzin verilen her işlem \(S\)'yi korur, çünkü \[ (x+y)+(-y)+(z+y)=x+y+z. \] Sayılar ayrıca tam sayı olarak kalır.
Negatif olmayan \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2 \] tam sayısını ele alalım. İzin verilen her işlemin \(\Phi\)'yi kesin olarak azalttığını kanıtlayacağız.
Harfler çevresel olarak kaydırıldığında \(\Phi\)'nin tanımı değişmediğinden, seçilen negatif sayıyı \(b\) ile gösterebiliriz. İşlem, \[ (a,b,c,d,e)\quad\text{yerine}\quad(a+b,-b,c+b,d,e) \] beşlisini getirir. Dolayısıyla \(\Phi\)'nin yeni değeri \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2 \] olur. Çıkarıp açarsak \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS \end{aligned} \] elde ederiz. \(b\) negatif bir tam sayı olduğundan \(b\le -1\)'dir. Böylece her işlem \(\Phi\)'yi en az \(2S>0\) kadar azaltır.
Başlangıç değeri \(\Phi_0\) ise \(k\) işlemden sonra \[ 0\le \Phi_k\le \Phi_0-2Sk \] olur. Buna göre en fazla \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] işlem yapılabilir. Dolayısıyla süreç sona ermek zorundadır. Süreç sona erdiğinde negatif bir sayı kalamaz; çünkü herhangi bir negatif sayı başka bir işlem yapılmasına olanak verirdi. Bu akıl yürütme, işlemlerin mümkün olan her seçimi için geçerlidir.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1986 · Problema 3
A cada vértice de un pentágono regular se le asigna un entero de tal manera que la suma de los cinco números sea positiva. Si a tres vértices consecutivos se les han asignado los números \(x, y, z\), respectivamente, e \(y < 0\), se permite la siguiente operación: los números \(x, y, z\) se sustituyen por \(x+y, -y, z+y\), respectivamente. Esta operación se realiza repetidamente mientras al menos uno de los cinco números sea negativo. Determinar si este procedimiento termina necesariamente tras un número finito de pasos.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Sí. El procedimiento termina tras un número finito de pasos, independientemente de qué número negativo se elija en cada paso.
Solución
Sean \(a,b,c,d,e\) los números, en orden cíclico, y sea \[ S=a+b+c+d+e>0. \] Toda operación permitida conserva \(S\), pues \[ (x+y)+(-y)+(z+y)=x+y+z. \] Además, los números siguen siendo enteros.
Consideremos el entero no negativo \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] Demostraremos que toda operación permitida disminuye estrictamente \(\Phi\).
La definición de \(\Phi\) no cambia al renombrar cíclicamente los números, por lo que podemos llamar \(b\) al número negativo elegido. La operación sustituye \[ (a,b,c,d,e)\quad\text{por}\quad(a+b,-b,c+b,d,e). \] Por tanto, el nuevo valor de \(\Phi\) es \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] Restando y desarrollando, obtenemos \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] Como \(b\) es un entero negativo, \(b\le -1\). Así, cada operación disminuye \(\Phi\) en al menos \(2S>0\).
Si \(\Phi_0\) es el valor inicial, entonces, tras \(k\) operaciones, \[ 0\le \Phi_k\le \Phi_0-2Sk. \] En consecuencia, puede haber a lo sumo \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] operaciones. Por tanto, el procedimiento debe terminar. Al terminar no puede quedar ningún número negativo, pues cualquier número negativo permitiría realizar otra operación. Este argumento se aplica a cualquier elección posible de operaciones.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1986 · 问题 3
在一个正五边形的每个顶点上各标一个整数，使这五个数的和为正。若三个连续顶点上所标的数依次为 \(x, y, z\)，且 \(y < 0\)，则允许进行如下操作：将 \(x, y, z\) 分别替换为 \(x+y, -y, z+y\)。只要五个数中至少有一个为负，就反复进行这样的操作。判断这一过程是否必定在有限步后终止。
题目译自官方英文原文。 官方试卷 (PDF)
答案
是。无论每一步选择哪个负数，这一过程都会在有限步后终止。
解答
设按循环顺序排列的五个数为 \(a,b,c,d,e\)，并令 \[ S=a+b+c+d+e>0. \] 每次允许的操作都保持 \(S\) 不变，因为 \[ (x+y)+(-y)+(z+y)=x+y+z. \] 这些数也始终为整数。
考虑非负整数 \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] 我们证明，每次允许的操作都会使 \(\Phi\) 严格减小。
循环变换字母标记不改变 \(\Phi\) 的定义，因此不妨将所选的负数记为 \(b\)。该操作将 \[ (a,b,c,d,e)\quad\text{替换为}\quad(a+b,-b,c+b,d,e). \] 因此，\(\Phi\) 的新值为 \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] 相减并展开得 \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] 由于 \(b\) 为负整数，故 \(b\le -1\)。因此，每次操作都使 \(\Phi\) 至少减小 \(2S>0\)。
若 \(\Phi_0\) 为初始值，则在 \(k\) 次操作后， \[ 0\le \Phi_k\le \Phi_0-2Sk. \] 所以，操作次数至多为 \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] 次。因此，这一过程必定终止。终止时不可能仍有负数，因为任何负数都会允许再进行一次操作。这一论证适用于所有可能的操作选择。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1986 · Задача 3
В каждой вершине правильного пятиугольника записано целое число так, что сумма всех пяти чисел положительна. Если в трёх последовательных вершинах записаны числа \(x, y, z\) соответственно и \(y < 0\), то разрешается следующая операция: числа \(x, y, z\) заменяются на \(x+y, -y, z+y\) соответственно. Такую операцию повторяют, пока хотя бы одно из пяти чисел отрицательно. Определите, обязательно ли этот процесс заканчивается через конечное число шагов.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Да. Процесс заканчивается через конечное число шагов независимо от того, какое отрицательное число выбирается на каждом шаге.
Решение
Пусть числа в порядке обхода пятиугольника равны \(a,b,c,d,e\), и пусть \[ S=a+b+c+d+e>0. \] Каждая разрешённая операция сохраняет \(S\), поскольку \[ (x+y)+(-y)+(z+y)=x+y+z. \] Числа также остаются целыми.
Рассмотрим неотрицательное целое число \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] Докажем, что каждая разрешённая операция строго уменьшает \(\Phi\).
Определение \(\Phi\) не меняется при циклической перестановке обозначений, поэтому выбранное отрицательное число можно обозначить через \(b\). Операция заменяет \[ (a,b,c,d,e)\quad\text{на}\quad(a+b,-b,c+b,d,e). \] Следовательно, новое значение \(\Phi\) равно \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] Вычитая и раскрывая скобки, получаем \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] Поскольку \(b\) — отрицательное целое число, \(b\le -1\). Значит, каждая операция уменьшает \(\Phi\) хотя бы на \(2S>0\).
Если \(\Phi_0\) — начальное значение, то после \(k\) операций \[ 0\le \Phi_k\le \Phi_0-2Sk. \] Следовательно, можно выполнить не более \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] операций. Поэтому процесс обязательно заканчивается. После его завершения отрицательных чисел остаться не может, поскольку любое отрицательное число позволило бы выполнить ещё одну операцию. Это рассуждение применимо при любом выборе операций.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1986 · المسألة 3
نُسب إلى كل رأس من رؤوس خماسي منتظم عدد صحيح بحيث يكون مجموع الأعداد الخمسة موجبًا. إذا كانت الأعداد المنسوبة إلى ثلاثة رؤوس متتالية هي \(x, y, z\) على الترتيب، وكان \(y < 0\)، فيُسمح بالعملية الآتية: تُستبدل الأعداد \(x, y, z\) بالأعداد \(x+y, -y, z+y\) على الترتيب. تُكرَّر هذه العملية ما دام واحد على الأقل من الأعداد الخمسة سالبًا. حدّد ما إذا كان هذا الإجراء ينتهي بالضرورة بعد عدد منتهٍ من الخطوات.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
نعم. ينتهي الإجراء بعد عدد منتهٍ من الخطوات، بصرف النظر عن العدد السالب الذي يُختار في كل خطوة.
الحل
لتكن الأعداد، بترتيبها الدوري، هي \(a,b,c,d,e\)، وليكن \[ S=a+b+c+d+e>0. \] تحافظ كل عملية مسموح بها على \(S\)، لأن \[ (x+y)+(-y)+(z+y)=x+y+z. \] كما تبقى الأعداد صحيحة.
ننظر في العدد الصحيح غير السالب \[ \Phi=(a-c)^2+(b-d)^2+(c-e)^2+(d-a)^2+(e-b)^2. \] سنثبت أن كل عملية مسموح بها تُنقص \(\Phi\) إنقاصًا صارمًا.
لا يتغير تعريف \(\Phi\) بإعادة التسمية دوريًا، لذا يمكننا تسمية العدد السالب المختار \(b\). تستبدل العملية \[ (a,b,c,d,e)\quad\text{بـ}\quad(a+b,-b,c+b,d,e). \] وعليه، فإن القيمة الجديدة لـ\(\Phi\) هي \[ \Phi'=(a-c)^2+(b+d)^2+(c+b-e)^2 +(d-a-b)^2+(e+b)^2. \] بالطرح والنشر نحصل على \[ \begin{aligned} \Phi'-\Phi &=4bd+\bigl(2b(c-e)+b^2\bigr) +\bigl(-2b(d-a)+b^2\bigr)+4be\\ &=2b(a+b+c+d+e)\\ &=2bS. \end{aligned} \] بما أن \(b\) عدد صحيح سالب، فإن \(b\le -1\). إذن تُنقص كل عملية \(\Phi\) بمقدار لا يقل عن \(2S>0\).
إذا كانت \(\Phi_0\) هي القيمة الابتدائية، فإنه بعد \(k\) عمليات، \[ 0\le \Phi_k\le \Phi_0-2Sk. \] وعليه، فإن عدد العمليات لا يمكن أن يتجاوز \[ \left\lfloor\frac{\Phi_0}{2S}\right\rfloor \] عملية. لذلك لا بد أن ينتهي الإجراء. وعند انتهائه لا يمكن أن يبقى أي عدد سالب، لأن وجود عدد سالب يتيح إجراء عملية أخرى. تنطبق هذه الحجة على كل اختيار ممكن للعمليات.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).