Тема Курчатов - задания по годам

Курчатов 2019

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела курчатов - задания по годам

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#73406

В каждой клетке квадратной таблицы размером $200×200$ написали по действительному числу, по модулю не превосходящему $1.$ Оказалось, что сумма всех чисел равна нулю. Для какого наименьшего $S$ можно утверждать, что в какой-то строке или каком-то столбце сумма чисел заведомо окажется по модулю не превышающей $S?$

Источники: Курчатов-2019, 10.5 (см. olimpiadakurchatov.ru)

Показать ответ и решение

Сначала покажем, что $S < 100$ не подойдет. Разделим таблицу на четыре квадрата $100 ×100.$ Правый верхний квадрат заполним числами $+1,$ а левый нижний - числами $− 1.$ Остальные клетки заполним нулями. Легко видеть, что в каждой строке и в каждом столбце сумма равна $± 100.$

Теперь покажем, что $S = 100$ подходит. Предположим, что для некоторой таблицы это не так, то есть суммы во всех её строках и столбцах оказались либо больше $100,$ либо меньше $− 100.$ Заметим, что можно менять местами строки в таблице, не нарушая это свойство и условие задачи.

Поменяем местами строки так, чтобы их суммы убывали сверху вниз. Разделим таблицу на две половины $100× 200,$ верхнюю и нижнюю. Заметим, что либо в верхней половине все строки имеют положительную сумму, либо в нижней - все отрицательную. Тогда в одной из половин сумма по модулю больше $10000.$ Так как общая сумма всех чисел равна нулю, то в другой половине сумма такая же по модулю и противоположная по знаку.

Теперь отсортируем столбцы так, чтобы их суммы убывали слева направо. (Суммы в строках при этом не поменяются.) Аналогично, суммы в правой и в левой половине таблицы оказались по модулю больше $10000.$

Разобьем таблицу на четыре квадрата $100 ×100,$ суммы в них обозначим за $A,B,C,D :$


$A$	$B$

$C$	$D$

A + B > +10000 A + C > +10000 C + D< −10000 B + D <−10000

Заметим, что

2|A|+2|D|≥2A − 2D = (A + B)+(A +C )− (B+ D)− (C+ D)> 40000.

Это означает, что одно из чисел $A$ или $D$ по модулю превосходит $10000.$ Но в каждом из соответствующих квадратов всего $10000$ клеток, и числа в них по модулю не превосходят $1.$ Противоречие.

Ответ:

$100$