IMO 1991 · Problem 3
Let \(S = \{1, 2, 3, \ldots, 280\}\). Find the smallest integer \(n\) such that each \(n\)-element subset of \(S\) contains five numbers which are pairwise relatively prime.
Official text of the problem. Official problem paper (PDF)
Answer
\[ \boxed{217} \]
Solution
Let \[ F=\{m\in S:\text{at least one of }2,3,5,7\text{ divides }m\}. \] By inclusion–exclusion, \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] Among any five members of \(F\), two must have a common divisor from \(\{2,3,5,7\}\), by the pigeonhole principle. Thus \(F\) contains no five pairwise relatively prime numbers, so \(n\ge217\).
We prove that every subset with no five pairwise relatively prime numbers has at most \(216\) elements.
First, determine the composite numbers in \(S\setminus F\). All their prime factors are at least \(11\). Since \(11^3>280\), each such number is a product \(pq\) of two primes, with \(11\le p\le q\). Also \(p^2\le280<17^2\), so \(p=11\) or \(p=13\). The possibilities are exactly \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] Consequently, \(S\setminus F\) consists of these eight numbers, the number \(1\), and all primes from \(11\) to \(280\).
Now construct six sets \(G_1,\ldots,G_6\) using the following table. Each set consists of all entries in its row.
| Set | Four members of \(F\) | Members of \(S\setminus F\) |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\), and all primes from \(11\) to \(280\) |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
All displayed numbers belong to \(S\), and the six sets are disjoint. Within each row, no prime divides two different entries, so the members of each \(G_i\) are pairwise relatively prime.
Moreover, these sets cover every element of \(S\setminus F\) and exactly \(24\) elements of \(F\). Therefore, writing \[ U=G_1\cup\cdots\cup G_6, \] we have \[ |S\setminus U|=|F|-24=192. \]
Let \(A\subseteq S\) contain no five pairwise relatively prime numbers. Each \(G_i\) can contain at most four elements of \(A\). Hence \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] Thus every \(217\)-element subset contains five pairwise relatively prime numbers. Together with the example \(F\), this proves that the smallest integer is \(\boxed{217}\).
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1991 · Aufgabe 3
Es sei \(S = \{1, 2, 3, \ldots, 280\}\). Man bestimme die kleinste ganze Zahl \(n\), für die jede \(n\)-elementige Teilmenge von \(S\) fünf paarweise teilerfremde Zahlen enthält.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
\[ \boxed{217} \]
Lösung
Es sei \[ F=\{m\in S:\text{mindestens eine der Zahlen }2,3,5,7\text{ teilt }m\}. \] Nach dem Prinzip von Inklusion und Exklusion gilt \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] Unter beliebigen fünf Elementen von \(F\) müssen nach dem Schubfachprinzip zwei einen gemeinsamen Teiler aus \(\{2,3,5,7\}\) haben. Somit enthält \(F\) keine fünf paarweise teilerfremden Zahlen, also ist \(n\ge217\).
Wir beweisen, dass jede Teilmenge, die keine fünf paarweise teilerfremden Zahlen enthält, höchstens \(216\) Elemente hat.
Zunächst bestimmen wir die zusammengesetzten Zahlen in \(S\setminus F\). Alle ihre Primfaktoren sind mindestens \(11\). Da \(11^3>280\), ist jede solche Zahl ein Produkt \(pq\) zweier Primzahlen mit \(11\le p\le q\). Außerdem gilt \(p^2\le280<17^2\), also ist \(p=11\) oder \(p=13\). Die Möglichkeiten sind genau \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] Folglich besteht \(S\setminus F\) aus diesen acht Zahlen, der Zahl \(1\) und allen Primzahlen von \(11\) bis \(280\).
Nun konstruieren wir sechs Mengen \(G_1,\ldots,G_6\) mithilfe der folgenden Tabelle. Jede Menge besteht aus allen Einträgen ihrer Zeile.
| Menge | Vier Elemente von \(F\) | Elemente von \(S\setminus F\) |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\) und alle Primzahlen von \(11\) bis \(280\) |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
Alle aufgeführten Zahlen gehören zu \(S\), und die sechs Mengen sind paarweise disjunkt. Innerhalb jeder Zeile teilt keine Primzahl zwei verschiedene Einträge, also sind die Elemente jeder Menge \(G_i\) paarweise teilerfremd.
Außerdem überdecken diese Mengen jedes Element von \(S\setminus F\) und genau \(24\) Elemente von \(F\). Setzen wir also \[ U=G_1\cup\cdots\cup G_6, \] so gilt \[ |S\setminus U|=|F|-24=192. \]
Es sei \(A\subseteq S\) eine Menge, die keine fünf paarweise teilerfremden Zahlen enthält. Jede Menge \(G_i\) kann höchstens vier Elemente von \(A\) enthalten. Daher gilt \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] Somit enthält jede \(217\)-elementige Teilmenge fünf paarweise teilerfremde Zahlen. Zusammen mit dem Beispiel \(F\) beweist dies, dass die kleinste ganze Zahl \(\boxed{217}\) ist.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1991 · Soru 3
\(S = \{1, 2, 3, \ldots, 280\}\) olsun. \(S\)'nin her \(n\) elemanlı alt kümesinin, herhangi ikisi aralarında asal olan beş sayı içermesini sağlayan en küçük \(n\) tam sayısını bulunuz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
\[ \boxed{217} \]
Çözüm
\[ F=\{m\in S:\text{en az bir }2,3,5,7\text{ sayısının katıdır }m\} \] olsun. İçerme–dışlama ilkesinden, \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] Güvercin yuvası ilkesine göre, \(F\)'nin herhangi beş elemanından ikisinin \(\{2,3,5,7\}\) kümesinden ortak bir böleni bulunmalıdır. Dolayısıyla \(F\), herhangi ikisi aralarında asal olan beş sayı içermez; bu nedenle \(n\ge217\) olur.
Herhangi ikisi aralarında asal olan beş sayı içermeyen her alt kümenin en fazla \(216\) elemanlı olduğunu kanıtlayacağız.
Önce \(S\setminus F\) kümesindeki bileşik sayıları belirleyelim. Bunların tüm asal çarpanları en az \(11\)'dir. \(11^3>280\) olduğundan, böyle her sayı \(11\le p\le q\) olmak üzere iki asal sayının \(pq\) çarpımıdır. Ayrıca \(p^2\le280<17^2\) olduğundan \(p=11\) veya \(p=13\) olur. Olasılıklar tam olarak şunlardır: \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] Dolayısıyla \(S\setminus F\), bu sekiz sayıdan, \(1\) sayısından ve \(11\)'den \(280\)'e kadar tüm asal sayılardan oluşur.
Şimdi aşağıdaki tabloyu kullanarak \(G_1,\ldots,G_6\) kümelerini oluşturalım. Her küme, kendi satırındaki tüm sayılardan oluşur.
| Küme | \(F\)'nin dört elemanı | \(S\setminus F\)'nin elemanları |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\) ve 11'den 280'e kadar tüm asal sayılar |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
Tabloda verilen tüm sayılar \(S\)'ye aittir ve bu altı küme birbirinden ayrıktır. Her satırda, hiçbir asal sayı iki farklı sayıyı bölmez; dolayısıyla her \(G_i\)'nin elemanları ikişer ikişer aralarında asaldır.
Ayrıca bu kümeler, \(S\setminus F\)'nin tüm elemanlarını ve \(F\)'nin tam olarak \(24\) elemanını kapsar. Bu nedenle, \[ U=G_1\cup\cdots\cup G_6 \] yazarsak, \[ |S\setminus U|=|F|-24=192 \] olur.
\(A\subseteq S\), herhangi ikisi aralarında asal olan beş sayı içermesin. Her \(G_i\), \(A\)'nın en fazla dört elemanını içerebilir. Böylece \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] Dolayısıyla her \(217\) elemanlı alt küme, herhangi ikisi aralarında asal olan beş sayı içerir. Bu sonuç, \(F\) örneğiyle birlikte, en küçük tam sayının \(\boxed{217}\) olduğunu kanıtlar.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1991 · Problema 3
Sea \(S = \{1, 2, 3, \ldots, 280\}\). Hallar el menor entero \(n\) tal que todo subconjunto de \(S\) con \(n\) elementos contenga cinco números primos entre sí dos a dos.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
\[ \boxed{217} \]
Solución
Sea \[ F=\{m\in S:\text{al menos uno de }2,3,5,7\text{ divide a }m\}. \] Por el principio de inclusión-exclusión, \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] Entre cualesquiera cinco elementos de \(F\), dos deben tener un divisor común perteneciente a \(\{2,3,5,7\}\), por el principio del palomar. Así, \(F\) no contiene cinco números primos entre sí dos a dos, por lo que \(n\ge217\).
Demostraremos que todo subconjunto que no contenga cinco números primos entre sí dos a dos tiene a lo sumo \(216\) elementos.
Primero, determinemos los números compuestos de \(S\setminus F\). Todos sus factores primos son al menos \(11\). Como \(11^3>280\), cada uno de esos números es un producto \(pq\) de dos primos, con \(11\le p\le q\). Además, \(p^2\le280<17^2\), por lo que \(p=11\) o \(p=13\). Las posibilidades son exactamente \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] Por consiguiente, \(S\setminus F\) consta de estos ocho números, el número \(1\) y todos los primos desde \(11\) hasta \(280\).
Construyamos ahora seis conjuntos \(G_1,\ldots,G_6\) mediante la siguiente tabla. Cada conjunto consta de todas las entradas de su fila.
| Conjunto | Cuatro elementos de \(F\) | Elementos de \(S\setminus F\) |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\), y todos los primos desde \(11\) hasta \(280\) |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
Todos los números de la tabla pertenecen a \(S\), y los seis conjuntos son disjuntos. En cada fila, ningún primo divide dos entradas distintas, de modo que los elementos de cada \(G_i\) son primos entre sí dos a dos.
Además, estos conjuntos cubren todos los elementos de \(S\setminus F\) y exactamente \(24\) elementos de \(F\). Por tanto, si escribimos \[ U=G_1\cup\cdots\cup G_6, \] tenemos \[ |S\setminus U|=|F|-24=192. \]
Sea \(A\subseteq S\) un conjunto que no contenga cinco números primos entre sí dos a dos. Cada \(G_i\) puede contener a lo sumo cuatro elementos de \(A\). Por lo tanto, \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] Así, todo subconjunto con \(217\) elementos contiene cinco números primos entre sí dos a dos. Junto con el ejemplo \(F\), esto demuestra que el menor entero es \(\boxed{217}\).
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1991 · 问题 3
设 \(S = \{1, 2, 3, \ldots, 280\}\)。求最小的整数 \(n\)，使得 \(S\) 的每个含 \(n\) 个元素的子集都包含五个两两互素的数。
题目译自官方英文原文。 官方试卷 (PDF)
答案
\[ \boxed{217} \]
解答
设 \[ F=\{m\in S:\text{在 }2,3,5,7\text{ 中至少有一个数整除 }m\}. \] 由容斥原理， \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] 由抽屉原理，在 \(F\) 的任意五个元素中，必有两个数具有一个属于 \(\{2,3,5,7\}\) 的公因数。因此 \(F\) 不包含五个两两互素的数，故 \(n\ge217\)。
下面证明，任何不包含五个两两互素的数的子集至多有 \(216\) 个元素。
首先确定 \(S\setminus F\) 中的合数。它们的所有素因数都至少为 \(11\)。由于 \(11^3>280\)，每个这样的数都是两个素数的乘积 \(pq\)，其中 \(11\le p\le q\)。又有 \(p^2\le280<17^2\)，故 \(p=11\) 或 \(p=13\)。所有可能的数恰好为 \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] 因此，\(S\setminus F\) 由这八个数、数 \(1\) 以及从 \(11\) 到 \(280\) 的所有素数组成。
现在按照下表构造六个集合 \(G_1,\ldots,G_6\)。每个集合由所在行中的所有数构成。
| 集合 | \(F\) 中的四个元素 | \(S\setminus F\) 中的元素 |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\)，以及从 \(11\) 到 \(280\) 的所有素数 |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
表中所有数都属于 \(S\)，且这六个集合两两不交。在每一行中，没有素数能整除两个不同的数，因此每个 \(G_i\) 中的元素两两互素。
此外，这些集合覆盖了 \(S\setminus F\) 的每个元素，以及 \(F\) 中恰好 \(24\) 个元素。因此，记 \[ U=G_1\cup\cdots\cup G_6, \] 则有 \[ |S\setminus U|=|F|-24=192. \]
设 \(A\subseteq S\) 不包含五个两两互素的数。每个 \(G_i\) 至多包含 \(A\) 的四个元素。从而 \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] 因此，每个含 \(217\) 个元素的子集都包含五个两两互素的数。结合例子 \(F\)，可知所求最小整数为 \(\boxed{217}\)。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1991 · Задача 3
Пусть \(S = \{1, 2, 3, \ldots, 280\}\). Найдите наименьшее целое число \(n\), для которого каждое \(n\)-элементное подмножество \(S\) содержит пять попарно взаимно простых чисел.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
\[ \boxed{217} \]
Решение
Пусть \[ F=\{m\in S:\text{хотя бы одно из чисел }2,3,5,7\text{ делит }m\}. \] По формуле включений и исключений \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] По принципу Дирихле среди любых пяти элементов \(F\) найдутся два, имеющие общий делитель из \(\{2,3,5,7\}\). Таким образом, \(F\) не содержит пяти попарно взаимно простых чисел, поэтому \(n\ge217\).
Докажем, что любое подмножество, не содержащее пяти попарно взаимно простых чисел, имеет не более \(216\) элементов.
Сначала найдём все составные числа в \(S\setminus F\). Все их простые делители не меньше \(11\). Поскольку \(11^3>280\), каждое такое число является произведением \(pq\) двух простых чисел, где \(11\le p\le q\). Кроме того, \(p^2\le280<17^2\), поэтому \(p=11\) или \(p=13\). Получаем в точности следующие возможности: \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] Следовательно, \(S\setminus F\) состоит из этих восьми чисел, числа \(1\) и всех простых чисел от \(11\) до \(280\).
Теперь построим шесть множеств \(G_1,\ldots,G_6\) с помощью следующей таблицы. Каждое множество состоит из всех чисел, указанных в соответствующей строке.
| Множество | Четыре элемента \(F\) | Элементы \(S\setminus F\) |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\) и все простые числа от \(11\) до \(280\) |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
Все указанные числа принадлежат \(S\), и эти шесть множеств попарно не пересекаются. В каждой строке никакое простое число не делит два различных числа, поэтому элементы каждого \(G_i\) попарно взаимно просты.
Кроме того, эти множества покрывают все элементы \(S\setminus F\) и ровно \(24\) элемента \(F\). Поэтому, обозначив \[ U=G_1\cup\cdots\cup G_6, \] получаем \[ |S\setminus U|=|F|-24=192. \]
Пусть \(A\subseteq S\) не содержит пяти попарно взаимно простых чисел. Каждое \(G_i\) может содержать не более четырёх элементов \(A\). Следовательно, \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] Таким образом, каждое \(217\)-элементное подмножество содержит пять попарно взаимно простых чисел. Вместе с примером \(F\) это доказывает, что наименьшее целое число равно \(\boxed{217}\).
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1991 · المسألة 3
لتكن \(S = \{1, 2, 3, \ldots, 280\}\). أوجد أصغر عدد صحيح \(n\) بحيث تحتوي كل مجموعة جزئية من \(S\) ذات \(n\) عنصرًا على خمسة أعداد أولية نسبيًا مثنى مثنى.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
\[ \boxed{217} \]
الحل
لتكن \[ F=\{m\in S:\text{واحد على الأقل من }2,3,5,7\text{ يقسم }m\}. \] بمبدأ الشمول والاستبعاد، \[ \begin{aligned} |F| &=(140+93+56+40)\\ &\quad -(46+28+20+18+13+8)\\ &\quad +(9+6+4+2)-1\\ &=216. \end{aligned} \] من بين أي خمسة عناصر من \(F\)، لا بد أن يكون لاثنين منها قاسم مشترك من \(\{2,3,5,7\}\)، بمبدأ الحمام. إذن لا تحتوي \(F\) على خمسة أعداد أولية نسبيًا مثنى مثنى، ومن ثم \(n\ge217\).
سنثبت أن كل مجموعة جزئية لا تحتوي على خمسة أعداد أولية نسبيًا مثنى مثنى تضم على الأكثر \(216\) عنصرًا.
أولًا، نحدد الأعداد المركبة في \(S\setminus F\). جميع عواملها الأولية لا تقل عن \(11\). وبما أن \(11^3>280\)، فإن كل عدد من هذه الأعداد هو حاصل ضرب \(pq\) لعددين أوليين، حيث \(11\le p\le q\). ولدينا أيضًا \(p^2\le280<17^2\)، ومن ثم \(p=11\) أو \(p=13\). والاحتمالات هي بالضبط \[ 11^2,\quad11\cdot13,\quad11\cdot17,\quad11\cdot19,\quad 11\cdot23,\quad13^2,\quad13\cdot17,\quad13\cdot19. \] وبالتالي، تتكون \(S\setminus F\) من هذه الأعداد الثمانية، والعدد \(1\)، وجميع الأعداد الأولية من \(11\) إلى \(280\).
ننشئ الآن ست مجموعات \(G_1,\ldots,G_6\) باستخدام الجدول الآتي. تتكون كل مجموعة من جميع الأعداد الواردة في صفها.
| المجموعة | أربعة عناصر من \(F\) | عناصر من \(S\setminus F\) |
|---|---|---|
| \(G_1\) | \(2,\ 3,\ 5,\ 7\) | \(1\)، وجميع الأعداد الأولية من \(11\) إلى \(280\) |
| \(G_2\) | \(2^2,\ 3^2,\ 5^2,\ 7^2\) | \(11^2,\ 13^2\) |
| \(G_3\) | \(2^3,\ 3^3,\ 5^3,\ 7\cdot17\) | \(11\cdot13\) |
| \(G_4\) | \(2^4,\ 3^4,\ 5\cdot23,\ 7\cdot29\) | \(11\cdot17,\ 13\cdot19\) |
| \(G_5\) | \(2^5,\ 3^5,\ 5\cdot29,\ 7\cdot23\) | \(11\cdot19,\ 13\cdot17\) |
| \(G_6\) | \(2^6,\ 3\cdot13,\ 5\cdot17,\ 7\cdot19\) | \(11\cdot23\) |
جميع الأعداد المعروضة تنتمي إلى \(S\)، والمجموعات الست متباينة فيما بينها. وفي كل صف، لا يوجد عدد أولي يقسم عددين مختلفين من الأعداد الواردة فيه، لذا فإن عناصر كل \(G_i\) أولية نسبيًا مثنى مثنى.
علاوة على ذلك، تغطي هذه المجموعات جميع عناصر \(S\setminus F\) و\(24\) عنصرًا بالضبط من \(F\). لذلك، إذا كتبنا \[ U=G_1\cup\cdots\cup G_6, \] فإن لدينا \[ |S\setminus U|=|F|-24=192. \]
لتكن \(A\subseteq S\) لا تحتوي على خمسة أعداد أولية نسبيًا مثنى مثنى. لا يمكن أن تحتوي أي \(G_i\) على أكثر من أربعة عناصر من \(A\). ومن ثم \[ |A| =|A\setminus U|+\sum_{i=1}^{6}|A\cap G_i| \le192+6\cdot4 =216. \] إذن تحتوي كل مجموعة جزئية ذات \(217\) عنصرًا على خمسة أعداد أولية نسبيًا مثنى مثنى. ومع المثال \(F\)، يثبت هذا أن أصغر عدد صحيح هو \(\boxed{217}\).
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).