IMO 2021 · Problem 6
Let \(m \geq 2\) be an integer, \(A\) be a finite set of (not necessarily positive) integers, and \(B_1, B_2, B_3, \ldots, B_m\) be subsets of \(A\). Assume that for each \(k = 1, 2, \ldots, m\) the sum of the elements of \(B_k\) is \(m^k\). Prove that \(A\) contains at least \(m/2\) elements.
Official text of the problem. Official problem paper (PDF)
Solution
Write \(A=\{a_1,\ldots,a_n\}\). For each choice of integers \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] consider the number \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
These \(m^m\) choices give distinct numbers. Indeed, suppose two different choices \(c\) and \(d\) gave the same number, and let \(r\) be the smallest index with \(c_r\ne d_r\). Dividing their equality by \(m^r\) shows that \(c_r-d_r\) is divisible by \(m\), contradicting \[ 0<|c_r-d_r|\le m-1. \]
On the other hand, the given subset sums imply \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] Each \(t_i\) is an integer satisfying \[ 0\le t_i\le m(m-1)\le m^2-1. \] Consequently, there are at most \((m^2)^n\) possible coefficient vectors \((t_1,\ldots,t_n)\), and hence at most \(m^{2n}\) possible values of \(S\). This upper bound is valid regardless of the signs of the \(a_i\).
Comparing the two counts gives \[ m^m\le m^{2n}. \] Since \(m>1\), we obtain \(m\le 2n\), or \[ \boxed{|A|\ge \frac m2}. \]
The solution was checked against the official IMO shortlist solutions.
IMO 2021 · Aufgabe 6
Es seien \(m\ge 2\) eine ganze Zahl, \(A\) eine endliche Menge von (nicht notwendigerweise positiven) ganzen Zahlen und \(B_1,B_2,B_3,\ldots,B_m\) Teilmengen von \(A\). Es werde vorausgesetzt, dass für jedes \(1\le k\le m\) die Summe der Elemente von \(B_k\) genau \(m^k\) beträgt. Man beweise, dass \(A\) mindestens \(m/2\) Elemente enthält.
Offizieller deutscher Aufgabentext. Offizielles Aufgabenblatt (PDF)
Lösung
Schreibe \(A=\{a_1,\ldots,a_n\}\). Für jede Wahl ganzer Zahlen \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] betrachten wir die Zahl \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
Diese \(m^m\) Möglichkeiten ergeben verschiedene Zahlen. Nehmen wir nämlich an, zwei verschiedene Wahlen \(c\) und \(d\) ergäben dieselbe Zahl, und sei \(r\) der kleinste Index mit \(c_r\ne d_r\). Division der entsprechenden Gleichung durch \(m^r\) zeigt, dass \(c_r-d_r\) durch \(m\) teilbar ist, im Widerspruch zu \[ 0<|c_r-d_r|\le m-1. \]
Andererseits folgt aus den gegebenen Teilmengensummen \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] Jedes \(t_i\) ist eine ganze Zahl mit \[ 0\le t_i\le m(m-1)\le m^2-1. \] Folglich gibt es höchstens \((m^2)^n\) mögliche Koeffizientenvektoren \((t_1,\ldots,t_n)\) und damit höchstens \(m^{2n}\) mögliche Werte von \(S\). Diese obere Schranke gilt unabhängig von den Vorzeichen der \(a_i\).
Der Vergleich der beiden Anzahlen ergibt \[ m^m\le m^{2n}. \] Wegen \(m>1\) erhalten wir \(m\le 2n\), also \[ \boxed{|A|\ge \frac m2}. \]
Die Lösung wurde mit den offiziellen Lösungen der IMO-Shortlist abgeglichen.
IMO 2021 · Soru 6
\(m\ge 2\) bir tam sayı, \(A\) (pozitif olmak zorunda olmayan) tam sayılardan oluşan bir sonlu küme ve \(B_1,B_2,B_3,\ldots,B_m\) kümeleri \(A\) nın alt kümeleri olsun. Her \(k=1,2,\ldots,m\) için \(B_k\) kümesinin elemanlarının toplamı \(m^k\) dır. \(A\) kümesinin en az \(m/2\) eleman içerdiğini gösteriniz.
Sorunun resmi Türkçe metni. Resmi soru kâğıdı (PDF)
Çözüm
\(A=\{a_1,\ldots,a_n\}\) yazalım. \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] tam sayılarının her seçimi için \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k \] sayısını ele alalım.
Bu \(m^m\) seçim farklı sayılar verir. Gerçekten, iki farklı \(c\) ve \(d\) seçiminin aynı sayıyı verdiğini varsayalım ve \(r\), \(c_r\ne d_r\) olan en küçük indis olsun. Eşitliği \(m^r\)'ye bölmek, \(c_r-d_r\)'nin \(m\)'ye bölündüğünü gösterir; bu ise \[ 0<|c_r-d_r|\le m-1 \] eşitsizliğiyle çelişir.
Öte yandan, verilen alt küme toplamlarından \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k \] elde edilir. Her \(t_i\), \[ 0\le t_i\le m(m-1)\le m^2-1 \] eşitsizliklerini sağlayan bir tam sayıdır. Dolayısıyla en fazla \((m^2)^n\) olası \((t_1,\ldots,t_n)\) katsayı vektörü ve bu nedenle \(S\)'nin en fazla \(m^{2n}\) olası değeri vardır. Bu üst sınır, \(a_i\)'lerin işaretlerinden bağımsız olarak geçerlidir.
İki sayımı karşılaştırarak \[ m^m\le m^{2n} \] elde ederiz. \(m>1\) olduğundan \(m\le 2n\), yani \[ \boxed{|A|\ge \frac m2} \] elde edilir.
Çözüm, resmi IMO shortlist çözümleriyle karşılaştırılarak kontrol edildi.
IMO 2021 · Problema 6
Sean \(m \ge 2\) un entero, \(A\) un conjunto finito de enteros (no necesariamente positivos), y \(B_1,B_2,B_3,\ldots,B_m\) subconjuntos de \(A\). Suponemos que para cada \(k = 1, 2, \ldots, m\), la suma de los elementos de \(B_k\) es \(m^k\). Probar que \(A\) contiene al menos \(m/2\) elementos.
Texto oficial en español del problema. Enunciado oficial (PDF)
Solución
Escribamos \(A=\{a_1,\ldots,a_n\}\). Para cada elección de enteros \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] consideremos el número \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
Estas \(m^m\) elecciones dan números distintos. En efecto, supongamos que dos elecciones distintas \(c\) y \(d\) dieran el mismo número, y sea \(r\) el menor índice con \(c_r\ne d_r\). Dividiendo la igualdad entre \(m^r\), se ve que \(c_r-d_r\) es divisible por \(m\), lo que contradice \[ 0<|c_r-d_r|\le m-1. \]
Por otro lado, las sumas dadas de los subconjuntos implican \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] Cada \(t_i\) es un entero que satisface \[ 0\le t_i\le m(m-1)\le m^2-1. \] Por consiguiente, hay a lo sumo \((m^2)^n\) vectores de coeficientes \((t_1,\ldots,t_n)\) posibles y, por tanto, a lo sumo \(m^{2n}\) valores posibles de \(S\). Esta cota superior es válida independientemente de los signos de los \(a_i\).
Comparando los dos recuentos, obtenemos \[ m^m\le m^{2n}. \] Como \(m>1\), obtenemos \(m\le 2n\), o bien \[ \boxed{|A|\ge \frac m2}. \]
La solución se comprobó con las soluciones oficiales de la shortlist de la IMO.
IMO 2021 · 问题 6
设整数 \(m\ge 2\). 设集合 \(A\) 由有限个整数 (不一定为正) 构成, 且 \(B_1,B_2,B_3,\ldots,B_m\) 是 \(A\) 的子集. 假设对任意 \(k=1,2,\ldots,m\), \(B_k\) 中所有元素之和为 \(m^k\). 证明: \(A\) 包含至少 \(m/2\) 个元素.
题目为官方中文译本。 官方试卷 (PDF)
解答
记 \(A=\{a_1,\ldots,a_n\}\)。对整数 \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] 的每一种选取，考虑数 \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
这 \(m^m\) 种选取给出互不相同的数。事实上，假设两种不同的选取 \(c\) 和 \(d\) 给出了相同的数，并设 \(r\) 是满足 \(c_r\ne d_r\) 的最小下标。将相应的等式两边除以 \(m^r\)，可知 \(c_r-d_r\) 能被 \(m\) 整除，这与 \[ 0<|c_r-d_r|\le m-1. \] 矛盾。
另一方面，由题设的子集元素之和可知 \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] 每个 \(t_i\) 都是整数，且满足 \[ 0\le t_i\le m(m-1)\le m^2-1. \] 因此，系数向量 \((t_1,\ldots,t_n)\) 至多有 \((m^2)^n\) 种可能，从而 \(S\) 至多有 \(m^{2n}\) 个可能的值。无论 \(a_i\) 的符号如何，这一上界都成立。
比较两次计数的结果，得到 \[ m^m\le m^{2n}. \] 由于 \(m>1\)，可得 \(m\le 2n\)，即 \[ \boxed{|A|\ge \frac m2}. \]
解答已与 IMO 官方预选题（shortlist）解答核对。
IMO 2021 · Задача 6
Дано целое число \(m\ge 2\). В конечном множестве \(A\), состоящем из (не обязательно положительных) целых чисел, нашлись такие подмножества \(B_1,B_2,B_3,\ldots,B_m\), что при каждом \(k=1,2,\ldots,m\) сумма элементов множества \(B_k\) равна \(m^k\). Докажите, что \(A\) содержит хотя бы \(m/2\) элементов.
Официальный русский текст задачи. Официальный текст задач (PDF)
Решение
Запишем \(A=\{a_1,\ldots,a_n\}\). Для каждого выбора целых чисел \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] рассмотрим число \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
Эти \(m^m\) вариантов выбора дают различные числа. Действительно, предположим, что два различных набора \(c\) и \(d\) дают одно и то же число, и пусть \(r\) — наименьший индекс, для которого \(c_r\ne d_r\). Разделив соответствующее равенство на \(m^r\), получаем, что \(c_r-d_r\) делится на \(m\), что противоречит неравенству \[ 0<|c_r-d_r|\le m-1. \]
С другой стороны, из заданных сумм элементов подмножеств следует \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] Каждое \(t_i\) — целое число, удовлетворяющее неравенствам \[ 0\le t_i\le m(m-1)\le m^2-1. \] Следовательно, существует не более \((m^2)^n\) возможных векторов коэффициентов \((t_1,\ldots,t_n)\), а значит, не более \(m^{2n}\) возможных значений \(S\). Эта верхняя оценка верна независимо от знаков \(a_i\).
Сравнивая результаты двух подсчётов, получаем \[ m^m\le m^{2n}. \] Поскольку \(m>1\), получаем \(m\le 2n\), или \[ \boxed{|A|\ge \frac m2}. \]
Решение проверено по официальным решениям шортлиста IMO.
IMO 2021 · المسألة 6
ليكن \(m\ge 2\) عدداً صحيحاً، و \(A\) مجموعة منتهية من الأعداد الصحيحة (ليست بالضرورة موجبة)، و \(B_1,B_2,B_3,\ldots,B_m\) مجموعات جزئية من \(A\). بفرض أنه لكل \(k=1,2,\ldots,m\) فإن مجموع عناصر \(B_k\) يساوي \(m^k\). أثبت أن \(A\) تحوي على الأقل \(m/2\) عنصراً.
نص المسألة هو الترجمة العربية الرسمية. ورقة المسائل الرسمية (PDF)
الحل
نكتب \(A=\{a_1,\ldots,a_n\}\). لكل اختيار للأعداد الصحيحة \[ c_1,\ldots,c_m\in\{0,1,\ldots,m-1\}, \] ننظر إلى العدد \[ S(c_1,\ldots,c_m)=\sum_{k=1}^{m}c_km^k. \]
تعطي هذه الاختيارات البالغ عددها \(m^m\) أعداداً متمايزة. بالفعل، لنفترض أن اختيارين مختلفين \(c\) و\(d\) أعطيا العدد نفسه، وليكن \(r\) أصغر دليل يحقق \(c_r\ne d_r\). بقسمة المساواة بينهما على \(m^r\)، يتبين أن \(c_r-d_r\) يقبل القسمة على \(m\)، وهذا يناقض \[ 0<|c_r-d_r|\le m-1. \]
من جهة أخرى، تستلزم المجاميع المعطاة لعناصر المجموعات الجزئية أن \[ S(c_1,\ldots,c_m) =\sum_{k=1}^{m}c_k\sum_{a_i\in B_k}a_i =\sum_{i=1}^{n}t_i a_i, \qquad t_i=\sum_{\substack{1\le k\le m\\a_i\in B_k}}c_k. \] كل \(t_i\) عدد صحيح يحقق \[ 0\le t_i\le m(m-1)\le m^2-1. \] وبالتالي، يوجد على الأكثر \((m^2)^n\) متجه معاملات ممكن \((t_1,\ldots,t_n)\)، ومن ثم يوجد على الأكثر \(m^{2n}\) قيمة ممكنة لـ\(S\). وهذا الحد الأعلى صحيح بغض النظر عن إشارات الأعداد \(a_i\).
بمقارنة العددين نحصل على \[ m^m\le m^{2n}. \] بما أن \(m>1\)، نحصل على \(m\le 2n\)، أو \[ \boxed{|A|\ge \frac m2}. \]
تمت مراجعة الحل بمقارنته بالحلول الرسمية لقائمة IMO المختصرة.