IMO 2001 · Problem 3
Twenty-one girls and twenty-one boys took part in a mathematical contest.
- Each contestant solved at most six problems.
- For each girl and each boy, at least one problem was solved by both of them.
Prove that there was a problem that was solved by at least three girls and at least three boys.
Official text of the problem. Official problem paper (PDF)
Solution
Suppose, for a contradiction, that no problem was solved by at least three girls and at least three boys. Consider only problems solved by at least one contestant, and partition them into two classes:
- \(\mathcal A\): problems solved by at most two girls;
- \(\mathcal B\): problems solved by at least three girls, hence by at most two boys.
Every girl solved at least one problem in \(\mathcal A\). Indeed, otherwise all her problems would belong to \(\mathcal B\). Since she solved at most six problems, each solved by at most two boys, she could share a solved problem with at most \(12\) boys, contradicting the hypothesis. Consequently, every girl solved at most five problems in \(\mathcal B\).
Similarly, every boy solved at least one problem in \(\mathcal B\): otherwise his at most six problems, all in \(\mathcal A\), could connect him to at most \(12\) girls. Thus every boy solved at most five problems in \(\mathcal A\).
For each problem \(p\), let \(g_p\) and \(b_p\) denote the numbers of girls and boys who solved it. Since each of the \(21^2=441\) girl–boy pairs shares at least one solved problem, \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] On the other hand, \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] because each boy solved at most five problems in \(\mathcal A\). Likewise, \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] Together these inequalities give \(441\le420\), a contradiction.
Therefore some problem was solved by at least three girls and at least three boys. \(\square\)
The solution was checked against Evan Chen's published IMO solution notes.
IMO 2001 · Aufgabe 3
Einundzwanzig Mädchen und einundzwanzig Jungen nahmen an einem Mathematikwettbewerb teil.
- Jeder Teilnehmer löste höchstens sechs Aufgaben.
- Für jedes Mädchen und jeden Jungen gab es mindestens eine Aufgabe, die beide gelöst hatten.
Man beweise, dass es eine Aufgabe gab, die von mindestens drei Mädchen und mindestens drei Jungen gelöst wurde.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir nehmen zum Widerspruch an, dass keine Aufgabe von mindestens drei Mädchen und mindestens drei Jungen gelöst wurde. Wir betrachten nur Aufgaben, die von mindestens einem Teilnehmer gelöst wurden, und teilen sie in zwei Klassen ein:
- \(\mathcal A\): Aufgaben, die von höchstens zwei Mädchen gelöst wurden;
- \(\mathcal B\): Aufgaben, die von mindestens drei Mädchen, also von höchstens zwei Jungen gelöst wurden.
Jedes Mädchen löste mindestens eine Aufgabe aus \(\mathcal A\). Andernfalls würden nämlich alle von ihm gelösten Aufgaben zu \(\mathcal B\) gehören. Da es höchstens sechs Aufgaben löste, von denen jede von höchstens zwei Jungen gelöst wurde, könnte es mit höchstens \(12\) Jungen eine gelöste Aufgabe gemeinsam haben, im Widerspruch zur Voraussetzung. Folglich löste jedes Mädchen höchstens fünf Aufgaben aus \(\mathcal B\).
Ebenso löste jeder Junge mindestens eine Aufgabe aus \(\mathcal B\): Andernfalls könnte er über seine höchstens sechs gelösten Aufgaben, die alle zu \(\mathcal A\) gehören würden, mit höchstens \(12\) Mädchen eine gelöste Aufgabe gemeinsam haben. Somit löste jeder Junge höchstens fünf Aufgaben aus \(\mathcal A\).
Für jede Aufgabe \(p\) bezeichnen \(g_p\) und \(b_p\) die Anzahlen der Mädchen beziehungsweise Jungen, die sie gelöst haben. Da jedes der \(21^2=441\) Paare aus einem Mädchen und einem Jungen mindestens eine gelöste Aufgabe gemeinsam hat, gilt \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] Andererseits gilt \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] da jeder Junge höchstens fünf Aufgaben aus \(\mathcal A\) löste. Ebenso gilt \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] Zusammen ergeben diese Ungleichungen \(441\le420\), einen Widerspruch.
Also wurde eine Aufgabe von mindestens drei Mädchen und mindestens drei Jungen gelöst. \(\square\)
Die Lösung wurde mit den veröffentlichten IMO-Lösungsnotizen von Evan Chen abgeglichen.
IMO 2001 · Soru 3
Bir matematik yarışmasına yirmi bir kız ve yirmi bir erkek katılmıştır.
- Her yarışmacı en fazla altı soru çözmüştür.
- Her kız ve her erkek için, ikisinin de çözdüğü en az bir soru vardır.
En az üç kızın ve en az üç erkeğin çözdüğü bir soru olduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Çelişki elde etmek amacıyla, en az üç kızın ve en az üç erkeğin çözdüğü hiçbir soru olmadığını varsayalım. Yalnızca en az bir yarışmacının çözdüğü soruları ele alıp bunları iki sınıfa ayıralım:
- \(\mathcal A\): en fazla iki kızın çözdüğü sorular;
- \(\mathcal B\): en az üç kızın, dolayısıyla en fazla iki erkeğin çözdüğü sorular.
Her kız \(\mathcal A\)'daki en az bir soruyu çözmüştür. Gerçekten de aksi hâlde çözdüğü tüm sorular \(\mathcal B\)'de olurdu. Her birini en fazla iki erkeğin çözdüğü en fazla altı soru çözdüğünden, en fazla \(12\) erkekle ortak çözdüğü bir soru bulunabilirdi; bu ise varsayımla çelişir. Dolayısıyla her kız \(\mathcal B\)'deki en fazla beş soruyu çözmüştür.
Benzer biçimde, her erkek \(\mathcal B\)'deki en az bir soruyu çözmüştür: aksi hâlde, çözdüğü ve hepsi \(\mathcal A\)'da olan en fazla altı soru aracılığıyla en fazla \(12\) kızla ortak bir soru çözmüş olabilirdi. Böylece her erkek \(\mathcal A\)'daki en fazla beş soruyu çözmüştür.
Her \(p\) sorusu için, bu soruyu çözen kızların ve erkeklerin sayılarını sırasıyla \(g_p\) ve \(b_p\) ile gösterelim. \(21^2=441\) kız–erkek çiftinin her birinin ortak çözdüğü en az bir soru olduğundan \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] Öte yandan, her erkek \(\mathcal A\)'daki en fazla beş soruyu çözdüğünden \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210. \] Benzer şekilde, \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] Bu eşitsizlikler birlikte \(441\le420\) sonucunu verir; bu bir çelişkidir.
Dolayısıyla en az üç kızın ve en az üç erkeğin çözdüğü bir soru vardır. \(\square\)
Çözüm, Evan Chen'in yayımlanmış IMO çözüm notlarıyla karşılaştırılarak kontrol edildi.
IMO 2001 · Problema 3
Veintiuna chicas y veintiún chicos participaron en un concurso de matemáticas.
- Cada participante resolvió a lo sumo seis problemas.
- Para cada chica y cada chico, hubo al menos un problema que ambos resolvieron.
Demostrar que hubo un problema que resolvieron al menos tres chicas y al menos tres chicos.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Supongamos, por reducción al absurdo, que ningún problema fue resuelto por al menos tres chicas y al menos tres chicos. Consideremos únicamente los problemas resueltos por al menos un participante y dividámoslos en dos clases:
- \(\mathcal A\): problemas resueltos por a lo sumo dos chicas;
- \(\mathcal B\): problemas resueltos por al menos tres chicas y, por tanto, por a lo sumo dos chicos.
Cada chica resolvió al menos un problema de \(\mathcal A\). En efecto, de lo contrario todos los problemas que resolvió pertenecerían a \(\mathcal B\). Como resolvió a lo sumo seis problemas, cada uno resuelto por a lo sumo dos chicos, podría tener un problema resuelto en común con a lo sumo \(12\) chicos, lo que contradice la hipótesis. En consecuencia, cada chica resolvió a lo sumo cinco problemas de \(\mathcal B\).
Análogamente, cada chico resolvió al menos un problema de \(\mathcal B\): de lo contrario, los a lo sumo seis problemas que resolvió, todos de \(\mathcal A\), podrían vincularlo con a lo sumo \(12\) chicas. Por tanto, cada chico resolvió a lo sumo cinco problemas de \(\mathcal A\).
Para cada problema \(p\), sean \(g_p\) y \(b_p\) los números de chicas y chicos que lo resolvieron. Como cada una de las \(21^2=441\) parejas formadas por una chica y un chico tiene al menos un problema resuelto en común, \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] Por otra parte, \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] porque cada chico resolvió a lo sumo cinco problemas de \(\mathcal A\). Asimismo, \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] Estas desigualdades dan conjuntamente \(441\le420\), una contradicción.
Por tanto, algún problema fue resuelto por al menos tres chicas y al menos tres chicos. \(\square\)
La solución se comprobó con las notas de soluciones de la IMO publicadas por Evan Chen.
IMO 2001 · 问题 3
二十一名女生和二十一名男生参加了一次数学竞赛。
- 每名参赛者至多解出了六道题。
- 对每一名女生和每一名男生，都至少有一道题是他们两人都解出的。
证明：有一道题至少有三名女生和三名男生解出。
题目译自官方英文原文。 官方试卷 (PDF)
解答
用反证法，假设没有任何一道题至少有三名女生和三名男生解出。只考虑至少有一名参赛者解出的题目，并将它们分为两类：
- \(\mathcal A\)：至多有两名女生解出的题目；
- \(\mathcal B\)：至少有三名女生解出的题目，因而至多有两名男生解出。
每名女生都至少解出了一道 \(\mathcal A\) 中的题目。事实上，否则她解出的所有题目都属于 \(\mathcal B\)。由于她至多解出了六道题，而每道题至多有两名男生解出，因此至多有 \(12\) 名男生与她解出过同一道题，这与题设矛盾。所以，每名女生至多解出了五道 \(\mathcal B\) 中的题目。
同样，每名男生都至少解出了一道 \(\mathcal B\) 中的题目：否则，他解出的至多六道题全部属于 \(\mathcal A\)，从而至多有 \(12\) 名女生与他解出过同一道题。因此，每名男生至多解出了五道 \(\mathcal A\) 中的题目。
对每道题 \(p\)，设 \(g_p\) 和 \(b_p\) 分别表示解出该题的女生人数和男生人数。由于 \(21^2=441\) 对女生与男生中的每一对都至少解出过一道相同的题目， \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] 另一方面， \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] 因为每名男生至多解出了五道 \(\mathcal A\) 中的题目。同理， \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] 综合这些不等式，得到 \(441\le420\)，矛盾。
因此，有一道题至少有三名女生和三名男生解出。\(\square\)
解答已与 Evan Chen 发布的 IMO 解答笔记核对。
IMO 2001 · Задача 3
В математической олимпиаде участвовали двадцать одна девочка и двадцать один мальчик.
- Каждый участник решил не более шести задач.
- Для каждой девочки и каждого мальчика нашлась хотя бы одна задача, которую решили они оба.
Докажите, что нашлась задача, которую решили не менее трёх девочек и не менее трёх мальчиков.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Предположим противное: ни одну задачу не решили одновременно не менее трёх девочек и не менее трёх мальчиков. Рассмотрим только задачи, решённые хотя бы одним участником, и разобьём их на два класса:
- \(\mathcal A\): задачи, решённые не более чем двумя девочками;
- \(\mathcal B\): задачи, решённые не менее чем тремя девочками, а значит, не более чем двумя мальчиками.
Каждая девочка решила хотя бы одну задачу из \(\mathcal A\). Действительно, иначе все решённые ею задачи принадлежали бы \(\mathcal B\). Поскольку она решила не более шести задач, каждую из которых решили не более двух мальчиков, общая решённая задача могла бы найтись у неё не более чем с \(12\) мальчиками, что противоречит условию. Следовательно, каждая девочка решила не более пяти задач из \(\mathcal B\).
Аналогично, каждый мальчик решил хотя бы одну задачу из \(\mathcal B\): иначе все решённые им задачи, которых не более шести и которые принадлежат \(\mathcal A\), могли бы обеспечить ему общую решённую задачу не более чем с \(12\) девочками. Таким образом, каждый мальчик решил не более пяти задач из \(\mathcal A\).
Для каждой задачи \(p\) обозначим через \(g_p\) и \(b_p\) количество решивших её девочек и мальчиков. Поскольку у каждой из \(21^2=441\) пар «девочка — мальчик» есть хотя бы одна общая решённая задача, \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] С другой стороны, \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] поскольку каждый мальчик решил не более пяти задач из \(\mathcal A\). Аналогично, \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] Вместе эти неравенства дают \(441\le420\), что является противоречием.
Следовательно, некоторую задачу решили не менее трёх девочек и не менее трёх мальчиков. \(\square\)
Решение проверено по опубликованным заметкам Эвана Чена с решениями IMO.
IMO 2001 · المسألة 3
شاركت إحدى وعشرون فتاة وواحد وعشرون فتى في مسابقة رياضية.
- حل كل متسابق ست مسائل على الأكثر.
- لكل فتاة ولكل فتى، توجد مسألة واحدة على الأقل حلها كلاهما.
أثبت أن هناك مسألة حلها ما لا يقل عن ثلاث فتيات وثلاثة فتيان.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
لنفترض، طلبًا للتناقض، أنه لا توجد مسألة حلها ما لا يقل عن ثلاث فتيات وثلاثة فتيان. لننظر فقط إلى المسائل التي حلها متسابق واحد على الأقل، ولنقسمها إلى فئتين:
- \(\mathcal A\): المسائل التي حلتها فتاتان على الأكثر؛
- \(\mathcal B\): المسائل التي حلتها ثلاث فتيات على الأقل، ومن ثم حلها فتيان اثنان على الأكثر.
حلت كل فتاة مسألة واحدة على الأقل من \(\mathcal A\). بالفعل، لو لم يكن الأمر كذلك، لانتمت جميع المسائل التي حلتها إلى \(\mathcal B\). وبما أنها حلت ست مسائل على الأكثر، وحل كل مسألة منها فتيان اثنان على الأكثر، فلا يمكن أن تشترك في حل مسألة مع أكثر من \(12\) فتى، وهذا يناقض الفرض. وعليه، حلت كل فتاة خمس مسائل على الأكثر من \(\mathcal B\).
وبالمثل، حل كل فتى مسألة واحدة على الأقل من \(\mathcal B\): وإلا فإن المسائل التي حلها، وعددها ست على الأكثر وجميعها من \(\mathcal A\)، لا يمكن أن تجعله يشترك في حل مسألة مع أكثر من \(12\) فتاة. إذن حل كل فتى خمس مسائل على الأكثر من \(\mathcal A\).
لكل مسألة \(p\)، ليرمز \(g_p\) و\(b_p\) إلى عددي الفتيات والفتيان الذين حلوها، على الترتيب. وبما أن كل زوج من الأزواج المكونة من فتاة وفتى، وعددها \(21^2=441\)، يشترك في حل مسألة واحدة على الأقل، فإن \[ 441\le \sum_{p\in\mathcal A}g_pb_p+\sum_{p\in\mathcal B}g_pb_p. \] ومن جهة أخرى، \[ \sum_{p\in\mathcal A}g_pb_p \le 2\sum_{p\in\mathcal A}b_p \le 2\cdot21\cdot5=210, \] لأن كل فتى حل خمس مسائل على الأكثر من \(\mathcal A\). وبالمثل، \[ \sum_{p\in\mathcal B}g_pb_p \le 2\sum_{p\in\mathcal B}g_p \le 2\cdot21\cdot5=210. \] وتعطي هذه المتباينات مجتمعة \(441\le420\)، وهو تناقض.
إذن توجد مسألة حلها ما لا يقل عن ثلاث فتيات وثلاثة فتيان. \(\square\)
تمت مراجعة الحل بمقارنته بملاحظات حلول IMO المنشورة لإيفان تشين.