IMO 1994 · Problem 6
Show that there exists a set \(A\) of positive integers with the following property: For any infinite set \(S\) of primes there exist two positive integers \(m \in A\) and \(n \notin A\) each of which is a product of \(k\) distinct elements of \(S\) for some \(k \geq 2\).
Official text of the problem. Official problem paper (PDF)
Solution
Define \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ are primes},\quad p_1\leq r \right\}. \] By unique prime factorization, a product of \(r\geq2\) distinct primes belongs to \(A\) exactly when its smallest prime factor is at most \(r\).
Now let \(S\) be any infinite set of primes, and let \(p\) be its smallest element. Since \(S\) is infinite, we can choose \(p\) further elements \[ p<q_1<q_2<\cdots<q_p \] of \(S\). Set \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] Both \(m\) and \(n\) are products of exactly \(k\) distinct elements of \(S\), and \(k=p\geq2\).
The smallest prime factor of \(m\) is \(p=k\), so \(m\in A\). The smallest prime factor of \(n\) is \(q_1>p=k\), so \(n\notin A\).
Thus \(A\) has the required property. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1994 · Aufgabe 6
Man zeige, dass es eine Menge \(A\) positiver ganzer Zahlen mit folgender Eigenschaft gibt: Zu jeder unendlichen Menge \(S\) von Primzahlen gibt es zwei positive ganze Zahlen \(m \in A\) und \(n \notin A\), die für ein \(k \geq 2\) jeweils ein Produkt von \(k\) verschiedenen Elementen von \(S\) sind.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir definieren \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ sind Primzahlen},\quad p_1\leq r \right\}. \] Aufgrund der Eindeutigkeit der Primfaktorzerlegung gehört ein Produkt von \(r\geq2\) verschiedenen Primzahlen genau dann zu \(A\), wenn sein kleinster Primfaktor höchstens \(r\) ist.
Sei nun \(S\) eine beliebige unendliche Menge von Primzahlen und \(p\) ihr kleinstes Element. Da \(S\) unendlich ist, können wir \(p\) weitere Elemente \[ p<q_1<q_2<\cdots<q_p \] von \(S\) wählen. Wir setzen \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] Sowohl \(m\) als auch \(n\) sind Produkte von genau \(k\) verschiedenen Elementen von \(S\), und es gilt \(k=p\geq2\).
Der kleinste Primfaktor von \(m\) ist \(p=k\), also gilt \(m\in A\). Der kleinste Primfaktor von \(n\) ist \(q_1>p=k\), also gilt \(n\notin A\).
Somit hat \(A\) die geforderte Eigenschaft. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1994 · Soru 6
Şu özelliğe sahip bir pozitif tam sayılar kümesi \(A\)'nın var olduğunu gösteriniz: Asal sayılardan oluşan her sonsuz \(S\) kümesi için, bir \(k \geq 2\) için her biri \(S\)'nin birbirinden farklı \(k\) elemanının çarpımı olan \(m \in A\) ve \(n \notin A\) pozitif tam sayıları vardır.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ asal sayılardır},\quad p_1\leq r \right\} \] olarak tanımlayalım. Asal çarpanlara ayrılışın tekliğinden, birbirinden farklı \(r\geq2\) asal sayının çarpımının \(A\)'ya ait olması için gerek ve yeter koşul, en küçük asal çarpanının en fazla \(r\) olmasıdır.
Şimdi \(S\), asal sayılardan oluşan herhangi bir sonsuz küme olsun ve \(p\), bu kümenin en küçük elemanı olsun. \(S\) sonsuz olduğundan, \(S\)'nin \(p\) tane daha elemanını \[ p<q_1<q_2<\cdots<q_p \] olacak biçimde seçebiliriz. \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p \] olarak tanımlayalım. Hem \(m\) hem de \(n\), \(S\)'nin tam olarak \(k\) farklı elemanının çarpımıdır ve \(k=p\geq2\)'dir.
\(m\)'nin en küçük asal çarpanı \(p=k\) olduğundan \(m\in A\)'dır. \(n\)'nin en küçük asal çarpanı \(q_1>p=k\) olduğundan \(n\notin A\)'dır.
Böylece \(A\) istenen özelliğe sahiptir. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1994 · Problema 6
Demostrar que existe un conjunto \(A\) de enteros positivos con la siguiente propiedad: para cualquier conjunto infinito \(S\) de números primos, existen dos enteros positivos \(m \in A\) y \(n \notin A\), cada uno de los cuales es un producto de \(k\) elementos distintos de \(S\) para algún \(k \geq 2\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Definamos \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ son primos},\quad p_1\leq r \right\}. \] Por la unicidad de la descomposición en factores primos, un producto de \(r\geq2\) primos distintos pertenece a \(A\) exactamente cuando su menor factor primo es a lo sumo \(r\).
Sea ahora \(S\) un conjunto infinito cualquiera de números primos, y sea \(p\) su menor elemento. Como \(S\) es infinito, podemos elegir otros \(p\) elementos \[ p<q_1<q_2<\cdots<q_p \] de \(S\). Sean \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] Tanto \(m\) como \(n\) son productos de exactamente \(k\) elementos distintos de \(S\), y \(k=p\geq2\).
El menor factor primo de \(m\) es \(p=k\), por lo que \(m\in A\). El menor factor primo de \(n\) es \(q_1>p=k\), por lo que \(n\notin A\).
Así, \(A\) tiene la propiedad requerida. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1994 · 问题 6
证明存在一个正整数集合 \(A\)，具有如下性质：对于任意无限素数集合 \(S\)，存在两个正整数 \(m \in A\) 和 \(n \notin A\)，使得对于某个 \(k \geq 2\)，它们各自都是 \(S\) 中 \(k\) 个互不相同的元素的乘积。
题目译自官方英文原文。 官方试卷 (PDF)
解答
定义 \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ 均为素数},\quad p_1\leq r \right\}. \] 由素因数分解的唯一性，\(r\geq2\) 个互不相同的素数的乘积属于 \(A\)，当且仅当它的最小素因数不大于 \(r\)。
现在设 \(S\) 为任意无限素数集合，\(p\) 为其最小元素。由于 \(S\) 是无限集，我们可以从 \(S\) 中另外选取 \(p\) 个元素： \[ p<q_1<q_2<\cdots<q_p \] 令 \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] \(m\) 和 \(n\) 都恰为 \(S\) 中 \(k\) 个互不相同的元素的乘积，且 \(k=p\geq2\)。
\(m\) 的最小素因数为 \(p=k\)，所以 \(m\in A\)。\(n\) 的最小素因数为 \(q_1>p=k\)，所以 \(n\notin A\)。
因此，\(A\) 具有所要求的性质。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1994 · Задача 6
Докажите, что существует множество \(A\) положительных целых чисел со следующим свойством: для любого бесконечного множества \(S\) простых чисел найдутся два положительных целых числа \(m \in A\) и \(n \notin A\), каждое из которых является произведением \(k\) различных элементов \(S\) для некоторого \(k \geq 2\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Определим \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ — простые числа},\quad p_1\leq r \right\}. \] В силу единственности разложения на простые множители произведение \(r\geq2\) различных простых чисел принадлежит \(A\) тогда и только тогда, когда его наименьший простой делитель не превосходит \(r\).
Пусть теперь \(S\) — произвольное бесконечное множество простых чисел, и пусть \(p\) — его наименьший элемент. Поскольку \(S\) бесконечно, можно выбрать ещё \(p\) элементов \[ p<q_1<q_2<\cdots<q_p \] множества \(S\). Положим \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] Оба числа \(m\) и \(n\) являются произведениями ровно \(k\) различных элементов \(S\), причём \(k=p\geq2\).
Наименьший простой делитель числа \(m\) равен \(p=k\), поэтому \(m\in A\). Наименьший простой делитель числа \(n\) равен \(q_1>p=k\), поэтому \(n\notin A\).
Таким образом, \(A\) обладает требуемым свойством. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1994 · المسألة 6
أثبت وجود مجموعة \(A\) من الأعداد الصحيحة الموجبة تتمتع بالخاصية الآتية: لكل مجموعة غير منتهية \(S\) من الأعداد الأولية، يوجد عددان صحيحان موجبان \(m \in A\) و\(n \notin A\)، كل منهما حاصل ضرب \(k\) عناصر متمايزة من \(S\) لبعض \(k \geq 2\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نعرّف \[ A=\left\{p_1p_2\cdots p_r: r\geq2,\quad p_1<p_2<\cdots<p_r\text{ أعداد أولية},\quad p_1\leq r \right\}. \] بحسب وحدانية التحليل إلى عوامل أولية، فإن حاصل ضرب \(r\geq2\) أعداد أولية متمايزة ينتمي إلى \(A\) إذا وفقط إذا كان أصغر عوامله الأولية لا يتجاوز \(r\).
لتكن الآن \(S\) أي مجموعة غير منتهية من الأعداد الأولية، وليكن \(p\) أصغر عناصرها. بما أن \(S\) غير منتهية، يمكننا اختيار \(p\) عناصر إضافية \[ p<q_1<q_2<\cdots<q_p \] من \(S\). نضع \[ k=p,\qquad m=pq_1q_2\cdots q_{p-1},\qquad n=q_1q_2\cdots q_p. \] كل من \(m\) و\(n\) حاصل ضرب \(k\) عناصر متمايزة من \(S\) بالضبط، و\(k=p\geq2\).
أصغر عامل أولي للعدد \(m\) هو \(p=k\)، لذا \(m\in A\). وأصغر عامل أولي للعدد \(n\) هو \(q_1>p=k\)، لذا \(n\notin A\).
إذن تتمتع \(A\) بالخاصية المطلوبة. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).