|
|
 |
Условие
В каждую клетку бесконечного листа клетчатой бумаги вписано некоторое число так, что сумма чисел в любом квадрате, стороны которого идут по линиям сетки, по модулю не превосходит единицы.
а) Докажите существование такого числа $c$, что сумма чисел в любом прямоугольнике, стороны которого идут по линиям сетки, не больше $c$; другими словами, докажите, что суммы чисел в прямоугольниках ограничены.
б) Докажите, что можно взять $c = 4$.
в) Улучшите эту оценку – докажите, что утверждение верно для $c = 3$.
г) Постройте пример, показывающий, что при $c < 3$ утверждение неверно.
Решение
Предположим, что в некотором прямоугольнике со сторонами $a$ и $b$ ($a < b$) сумма по модулю равна $4 + \varepsilon$, где $\varepsilon > 0$. Построим четыре квадрата, у каждого из которых три стороны идут по некоторым трём сторонам этого прямоугольника $a \times b$; тогда прямые, на которых лежат четвёртые стороны этих квадратов, образуют новый прямоугольник со сторонами $2 b - a$ и $|2 a - b|$ (см. рис. 1 и 2; случай $b = 2 a$, разумеется, невозможен).
Можно считать, что $S_4 + S_5 + S_6 = 4 + \varepsilon$ (если эта сумма равна $-(4 + \varepsilon)$, то заменим знаки у всех чисел на противоположные).
Рассмотрим сначала случай $b < 2 a$. Тогда $$S_5 = (S_4 + S_5) + (S_5 + S_6) - (S_4 + S_5 + S_6) \le 1 + 1 - 4 - \varepsilon = -2 - \varepsilon,$$ $$S_2 + S_8 = (S_1 + S_2 + S_3 + S_4 + S_5 + S_6) + (S_4 + S_5 + S_6 + S_7 + S_8 + S_9) - S_1 - S_3 - S_7 - S_9 - 2(S_4 + S_5 + S_6) \le$$ $$\le 1 + 1 + 1 + 1 + 1 + 1 - 2(4 + \varepsilon) = -2 - 2 \varepsilon,$$ откуда $S_2 + S_5 + S_8 \le -4 - 3 \varepsilon.$
Аналогично если $b > 2 a$, то $$S_5 = - S_4 - S_5 + (S_4 + S_5 + S_6) \le -1 -1 + 4 + \varepsilon \le 2 + \varepsilon,$$ $$S_2 + S_8 = (S_1 + S_2) + (S_2 + S_3) + (S_7 + S_8) + (S_8 + S_9) - (S_1 + S_2 + S_3 + S_4 + S_5 + S_6) - $$ $$-(S_4 + S_5 + S_6 + S_7 + S_8 + S_9) + 2(S_4 + S_5 + S_6) \ge 2 + 2 \varepsilon,$$ $$S_2 + S_5 + S_8 \ge 4 + 3 \varepsilon.$$ Итак, мы доказали, что если в прямоугольнике $a_1 \times b_1$ сумма чисел по модулю больше $4 + \varepsilon$, то в новом прямоугольнике $a_2 \times b_2$, где $a_2 = |2 a_1 - b_1|$, $b_2 = 2 b_1 - a_1$, сумма чисел по модулю больше $4 + 3 \varepsilon$. Для прямоугольника $a_2 \times b_2$ мы можем построить точно тем же способом новый прямоугольник $a_3 \times b_3$, в котором сумма чисел будет больше $4 + 3 \cdot 3 \varepsilon = 4 + 9 \varepsilon$, и так далее – такую последовательность прямоугольников $a_1 \times b_1$, $a_2 \times b_2$, ..., $a_n \times b_n$, ..., что в прямоугольнике $a_n \times b_n$ сумма чисел по модулю больше $4 + 3^{n - 1} \varepsilon$.
Докажем, что в этой последовательности все прямоугольники, начиная с некоторого, будут относиться ко второму типу, то есть для них $b_n > 2 a_n$. Действительно, во-первых, легко проверить, что если $\frac{a_n}{b_n} < \frac{1}{2},$ то и $\frac{a_{n+1}}{b_{n+1}} = \frac{b_n-2a_n}{2b_n-a_n} < \frac{1}2$. Во-вторых, если $\frac{a_n}{b_n} > \frac{1}{2},$ то $$\frac{1-\frac{a_{n+1}}{1-b_{n+1}}}{1-\frac{a_n}{b_n}} = \frac{1-\frac{2a_n-b_n}{2b_n-a_n}}{1-\frac{a_n}{b_n}} = \frac{3b_n}{2b_n-a_n} > \frac{3b_n}{2b_n-\frac{b_n}2} = 2;$$ таким образом, величина $1-\frac{a_n}{b_n}$ при переходе от $n$ к $n+1$ увеличивается не менее чем в два раза до тех пор, пока мы не придём к прямоугольнику с $\frac{a_n}{b_n} \ge \frac{1}2$. Поэтому, каким бы малым ни было $1-\frac{a_1}{b_1}$, всегда после нескольких операций мы придём к прямоугольнику второго типа, и дальше в нашей последовательности будут встречаться только такие прямоугольники.
Поэтому можно считать, что уже $\frac{a_1}{b_1} < \frac{1}2$.
При этом $$a_3 = b_2 - 2 a_2 = (2 b_1 - a_1) - 2(b_1 - 2 a_1) = 3 a_1,$$ $$b_3 = 2b_2 - a_2 = 2(2 b_1 - a_1) - (b_1 - 2 a_1) = 3 b_1.$$ Следовательно, вообще $a_{2k+1} = 3^k a_1$ и $b_{2k+1} = 3^k b_1$, причём сумма чисел в этом прямоугольнике $3^k a_1 \times 3^k b_1$ больше $4 + 9^k \varepsilon$, то есть, выбрав $k$ достаточно большим, мы можем сделать её сколь угодно большой. Но прямоугольник $Na_1 \times Nb_1$, где $a_1$, $b_1$ и $N$ – целые числа, можно разбить на $a_1 b_1$ квадратов (со стороной $N$), и поэтому сумма чисел в нём не может превосходить по модулю числа $a_1 b_1$. Противоречие.
Рис. 3 поясняет вторую половину доказательства.
г) На рис.4 изображен пример, для которого сумма чисел в некотором прямоугольнике равна $3$. Таким образом, для $c < 3$ утверждение задачи неверно.
в) Решение этой задачи неизвестно. Более того, весьма правдоподобно, что точная оценка $c = 4$. Впрочем, примеры, показывающие, что $c$ может быть больше $3$, тоже неизвестны.
