IMO 1971 · Problem 6
Let \(A=(a_{ij})(i,j=1,2,\ldots,n)\) be a square matrix whose elements are non-negative integers. Suppose that whenever an element \(a_{ij}=0\), the sum of the elements in the \(i\)th row and the \(j\)th column is \(\geq n\). Prove that the sum of all the elements of the matrix is \(\geq n^2/2\).
Official text of the problem. Official problem paper (PDF)
Solution
Let \(S\) be the sum of all entries, and let \(m\) be the smallest among all row sums and column sums.
If \(m\geq n/2\), summing the \(n\) row sums gives \[ S\geq nm\geq \frac{n^2}{2}. \]
Now suppose \(m<n/2\). Transposing the matrix if necessary, we may assume that some row has sum \(m\).
Every nonzero entry is an integer at least \(1\), so this row has at most \(m\) nonzero entries. It therefore has at least \(n-m\) zero entries. Choose \(n-m\) columns containing such zero entries. By the hypothesis, each of these columns has sum at least \(n-m\), since the chosen row has sum \(m\).
Each of the remaining \(m\) columns has sum at least \(m\), by the definition of \(m\). Consequently, \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] This proves the assertion in every case. \(\square\)
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1971 · Aufgabe 6
Sei \(A=(a_{ij})(i,j=1,2,\ldots,n)\) eine quadratische Matrix, deren Einträge nichtnegative ganze Zahlen sind. Es gelte: Wenn ein Eintrag \(a_{ij}=0\) ist, so ist die Summe der Einträge in der \(i\)-ten Zeile und der \(j\)-ten Spalte \(\geq n\). Beweise, dass die Summe aller Einträge der Matrix \(\geq n^2/2\) ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Sei \(S\) die Summe aller Einträge und \(m\) die kleinste aller Zeilen- und Spaltensummen.
Ist \(m\geq n/2\), so ergibt die Addition der \(n\) Zeilensummen \[ S\geq nm\geq \frac{n^2}{2}. \]
Nehmen wir nun an, dass \(m<n/2\) gilt. Indem wir die Matrix nötigenfalls transponieren, dürfen wir annehmen, dass eine Zeile die Summe \(m\) hat.
Jeder von null verschiedene Eintrag ist eine ganze Zahl, die mindestens \(1\) beträgt, also hat diese Zeile höchstens \(m\) von null verschiedene Einträge. Sie hat daher mindestens \(n-m\) Nulleinträge. Wir wählen \(n-m\) Spalten, die solche Nulleinträge enthalten. Nach Voraussetzung hat jede dieser Spalten eine Summe von mindestens \(n-m\), da die gewählte Zeile die Summe \(m\) hat.
Jede der übrigen \(m\) Spalten hat nach der Definition von \(m\) eine Summe von mindestens \(m\). Folglich gilt \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] Damit ist die Behauptung in jedem Fall bewiesen. \(\square\)
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1971 · Soru 6
\(A=(a_{ij})(i,j=1,2,\ldots,n)\), elemanları negatif olmayan tam sayılar olan bir kare matris olsun. Bir \(a_{ij}=0\) elemanı bulunduğunda, \(i\). satır ile \(j\). sütundaki elemanların toplamının \(\geq n\) olduğunu varsayalım. Matrisin bütün elemanlarının toplamının \(\geq n^2/2\) olduğunu kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
Bütün elemanların toplamı \(S\), tüm satır toplamları ve sütun toplamları arasındaki en küçük değer ise \(m\) olsun.
\(m\geq n/2\) ise \(n\) satır toplamını toplayarak \[ S\geq nm\geq \frac{n^2}{2} \] elde ederiz.
Şimdi \(m<n/2\) olduğunu varsayalım. Gerekirse matrisin transpozunu alarak bir satırın toplamının \(m\) olduğunu varsayabiliriz.
Sıfırdan farklı her eleman en az \(1\) olan bir tam sayı olduğundan, bu satırda sıfırdan farklı en fazla \(m\) eleman vardır. Dolayısıyla bu satırın en az \(n-m\) elemanı sıfırdır. Bu sıfır elemanları içeren \(n-m\) sütun seçelim. Seçilen satırın toplamı \(m\) olduğundan, verilen koşula göre bu sütunların her birinin toplamı en az \(n-m\)'dir.
\(m\)'nin tanımı gereği, kalan \(m\) sütunun her birinin toplamı en az \(m\)'dir. Dolayısıyla, \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] Böylece önerme her durumda kanıtlanmış olur. \(\square\)
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1971 · Problema 6
Sea \(A=(a_{ij})(i,j=1,2,\ldots,n)\) una matriz cuadrada cuyos elementos son enteros no negativos. Supongamos que, siempre que un elemento \(a_{ij}=0\), la suma de los elementos de la fila \(i\) y de la columna \(j\) es \(\geq n\). Demuestre que la suma de todos los elementos de la matriz es \(\geq n^2/2\).
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Sea \(S\) la suma de todos los elementos, y sea \(m\) la menor de todas las sumas de filas y de columnas.
Si \(m\geq n/2\), al sumar las \(n\) sumas de las filas se obtiene \[ S\geq nm\geq \frac{n^2}{2}. \]
Supongamos ahora que \(m<n/2\). Trasponiendo la matriz si es necesario, podemos suponer que alguna fila tiene suma \(m\).
Todo elemento no nulo es un entero mayor o igual que \(1\), por lo que esta fila tiene a lo sumo \(m\) elementos no nulos. Por tanto, tiene al menos \(n-m\) elementos nulos. Elijamos \(n-m\) columnas que contengan dichos elementos nulos. Por hipótesis, cada una de estas columnas tiene suma al menos \(n-m\), puesto que la fila elegida tiene suma \(m\).
Cada una de las \(m\) columnas restantes tiene suma al menos \(m\), por la definición de \(m\). En consecuencia, \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] Esto demuestra la afirmación en todos los casos. \(\square\)
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1971 · 问题 6
设 \(A=(a_{ij})(i,j=1,2,\ldots,n)\) 是一个元素均为非负整数的方阵。假设只要元素 \(a_{ij}=0\)，第 \(i\) 行与第 \(j\) 列的元素之和就满足 \(\geq n\)。证明：矩阵所有元素之和满足 \(\geq n^2/2\)。
题目译自官方英文原文。 官方试卷 (PDF)
解答
设 \(S\) 为所有元素之和，\(m\) 为所有行和与列和中的最小值。
若 \(m\geq n/2\)，将 \(n\) 个行和相加，得到 \[ S\geq nm\geq \frac{n^2}{2}. \]
现设 \(m<n/2\)。必要时将矩阵转置，可不妨假设某一行的元素之和为 \(m\)。
每个非零元素都是至少为 \(1\) 的整数，因此这一行至多有 \(m\) 个非零元素。所以，它至少有 \(n-m\) 个零元素。选取包含这些零元素的 \(n-m\) 列。由题设，由于所选行的元素之和为 \(m\)，这些列中每一列的元素之和都至少为 \(n-m\)。
根据 \(m\) 的定义，其余 \(m\) 列中每一列的元素之和都至少为 \(m\)。因此， \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] 这就证明了命题在所有情形下都成立。\(\square\)
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1971 · Задача 6
Пусть \(A=(a_{ij})(i,j=1,2,\ldots,n)\) — квадратная матрица, элементы которой являются неотрицательными целыми числами. Предположим, что всякий раз, когда элемент \(a_{ij}=0\), сумма элементов в \(i\)-й строке и \(j\)-м столбце составляет \(\geq n\). Докажите, что сумма всех элементов матрицы составляет \(\geq n^2/2\).
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Пусть \(S\) — сумма всех элементов, а \(m\) — наименьшая из всех сумм элементов строк и столбцов.
Если \(m\geq n/2\), то, складывая суммы элементов \(n\) строк, получаем \[ S\geq nm\geq \frac{n^2}{2}. \]
Теперь предположим, что \(m<n/2\). При необходимости транспонируя матрицу, можно считать, что сумма элементов некоторой строки равна \(m\).
Каждый ненулевой элемент — целое число, не меньшее \(1\), поэтому в этой строке не более \(m\) ненулевых элементов. Следовательно, в ней не менее \(n-m\) нулевых элементов. Выберем \(n-m\) столбцов, содержащих такие нулевые элементы. По условию сумма элементов каждого из этих столбцов не меньше \(n-m\), поскольку сумма элементов выбранной строки равна \(m\).
В каждом из оставшихся \(m\) столбцов сумма элементов не меньше \(m\) по определению \(m\). Следовательно, \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] Это доказывает утверждение во всех случаях. \(\square\)
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1971 · المسألة 6
لتكن \(A=(a_{ij})(i,j=1,2,\ldots,n)\) مصفوفة مربعة عناصرها أعداد صحيحة غير سالبة. لنفترض أنه كلما كان عنصر \(a_{ij}=0\)، كان مجموع العناصر في الصف ذي الرقم \(i\) والعمود ذي الرقم \(j\) هو \(\geq n\). أثبت أن مجموع جميع عناصر المصفوفة هو \(\geq n^2/2\).
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
ليكن \(S\) مجموع جميع العناصر، وليكن \(m\) أصغر مجموع من بين مجاميع الصفوف ومجاميع الأعمدة كلها.
إذا كان \(m\geq n/2\)، فإن جمع مجاميع الصفوف الـ \(n\) يعطي \[ S\geq nm\geq \frac{n^2}{2}. \]
لنفترض الآن أن \(m<n/2\). بالانتقال إلى منقول المصفوفة إذا لزم الأمر، يمكننا افتراض أن أحد الصفوف مجموعه \(m\).
كل عنصر غير صفري هو عدد صحيح لا يقل عن \(1\)، لذا فإن هذا الصف يحتوي على \(m\) عناصر غير صفرية على الأكثر. ولذلك يحتوي على \(n-m\) عناصر صفرية على الأقل. نختار \(n-m\) أعمدة تحتوي على هذه العناصر الصفرية. وبحسب الفرض، لا يقل مجموع كل من هذه الأعمدة عن \(n-m\)، لأن مجموع الصف المختار هو \(m\).
ولا يقل مجموع كل من الأعمدة الـ \(m\) المتبقية عن \(m\)، بحسب تعريف \(m\). ومن ثم، \[ S\geq (n-m)(n-m)+m\cdot m =(n-m)^2+m^2 =\frac{n^2}{2}+2\left(m-\frac n2\right)^2 \geq \frac{n^2}{2}. \] وهذا يثبت العبارة في جميع الحالات. \(\square\)
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).