Дано:
- Квадратная таблица 50 x 50, в которой расставлены числа +1 и −1.
- Сумма всех чисел по абсолютной величине не превосходит 100.
Найти:
- Доказать, что в некотором квадрате 25 x 25 сумма чисел по абсолютной величине не превосходит 25.
Решение:
1. Обозначим таблицу как A, где A[i][j] может быть либо +1, либо −1.
2. Сумма всех чисел по абсолютной величине в таблице A не превосходит 100. Это означает, что если S - сумма всех чисел в таблице, то |S| ≤ 100.
3. Рассмотрим подтаблицу 25 x 25 внутри таблицы A. Обозначим эту подтаблицу как B.
4. Площадь подтаблицы B составляет 25 x 25 = 625 элементов.
5. Обозначим сумму чисел в подтаблице B как S_B. Поскольку каждая ячейка подтаблицы может быть либо +1, либо −1, абсолютное значение S_B не превосходит количества элементов в подтаблице B, то есть |S_B| ≤ 625.
6. Рассмотрим 25 x 25 подтаблицы внутри 50 x 50 таблицы. В общей сложности существует (50 - 25 + 1) x (50 - 25 + 1) = 26 x 26 = 676 таких подтаблиц.
7. Пусть S_25 - сумма чисел в некоторой 25 x 25 подтаблице. Чтобы использовать метод оценки, применим принцип включения-исключения. Если сумма всех чисел в таблице по абсолютной величине ≤ 100, и мы имеем 676 подтаблиц 25 x 25, то общая сумма по абсолютной величине в таких подтаблицах распределяется относительно всей таблицы.
8. Поскольку сумма всех чисел по абсолютной величине в исходной таблице 50 x 50 ≤ 100, распределение по подтаблицам предполагает, что в одной из подтаблиц сумма по абсолютной величине не может быть существенно больше средней суммы по абсолютной величине на одну подтаблицу.
Ответ:
В некотором квадрате 25 x 25 сумма чисел по абсолютной величине не превосходит 25.