IMO 1972 · Problem 1
Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.
Official text of the problem. Official problem paper (PDF)
Solution
Let \(S\) be the given set. Each of its ten elements can either belong or not belong to a subset, so \(S\) has \(2^{10}=1024\) subsets.
For each subset \(T\subseteq S\), define \[ s(T)=\sum_{t\in T}t, \] with \(s(\varnothing)=0\). Since every element of \(S\) is an integer between \(10\) and \(99\), \[ 0\le s(T)\le 10\cdot99=990. \] Thus the \(1024\) subset sums take at most \(991\) different values. By the pigeonhole principle, there are distinct subsets \(A,B\subseteq S\) with \(s(A)=s(B)\).
Set \[ C=A\setminus B,\qquad D=B\setminus A. \] These subsets are disjoint, and removing the common elements gives \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] Moreover, both are nonempty: because \(A\ne B\), at least one is nonempty and therefore has positive sum; their equal sums force the other to be nonempty as well.
Hence \(C\) and \(D\) are two disjoint nonempty subsets whose members have the same sum. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1972 · Aufgabe 1
Beweise, dass man aus einer Menge von zehn verschiedenen zweistelligen Zahlen (im Dezimalsystem) zwei disjunkte Teilmengen auswählen kann, deren Elemente dieselbe Summe haben.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Sei \(S\) die gegebene Menge. Jedes ihrer zehn Elemente kann entweder zu einer Teilmenge gehören oder nicht, also hat \(S\) genau \(2^{10}=1024\) Teilmengen.
Definiere für jede Teilmenge \(T\subseteq S\) \[ s(T)=\sum_{t\in T}t, \] wobei \(s(\varnothing)=0\) ist. Da jedes Element von \(S\) eine ganze Zahl zwischen \(10\) und \(99\) ist, gilt \[ 0\le s(T)\le 10\cdot99=990. \] Somit nehmen die \(1024\) Teilmengensummen höchstens \(991\) verschiedene Werte an. Nach dem Schubfachprinzip gibt es verschiedene Teilmengen \(A,B\subseteq S\) mit \(s(A)=s(B)\).
Setze \[ C=A\setminus B,\qquad D=B\setminus A. \] Diese Teilmengen sind disjunkt, und durch Entfernen der gemeinsamen Elemente erhält man \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] Außerdem sind beide nicht leer: Wegen \(A\ne B\) ist mindestens eine nicht leer und hat daher eine positive Summe; da ihre Summen gleich sind, muss auch die andere nicht leer sein.
Damit sind \(C\) und \(D\) zwei disjunkte, nicht leere Teilmengen, deren Elemente dieselbe Summe haben. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1972 · Soru 1
On farklı iki basamaklı sayıdan (onluk sayı sisteminde) oluşan bir kümeden, elemanlarının toplamları eşit olan iki ayrık alt küme seçilebileceğini kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Verilen küme \(S\) olsun. On elemanının her biri bir alt kümeye ait olabilir veya olmayabilir; dolayısıyla \(S\) kümesinin \(2^{10}=1024\) alt kümesi vardır.
Her \(T\subseteq S\) alt kümesi için \[ s(T)=\sum_{t\in T}t, \] olarak tanımlayalım ve \(s(\varnothing)=0\) alalım. \(S\) kümesinin her elemanı \(10\) ile \(99\) arasında bir tam sayı olduğundan, \[ 0\le s(T)\le 10\cdot99=990. \] Böylece \(1024\) alt kümenin elemanlarının toplamları en fazla \(991\) farklı değer alır. Güvercin yuvası ilkesine göre, \(s(A)=s(B)\) olacak şekilde birbirinden farklı \(A,B\subseteq S\) alt kümeleri vardır.
\[ C=A\setminus B,\qquad D=B\setminus A \] olarak tanımlayalım. Bu alt kümeler ayrıktır ve ortak elemanlar çıkarıldığında \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D) \] elde edilir. Ayrıca her ikisi de boş değildir: \(A\ne B\) olduğundan en az biri boş değildir ve dolayısıyla elemanlarının toplamı pozitiftir; toplamlarının eşit olması diğerinin de boş olmamasını gerektirir.
O hâlde \(C\) ve \(D\), elemanlarının toplamları eşit olan, boş olmayan iki ayrık alt kümedir. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1972 · Problema 1
Demostrar que, de un conjunto de diez números distintos de dos cifras (en el sistema decimal), se pueden elegir dos subconjuntos disjuntos cuyos elementos tengan la misma suma.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Sea \(S\) el conjunto dado. Cada uno de sus diez elementos puede pertenecer o no a un subconjunto, por lo que \(S\) tiene \(2^{10}=1024\) subconjuntos.
Para cada subconjunto \(T\subseteq S\), definimos \[ s(T)=\sum_{t\in T}t, \] con \(s(\varnothing)=0\). Como cada elemento de \(S\) es un entero entre \(10\) y \(99\), \[ 0\le s(T)\le 10\cdot99=990. \] Así, las \(1024\) sumas de los subconjuntos toman a lo sumo \(991\) valores distintos. Por el principio del palomar, existen subconjuntos distintos \(A,B\subseteq S\) con \(s(A)=s(B)\).
Sean \[ C=A\setminus B,\qquad D=B\setminus A. \] Estos subconjuntos son disjuntos y, al eliminar los elementos comunes, se obtiene \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] Además, ambos son no vacíos: como \(A\ne B\), al menos uno es no vacío y, por tanto, tiene suma positiva; la igualdad de sus sumas obliga a que el otro también sea no vacío.
Por consiguiente, \(C\) y \(D\) son dos subconjuntos disjuntos no vacíos cuyos elementos tienen la misma suma. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1972 · 问题 1
证明：从一个由十个互不相同的两位数（十进制）组成的集合中，可以选出两个互不相交的子集，使这两个子集的元素之和相等。
题目译自官方英文原文。 官方试卷 (PDF)
解答
设给定的集合为 \(S\)。它的十个元素中的每一个都可以属于或不属于一个子集，因此 \(S\) 共有 \(2^{10}=1024\) 个子集。
对每个子集 \(T\subseteq S\)，定义 \[ s(T)=\sum_{t\in T}t, \] 并规定 \(s(\varnothing)=0\)。由于 \(S\) 中的每个元素都是介于 \(10\) 与 \(99\) 之间的整数， \[ 0\le s(T)\le 10\cdot99=990. \] 因此，这 \(1024\) 个子集的元素和至多有 \(991\) 个不同的值。由抽屉原理，存在不同的子集 \(A,B\subseteq S\)，使得 \(s(A)=s(B)\)。
令 \[ C=A\setminus B,\qquad D=B\setminus A. \] 这两个子集互不相交，去掉公共元素后可得 \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] 此外，它们都非空：由于 \(A\ne B\)，至少有一个非空，因而其元素和为正；两者的元素和相等，故另一个也必定非空。
因此，\(C\) 和 \(D\) 是两个互不相交的非空子集，且它们的元素之和相等。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1972 · Задача 1
Докажите, что из множества десяти различных двузначных чисел (в десятичной системе счисления) можно выбрать два непересекающихся подмножества с одинаковыми суммами элементов.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Пусть \(S\) — данное множество. Каждый из его десяти элементов может либо принадлежать, либо не принадлежать подмножеству, поэтому у \(S\) имеется \(2^{10}=1024\) подмножества.
Для каждого подмножества \(T\subseteq S\) определим \[ s(T)=\sum_{t\in T}t, \] полагая \(s(\varnothing)=0\). Поскольку каждый элемент \(S\) — целое число от \(10\) до \(99\), \[ 0\le s(T)\le 10\cdot99=990. \] Таким образом, \(1024\) суммы элементов подмножеств принимают не более \(991\) различных значений. По принципу Дирихле существуют различные подмножества \(A,B\subseteq S\), для которых \(s(A)=s(B)\).
Положим \[ C=A\setminus B,\qquad D=B\setminus A. \] Эти подмножества не пересекаются, и после удаления общих элементов получаем \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] Кроме того, оба они непусты: поскольку \(A\ne B\), хотя бы одно из них непусто и потому имеет положительную сумму элементов; из равенства сумм следует, что и другое подмножество непусто.
Следовательно, \(C\) и \(D\) — два непересекающихся непустых подмножества с одинаковыми суммами элементов. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1972 · المسألة 1
أثبت أنه يمكن اختيار مجموعتين جزئيتين متباينتين من مجموعة تضم عشرة أعداد مختلفة مكوّنة من رقمين (في النظام العشري)، بحيث يكون مجموع عناصر إحداهما مساويًا لمجموع عناصر الأخرى.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
لتكن \(S\) المجموعة المعطاة. كل عنصر من عناصرها العشرة إما أن ينتمي إلى مجموعة جزئية أو ألا ينتمي إليها، ولذلك فإن عدد المجموعات الجزئية للمجموعة \(S\) هو \(2^{10}=1024\).
لكل مجموعة جزئية \(T\subseteq S\)، نعرّف \[ s(T)=\sum_{t\in T}t, \] مع وضع \(s(\varnothing)=0\). وبما أن كل عنصر من عناصر \(S\) عدد صحيح بين \(10\) و\(99\)، فإن \[ 0\le s(T)\le 10\cdot99=990. \] إذن لا تأخذ مجاميع المجموعات الجزئية البالغ عددها \(1024\) أكثر من \(991\) قيمة مختلفة. وبحسب مبدأ الحمام، توجد مجموعتان جزئيتان مختلفتان \(A,B\subseteq S\) تحققان \(s(A)=s(B)\).
نضع \[ C=A\setminus B,\qquad D=B\setminus A. \] هاتان المجموعتان الجزئيتان متباينتان، وبحذف العناصر المشتركة نحصل على \[ s(C)=s(A)-s(A\cap B) =s(B)-s(A\cap B) =s(D). \] وفضلًا عن ذلك، كلتاهما غير خالية: فبما أن \(A\ne B\)، فإن إحداهما على الأقل غير خالية، ومن ثم يكون مجموع عناصرها موجبًا؛ وبما أن مجموعيهما متساويان، فلا بد أن تكون الأخرى غير خالية أيضًا.
إذن \(C\) و\(D\) مجموعتان جزئيتان متباينتان وغير خاليتين، ولهما مجموع العناصر نفسه. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).