IMO 1985 · Problem 4
Given a set \(M\) of 1985 distinct positive integers, none of which has a prime divisor greater than 26. Prove that \(M\) contains at least one subset of four distinct elements whose product is the fourth power of an integer.
Official text of the problem. Official problem paper (PDF)
Solution
The primes less than or equal to \(26\) are \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] Every positive integer \(n\) having no other prime divisors has a unique representation \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] Associate to \(n\) its parity vector \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] There are \(2^9=512\) possible parity vectors. Moreover, two such integers \(a,b\) have the same parity vector if and only if \(ab\) is a perfect square, since this is equivalent to every exponent in \(ab\) being even.
Repeatedly remove from \(M\) a pair of elements having the same parity vector, until no such pair remains. The remaining elements have distinct parity vectors, so there are at most \(512\) of them. Consequently, the number \(r\) of removed pairs satisfies \[ 1985-2r\le 512, \] and hence \(r\ge 737>512\).
Write these disjoint pairs as \((a_i,b_i)\), where \(1\le i\le r\). Each product is a square, so \[ a_i b_i=c_i^2 \] for a positive integer \(c_i\). Every prime divisor of \(c_i\) also divides \(a_i b_i\), so it belongs to the same list of nine primes.
Since there are more than \(512\) integers \(c_i\), two of them, say \(c_i\) and \(c_j\) with \(i\ne j\), have the same parity vector. Thus \(c_i c_j=d^2\) for some positive integer \(d\). Therefore \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] The four elements \(a_i,b_i,a_j,b_j\) are distinct because the removed pairs were disjoint. They form the required subset. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1985 · Aufgabe 4
Gegeben sei eine Menge \(M\) aus 1985 verschiedenen positiven ganzen Zahlen, von denen keine einen Primteiler größer als 26 hat. Beweise, dass \(M\) mindestens eine Teilmenge aus vier verschiedenen Elementen enthält, deren Produkt die vierte Potenz einer ganzen Zahl ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Die Primzahlen kleiner oder gleich \(26\) sind \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] Jede positive ganze Zahl \(n\), die keine anderen Primteiler hat, besitzt eine eindeutige Darstellung \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] Wir ordnen \(n\) seinen Paritätsvektor zu: \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] Es gibt \(2^9=512\) mögliche Paritätsvektoren. Außerdem haben zwei solche ganzen Zahlen \(a,b\) genau dann denselben Paritätsvektor, wenn \(ab\) eine Quadratzahl ist, denn dies ist dazu äquivalent, dass jeder Exponent in \(ab\) gerade ist.
Wir entfernen wiederholt ein Paar von Elementen mit demselben Paritätsvektor aus \(M\), bis kein solches Paar mehr vorhanden ist. Die verbleibenden Elemente haben verschiedene Paritätsvektoren, also gibt es höchstens \(512\) von ihnen. Folglich erfüllt die Anzahl \(r\) der entfernten Paare die Ungleichung \[ 1985-2r\le 512, \] und somit gilt \(r\ge 737>512\).
Wir bezeichnen diese disjunkten Paare mit \((a_i,b_i)\), wobei \(1\le i\le r\). Jedes Produkt ist eine Quadratzahl, also gilt \[ a_i b_i=c_i^2 \] für eine positive ganze Zahl \(c_i\). Jeder Primteiler von \(c_i\) teilt auch \(a_i b_i\) und gehört daher zu derselben Liste von neun Primzahlen.
Da es mehr als \(512\) ganze Zahlen \(c_i\) gibt, haben zwei von ihnen, etwa \(c_i\) und \(c_j\) mit \(i\ne j\), denselben Paritätsvektor. Somit gilt \(c_i c_j=d^2\) für eine positive ganze Zahl \(d\). Daher ist \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] Die vier Elemente \(a_i,b_i,a_j,b_j\) sind verschieden, da die entfernten Paare disjunkt waren. Sie bilden die gesuchte Teilmenge. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1985 · Soru 4
Hiçbirinin 26'dan büyük asal böleni olmayan, birbirinden farklı 1985 pozitif tam sayıdan oluşan bir \(M\) kümesi verilsin. \(M\)'nin, elemanlarının çarpımı bir tam sayının dördüncü kuvveti olan, birbirinden farklı dört elemanlı en az bir alt kümesi bulunduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\(26\)'dan küçük veya ona eşit asal sayılar \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23 \] şeklindedir. Başka asal böleni olmayan her pozitif \(n\) tam sayısının \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0 \] biçiminde tek bir gösterimi vardır. \(n\) sayısına karşılık gelen parite vektörünü \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2) \] olarak tanımlayalım. Olası parite vektörlerinin sayısı \(2^9=512\)'dir. Ayrıca, böyle iki \(a,b\) tam sayısının parite vektörlerinin aynı olması için gerek ve yeter koşul \(ab\)'nin bir tam kare olmasıdır; çünkü bu, \(ab\)'deki her üssün çift olmasına denktir.
\(M\)'den, aynı parite vektörüne sahip bir eleman çiftini, böyle bir çift kalmayıncaya kadar tekrar tekrar çıkaralım. Geriye kalan elemanların parite vektörleri birbirinden farklı olduğundan, bu elemanların sayısı en fazla \(512\)'dir. Dolayısıyla çıkarılan çiftlerin sayısı \(r\), \[ 1985-2r\le 512, \] eşitsizliğini sağlar ve buradan \(r\ge 737>512\) elde edilir.
Bu ayrık çiftleri, \(1\le i\le r\) olmak üzere \((a_i,b_i)\) ile gösterelim. Her çarpım bir tam kare olduğundan, bir pozitif \(c_i\) tam sayısı için \[ a_i b_i=c_i^2 \] olur. \(c_i\)'nin her asal böleni \(a_i b_i\)'yi de böldüğünden, aynı dokuz asal sayıdan oluşan listede yer alır.
\(c_i\) tam sayılarının sayısı \(512\)'den fazla olduğundan, bunlardan ikisinin, örneğin \(i\ne j\) olmak üzere \(c_i\) ve \(c_j\)'nin parite vektörleri aynıdır. Dolayısıyla bir pozitif \(d\) tam sayısı için \(c_i c_j=d^2\) olur. Böylece \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] Çıkarılan çiftler ayrık olduğundan, \(a_i,b_i,a_j,b_j\) elemanlarının dördü de birbirinden farklıdır. Bu elemanlar istenen alt kümeyi oluşturur. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1985 · Problema 4
Sea \(M\) un conjunto de 1985 enteros positivos distintos, ninguno de los cuales tiene un divisor primo mayor que 26. Demostrar que \(M\) contiene al menos un subconjunto de cuatro elementos distintos cuyo producto es la cuarta potencia de un entero.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Los números primos menores o iguales que \(26\) son \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] Todo entero positivo \(n\) que no tenga otros divisores primos admite una representación única \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] Asociamos a \(n\) su vector de paridades \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] Hay \(2^9=512\) vectores de paridades posibles. Además, dos enteros de este tipo \(a,b\) tienen el mismo vector de paridades si y solo si \(ab\) es un cuadrado perfecto, pues esto equivale a que todos los exponentes de \(ab\) sean pares.
Retiramos repetidamente de \(M\) un par de elementos que tengan el mismo vector de paridades, hasta que no quede ningún par de este tipo. Los elementos restantes tienen vectores de paridades distintos, de modo que quedan a lo sumo \(512\) elementos. En consecuencia, el número \(r\) de pares retirados satisface \[ 1985-2r\le 512, \] y, por tanto, \(r\ge 737>512\).
Escribimos estos pares disjuntos como \((a_i,b_i)\), donde \(1\le i\le r\). Cada producto es un cuadrado, por lo que \[ a_i b_i=c_i^2 \] para un entero positivo \(c_i\). Todo divisor primo de \(c_i\) divide también a \(a_i b_i\), por lo que pertenece a la misma lista de nueve primos.
Como hay más de \(512\) enteros \(c_i\), dos de ellos, digamos \(c_i\) y \(c_j\) con \(i\ne j\), tienen el mismo vector de paridades. Así, \(c_i c_j=d^2\) para algún entero positivo \(d\). Por tanto, \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] Los cuatro elementos \(a_i,b_i,a_j,b_j\) son distintos porque los pares retirados eran disjuntos. Estos forman el subconjunto requerido. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1985 · 问题 4
给定一个由 1985 个互不相同的正整数组成的集合 \(M\)，其中每个数都没有大于 26 的素因子。证明：\(M\) 至少包含一个由四个互不相同的元素组成的子集，使得这四个元素的乘积是某个整数的四次方。
题目译自官方英文原文。 官方试卷 (PDF)
解答
不超过 \(26\) 的素数为 \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] 每个不含其他素因子的正整数 \(n\) 都有唯一的表示 \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] 将 \(n\) 与其奇偶向量 \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] 相对应。 奇偶向量共有 \(2^9=512\) 种可能。此外，两个这样的整数 \(a,b\) 具有相同的奇偶向量，当且仅当 \(ab\) 是完全平方数，因为这等价于 \(ab\) 中每个素因子的指数均为偶数。
反复从 \(M\) 中取出一对奇偶向量相同的元素，直到不再存在这样的数对。剩余元素的奇偶向量互不相同，因此至多剩下 \(512\) 个元素。所以，取出的数对个数 \(r\) 满足 \[ 1985-2r\le 512, \] 从而 \(r\ge 737>512\)。
将这些互不相交的数对记为 \((a_i,b_i)\)，其中 \(1\le i\le r\)。每一对的乘积都是完全平方数，因此 \[ a_i b_i=c_i^2 \] 其中 \(c_i\) 为正整数。\(c_i\) 的每个素因子也都整除 \(a_i b_i\)，因此它也属于上述九个素数。
由于整数 \(c_i\) 的个数超过 \(512\)，其中必有两个具有相同的奇偶向量，不妨设为 \(c_i\) 和 \(c_j\)，其中 \(i\ne j\)。于是，存在正整数 \(d\)，使得 \(c_i c_j=d^2\)。因此 \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] 由于取出的数对互不相交，四个元素 \(a_i,b_i,a_j,b_j\) 互不相同。它们构成了所求的子集。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1985 · Задача 4
Дано множество \(M\), состоящее из 1985 различных натуральных чисел, ни одно из которых не имеет простого делителя, большего 26. Докажите, что в \(M\) найдутся четыре различных элемента, произведение которых является четвёртой степенью целого числа.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Простые числа, не превосходящие \(26\), — это \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] Каждое натуральное число \(n\), не имеющее других простых делителей, единственным образом представляется в виде \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] Сопоставим числу \(n\) его вектор чётностей \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] Всего существует \(2^9=512\) возможных векторов чётностей. Кроме того, два таких числа \(a,b\) имеют одинаковые векторы чётностей тогда и только тогда, когда \(ab\) является полным квадратом, поскольку это равносильно чётности всех показателей в разложении \(ab\).
Будем последовательно удалять из \(M\) пары элементов с одинаковыми векторами чётностей, пока таких пар не останется. У оставшихся элементов векторы чётностей попарно различны, поэтому этих элементов не более \(512\). Следовательно, число \(r\) удалённых пар удовлетворяет неравенству \[ 1985-2r\le 512, \] откуда \(r\ge 737>512\).
Обозначим эти непересекающиеся пары через \((a_i,b_i)\), где \(1\le i\le r\). Произведение чисел в каждой паре является квадратом, поэтому \[ a_i b_i=c_i^2 \] для некоторого натурального числа \(c_i\). Каждый простой делитель \(c_i\) делит и \(a_i b_i\), поэтому он входит в тот же список из девяти простых чисел.
Поскольку чисел \(c_i\) больше \(512\), два из них, скажем \(c_i\) и \(c_j\) при \(i\ne j\), имеют одинаковые векторы чётностей. Значит, \(c_i c_j=d^2\) для некоторого натурального числа \(d\). Поэтому \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] Четыре элемента \(a_i,b_i,a_j,b_j\) различны, поскольку удалённые пары не пересекались. Они и образуют искомое подмножество. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1985 · المسألة 4
لتكن \(M\) مجموعة من 1985 عددًا صحيحًا موجبًا مختلفًا، لا يملك أي منها قاسمًا أوليًا أكبر من 26. أثبت أن \(M\) تحتوي على مجموعة جزئية واحدة على الأقل من أربعة عناصر مختلفة حاصل ضربها قوة رابعة لعدد صحيح.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
الأعداد الأولية الأصغر من أو المساوية لـ \(26\) هي \[ p_1,\ldots,p_9=2,3,5,7,11,13,17,19,23. \] لكل عدد صحيح موجب \(n\) لا يملك قواسم أولية أخرى تمثيل وحيد \[ n=\prod_{j=1}^{9}p_j^{e_j}, \qquad e_j\ge 0. \] نربط بالعدد \(n\) متجه الزوجية الخاص به \[ v(n)=(e_1\bmod 2,\ldots,e_9\bmod 2). \] يوجد \(2^9=512\) متجه زوجية ممكنًا. فضلًا عن ذلك، يكون لعددين صحيحين \(a,b\) من هذا النوع متجه الزوجية نفسه إذا وفقط إذا كان \(ab\) مربعًا كاملًا، لأن ذلك يكافئ كون كل أس في \(ab\) زوجيًا.
نزيل من \(M\) تباعًا زوجًا من العناصر لهما متجه الزوجية نفسه، حتى لا يبقى أي زوج من هذا النوع. وللعناصر المتبقية متجهات زوجية مختلفة، لذا لا يتجاوز عددها \(512\). وبالتالي، فإن عدد الأزواج المزالة \(r\) يحقق \[ 1985-2r\le 512, \] ومن ثم \(r\ge 737>512\).
نكتب هذه الأزواج المنفصلة على الصورة \((a_i,b_i)\)، حيث \(1\le i\le r\). وحاصل ضرب كل زوج مربع، لذا \[ a_i b_i=c_i^2 \] لعدد صحيح موجب \(c_i\). وكل قاسم أولي لـ \(c_i\) يقسم أيضًا \(a_i b_i\)، لذا ينتمي إلى القائمة نفسها من الأعداد الأولية التسعة.
بما أن عدد الأعداد الصحيحة \(c_i\) أكبر من \(512\)، فإن اثنين منها، وليكونا \(c_i\) و\(c_j\) حيث \(i\ne j\)، لهما متجه الزوجية نفسه. ومن ثم \(c_i c_j=d^2\) لعدد صحيح موجب ما \(d\). وبالتالي \[ a_i b_i a_j b_j =c_i^2c_j^2 =(c_i c_j)^2 =d^4. \] العناصر الأربعة \(a_i,b_i,a_j,b_j\) مختلفة لأن الأزواج المزالة كانت منفصلة (لا تشترك في أي عنصر). وهي تشكل المجموعة الجزئية المطلوبة. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).