|
|
 |
Условие
а) В таблицу 2×n (где n > 2) вписаны числа. Суммы во всех столбцах различны. Докажите, что можно переставить числа в таблице так, чтобы суммы в столбцах были различны и суммы в строках были различны.
б) В таблицу 10×10 вписаны числа. Суммы во всех столбцах различны. Всегда ли можно переставить числа в таблице так, чтобы суммы в столбцах были различны и суммы в строках были различны?
Решение
а) Допустим, суммы в строках равны. Если есть столбец, где числа различны, то поменяем их местами, и суммы чисел в строках станут разными.
Если в каждом столбце оба числа равны, то все числа в строке различны. Возьмём три наименьших числа a < b < c в верхней строке и переставим их циклически. Так как
b + a < a + c < b + c, причём b + c меньше суммы чисел в любом из оставшихся n – 3 столбцов, то суммы чисел в столбцах останутся различными. Теперь у нас есть столбец, где числа различны.
б) Приведём контрпример для таблицы n×n. Впишем в столбцы последовательно по 0, 1, ..., n – 2, n единиц, а в остальные клетки впишем нули. Число, равное
0 + 1 + … + (n – 2) + n, нельзя по-другому разбить на n целых различных неотрицательных слагаемых. Следовательно, указанное разбиение единиц по столбцам единственное, при котором суммы в них различны. Значит, при любой "допустимой" перестановке обязательно должны быть столбец из нулей и столбец из единиц. То же самое можно сказать и про строки, если суммы в них различны. Но наличие столбца из нулей противоречит наличию строки из единиц.
Ответ
б) Не всегда.
Замечания
Баллы: 3 + 6
