Азиатско-Тихоокеанская математическая олимпиада, 2012 год

В каждой ячейке клетчатой доски размера $2012 \times 2012$ по одному вписаны действительные числа, одновременно не меньше $0$ и не больше $1$. Рассмотрим разбиения доски на два непустых прямоугольника вдоль горизонтальной или вертикальной линии сетки. Пусть при любом таком разбиении хотя бы в одном из двух полученных прямоугольников сумма чисел не будет превышать $1$. Определите максимально возможную сумму всех чисел доски размера $2012 \times 2012$.

Комментарий/решение

Действительно, легко обобщить сетку $n \times n$ для $n \ge 3$ и получить $5$ как максимально возможную сумму. Сначала я запутался, потому что думал, что нельзя использовать $0$, но после того, как я понял, что можно, это стало легко.

Чтобы показать, что $5$ достижимо, поместите $1$ в $(2,1), (2,2), (2,3), (1,2), (3,2)$, а затем $0$ во что-нибудь еще.

Теперь мы показываем, что $5$ — это круто. Предположим, что сумма $S$ достижима. Тогда следует, что сумма некоторого столбца не меньше $S-2$, поскольку пусть сумма столбца $m^{th}$ равна $C_m$. Тогда как только $C_1 + C_2 + ... + C_k > 1$, нам, очевидно, понадобится $C_1 + C_2 + ... + C_k \ge S-1$. Затем, используя аналогичные аргументы, в этом столбце есть элемент размером не менее $S-4$, но это означает $S-4 \leq 1 S \le 5$, и мы закончили.